【数据结构】二叉搜索树
目录
1、二叉搜索树的概念
2、二叉搜索树的实现
2.1 二叉搜索树的查找
查找规则是：1. 从根开始比较，比根大则取根的右子树查找，比根小则去根的左子树查找
2.做多查找高度次，走到空，还没找到，则这个值不存在
首先，创建一个结点
template<class K>
struct BSTNode // 二叉搜索树的结点
{
K _key;
BSTNode<K>* _left;
BSTNode<K>* _right;
BSTNode(const K& key)
:_key(key)
,_left(nullptr)
,_right(nullptr)
{}
};bool Find(const K& key)
{
Node* cur = _root;
while (cur) // 不为空时就继续找
{
if (cur->_key < key) cur = cur->_right;
else if (cur->_key > key) cur = cur->_left;
else return true; // 找到了返回true
}
return false; // 没找到返回false
}2.2 二叉搜索树的插入
首先，需要先判断一下这颗二叉搜索树是否为空，若是空，则直接创建一个结点，结点的值赋值为要插入的值，并将_root指向这个结点
若不为空，则按二叉搜索树的性质往下查找，从根节点开始往下查找，当前遍历到的结点的值小于插入的值，则到当前节点的右子树查找，当前遍历到的结点的值大于插入的值，则到当前节点的左子树查找，直到遍历到的结点为空，那么这个位置就是插入的位置
注意，一定要记录当前遍历到的结点的父节点，因为当遍历到的结点为空，要插入时，需要知道遍历到的结点的父节点才能插入
然后，遍历到的结点为空时，这时候只知道其父节点，但并不知道遍历到的位置是其父节点的左孩子还是右孩子，所以还需要用插入的那个值与父节点的值比较一下，以判断是父节点的左孩子还是右孩子
bool Insert(const K& key)
{
// 判断根节点是否为空
if (_root == nullptr)
{
_root = new Node(key);
return true;
}
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
if (cur->_key < key)
{
parent = cur;
cur = cur->_right;
}
else if (cur->_key > key)
{
parent = cur;
cur = cur->_left;
}
else return false;
}
Node* newNode = new Node(key);
if (parent->_key < key) parent->_right = newNode;
else parent->_left = newNode;
return true;
}注意，二叉搜索树是不允许有重复的元素的，所以会设计一个bool返回值，当遍历二叉树时，若是找到了与要插入的值相同的值，则不进行插入，并返回false
2.3 二叉搜索树的中序遍历
二叉搜索树也叫二叉排序树，正是因为二叉搜索树按照中序遍历打印出来后吗，是有序的
中序遍历是使用递归实现的，但是根节点是private的成员变量，外部没办法直接获取。此时有两种解决方法，第一种是在类中写一个函数GetRoot，第二种是写一个子函数，这里采用写子函数的方法
template<class K>
class BSTree
{
typedef BSTNode<K> Node;
public:
bool Find(const K& key)
{
Node* cur = _root;
while (cur) // 不为空时就继续找
{
if (cur->_key < key) cur = cur->_right;
else if (cur->_key > key) cur = cur->_left;
else return true; // 找到了返回true
}
return false; // 没找到返回false
}
bool Insert(const K& key)
{
// 判断根节点是否为空
if (_root == nullptr)
{
_root = new Node(key);
return true;
}
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
if (cur->_key < key)
{
parent = cur;
cur = cur->_right;
}
else if (cur->_key > key)
{
parent = cur;
cur = cur->_left;
}
else return false;
}
Node* newNode = new Node(key);
if (parent->_key < key) parent->_right = newNode;
else parent->_left = newNode;
return true;
}
void InOrder()
{
_InOrder(_root);
}
private:
void _InOrder(Node* _root)
{
if (_root == nullptr) return;
_InOrder(_root->_left);
cout << _root->_key << " ";
_InOrder(_root->_right);
}
Node* _root = nullptr;
};2.4 二叉搜索树的删除
首先，需要先找到需要删除的这个结点，所以函数需要有一个bool返回值，当找到了就进行删除操作，若没找到，则返回false。并且需要记录遍历到的位置的父亲结点
找到需要删除的结点后，会有3种情况：1. 要删除的结点没有孩子
2. 要删除的结点有1个孩子
3. 要删除的结点有2个孩子
此时我们会发现，这两种是可以合成为一种的。因为当我们找到要删除的结点后，如果这个结点有一个孩子是空，那么我们就是用另一个孩子去替换掉这个结点
bool Erase(const K& key)
{
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
if (cur->_key < key)
{
parent = cur;
cur = cur->_right;
}
else if (cur->_key > key)
{
parent = cur;
cur = cur->_left;
}
else // 此时已经找到了要删除的结点
{
// 要删除的结点只有一个孩子或者没有孩子,此时只需要把它的孩子给他的父亲结点
if (cur->_left == nullptr)
{
// 判断cur是父亲的左孩子还是右孩子
if (parent->_left == cur) parent->_left = cur->_right;
else parent->_right = cur->_right;
delete cur;
return true;
}
else if (cur->_right == nullptr)
{
if (parent->_left == cur) parent->_left = cur->_left;
else parent->_right = cur->_left;
delete cur;
return true;
}
// 要删除的结点有两个孩子
else
{
// 先去右子树中寻找值最小的结点，也就是右子树最左边的那个结点
Node* rightMin = cur->_right;
Node* rightMinP = nullptr;
while (rightMin->_left)
{
rightMinP = rightMin;
rightMin = rightMin->_left;
}
cur->_key = rightMin->_key;
rightMinP->_left = rightMin->_right;
delete rightMin;
return true;
}
}
}
return false;
}此时容易写出这样的代码，但是这是有问题的，问题在于处理要删除的结点有两个孩子时
问题1：我们将rightMinP初始化为空，如果我们要删除的结点是6，那么rightMin初始化就是7，不会进入循环，rightMinP仍然是空，后面还有解引用就会出错，也很容易发现，实际上要删除的结点激素rightMin的父节点，也就是rightMinP直接初始化为cur即可
问题2：我们将rightMin的值与cur替换后，此时需要将rightMin的孩子给其父节点，前面分析过了rightMin的孩子最多只有一个(因为左孩子一定为空)，上面的代码是直接将rightMin的右孩子给其父节点的左孩子，因为是找的cur的右子树最左边的结点，所以很容易就写成上面那样，这样是符合删除3的，但是对于删除6是不满足的，因为删除6并没有进去cur的右子树中一直往左边找，所以应该修改成判断一下rightMin在rightMinP的左边还是右边，然后将rightMin的右孩子替换到rightMin的位置
template<class K>
struct BSTNode // 二叉搜索树的结点
{
K _key;
BSTNode<K>* _left;
BSTNode<K>* _right;
BSTNode(const K& key)
:_key(key)
,_left(nullptr)
,_right(nullptr)
{}
};
template<class K>
class BSTree
{
typedef BSTNode<K> Node;
public:
bool Find(const K& key)
{
Node* cur = _root;
while (cur) // 不为空时就继续找
{
if (cur->_key < key) cur = cur->_right;
else if (cur->_key > key) cur = cur->_left;
else return true; // 找到了返回true
}
return false; // 没找到返回false
}
bool Insert(const K& key)
{
// 判断根节点是否为空
if (_root == nullptr)
{
_root = new Node(key);
return true;
}
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
if (cur->_key < key)
{
parent = cur;
cur = cur->_right;
}
else if (cur->_key > key)
{
parent = cur;
cur = cur->_left;
}
else return false;
}
Node* newNode = new Node(key);
if (parent->_key < key) parent->_right = newNode;
else parent->_left = newNode;
return true;
}
void InOrder()
{
_InOrder(_root);
}
bool Erase(const K& key)
{
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
if (cur->_key < key)
{
parent = cur;
cur = cur->_right;
}
else if (cur->_key > key)
{
parent = cur;
cur = cur->_left;
}
else // 此时已经找到了要删除的结点
{
// 要删除的结点只有一个孩子或者没有孩子,此时只需要把它的孩子给他的父亲结点
if (cur->_left == nullptr)
{
// 判断cur是父亲的左孩子还是右孩子
if (parent->_left == cur) parent->_left = cur->_right;
else parent->_right = cur->_right;
delete cur;
return true;
}
else if (cur->_right == nullptr)
{
if (parent->_left == cur) parent->_left = cur->_left;
else parent->_right = cur->_left;
delete cur;
return true;
}
// 要删除的结点有两个孩子
else
{
// 先去右子树中寻找值最小的结点，也就是右子树最左边的那个结点
Node* rightMin = cur->_right;
Node* rightMinP = cur;
while (rightMin->_left)
{
rightMinP = rightMin;
rightMin = rightMin->_left;
}
cur->_key = rightMin->_key;
if(rightMinP->_left == rightMin)
rightMinP->_left = rightMin->_right;
else
rightMinP->_right = rightMin->_right;
delete rightMin;
return true;
}
}
}
return false;
}
private:
void _InOrder(Node* _root)
{
if (_root == nullptr) return;
_InOrder(_root->_left);
cout << _root->_key << " ";
_InOrder(_root->_right);
}
Node* _root = nullptr;
};3、二叉搜索树的应用
3.1 K模型
K模型就是二叉搜索树的结点中只存放一个有效值
上面实现的就是K模型的二叉搜索树
K模型主要用来处理在不在的问题。如门禁系统，只需要判断一个人在不在门禁系统中。又如检查英文小说中是否有错误单词，只需要判断一个英文单词是否在词库中
3.2 KV模型
KV模型就是二叉搜索树的结点中存放两个有效值。每一个关键码key，都有与之对应的值value，即<key,value>的键值对
KV模型主要用来处理通过一个值(key)找另一个值(value)的问题。如简单词典、车库收费系统、统计单词出现的次数
对我们上面的二叉搜索树稍作修改，就能得到KV模型的二叉搜索树
1. 结点模板和类模板都增加一个模板参数
2. 插入结点时参数多一个value，不过比较时仍然用key比较
3. 查找时也只给key即可，不过现在需要返回的是结点的指针，因为找到了需要获取里面的值
4. 其余没有变化
KV模型的二叉搜索树仍然是不能有重复的key值的
template<class K,class V>
struct BSTNode_V // 二叉搜索树的结点
{
K _key;
V _value;
BSTNode_V<K,V>* _left;
BSTNode_V<K,V>* _right;
BSTNode_V(const K& key,const V& value)
:_key(key)
,_value(value)
, _left(nullptr)
, _right(nullptr)
{}
};
template<class K,class V>
class BSTree_V
{
typedef BSTNode_V<K,V> Node;
public:
Node* Find(const K& key)
{
Node* cur = _root;
while (cur) // 不为空时就继续找
{
if (cur->_key < key) cur = cur->_right;
else if (cur->_key > key) cur = cur->_left;
else return cur; // 找到了返回该结点的指针
}
return nullptr; // 没找到返回空
}
bool Insert(const K& key,const V& value)
{
// 判断根节点是否为空
if (_root == nullptr)
{
_root = new Node(key, value);
return true;
}
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
if (cur->_key < key)
{
parent = cur;
cur = cur->_right;
}
else if (cur->_key > key)
{
parent = cur;
cur = cur->_left;
}
else return false;
}
Node* newNode = new Node(key, value);
if (parent->_key < key) parent->_right = newNode;
else parent->_left = newNode;
return true;
}
void InOrder()
{
_InOrder(_root);
}
bool Erase(const K& key)
{
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
if (cur->_key < key)
{
parent = cur;
cur = cur->_right;
}
else if (cur->_key > key)
{
parent = cur;
cur = cur->_left;
}
else // 此时已经找到了要删除的结点
{
// 要删除的结点只有一个孩子或者没有孩子,此时只需要把它的孩子给他的父亲结点
if (cur->_left == nullptr)
{
// 判断cur是父亲的左孩子还是右孩子
if (parent->_left == cur) parent->_left = cur->_right;
else parent->_right = cur->_right;
delete cur;
return true;
}
else if (cur->_right == nullptr)
{
if (parent->_left == cur) parent->_left = cur->_left;
else parent->_right = cur->_left;
delete cur;
return true;
}
// 要删除的结点有两个孩子
else
{
// 先去右子树中寻找值最小的结点，也就是右子树最左边的那个结点
Node* rightMin = cur->_right;
Node* rightMinP = cur;
while (rightMin->_left)
{
rightMinP = rightMin;
rightMin = rightMin->_left;
}
cur->_key = rightMin->_key;
if (rightMinP->_left == rightMin)
rightMinP->_left = rightMin->_right;
else
rightMinP->_right = rightMin->_right;
delete rightMin;
return true;
}
}
}
return false;
}
private:
void _InOrder(Node* _root)
{
if (_root == nullptr) return;
_InOrder(_root->_left);
cout << _root->_key << "--" << _root->_value << " ";
_InOrder(_root->_right);
}
Node* _root = nullptr;
};利用KV模型实现一个简易的词典
void dictionary()
{
BSTree_V<string, string> dict;
dict.Insert("left", "左边");
dict.Insert("right", "右边");
dict.Insert("insert", "插入");
dict.Insert("string", "字符串");
string str;
while (cin >> str)
{
auto ret = dict.Find(str);
if (ret) cout << "->" << ret->_value << endl;
else cout << "无此单词，请重新输入" << endl;
}
}利用KV模型来记录每种水果的个数
4、二叉搜索树的性能分析
插入和删除操作都必须先查找，查找效率代表了二叉搜索树中各个操作的性能。
对有n个结点的二叉搜索树，若每个元素查找的概率相等，则二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数，即结点越深，则比较次数越多。
但对于同一个关键码集合，如果各关键码插入的次序不同，可能得到不同结构的二叉搜索树：
最优情况下，二叉搜索树为完全二叉树(或者接近完全二叉树)，其平均比较次数为：O(logN)
最差情况下，二叉搜索树退化为单支树(或者类似单支)，其平均比较次数为：O(N)
所以二叉搜索树并不是完美的，当其变成接近与单支树的情况时，时间复杂度是比较高的，所以引入的平衡二叉搜索树(AVL树和红黑树)。在内存中AVL树和红黑树已经够用了，但是在磁盘上仍然是不够的，所以又引入了B树家族
原文地址：https://blog.csdn.net/2301_80277275/article/details/140385368
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！