目录
前言
哈喽，小伙伴们大家好。今天我来给大家介绍一种新的二叉树结构——搜索二叉树。搜索二叉树是后面学习AVL树和红黑树的基础，学好它对于后面学习一些复杂的数据结构很有帮助。那么事不宜迟，我们赶快开始吧。
一、二叉搜索树概念
二叉搜索树又称二叉排序树，它或者是一棵空树，或者遵循以下特征：
- 如果它的左子树不为空，则左子树上节点的所有值都要小于根节点。
- 如果它的右子树不为空，则右子树上节点的所有制都要大于根节点。
- 左右子树也同样是二叉搜索树。
- 二叉搜索树中的节点不能有相同的值。
二叉树节点代码如下：
template<class T>
struct BSTreeNode
{
BSTreeNode(const T& key)
:_left(nullptr)
,_right(nullptr)
,_key(key)
{
}
BSTreeNode<T>* _left;
BSTreeNode<T>* _right;
T _key;
};二、二叉搜索树的操作
1、查找
- 从根开始比较，查找，比根大则往右边走查找，比根小则往左边走查找。
- 最多查找高度次，走到到空，还没找到，这个值不存在。
代码如下：
Node* find(const T& key)
{
Node* cur = _root;
while (cur)
{
if (key < cur->_key)
{
cur = cur->_left;
}
else if (key > cur->_key)
{
cur = cur->right;
}
else
{
return cur;
}
}
}2、插入
2.1插入非递归实现
- 树为空，则直接插入节点，赋值给root指针。
- 树不为空，则根据要插入节点数值的大小，依靠搜索二叉树的特性找到合适的位置插入。
代码如下：
bool insert(const T& key)
{
if (_root == nullptr)
{
_root = new Node(key);
return true;
}
else
{
Node*temp=new Node(key);
Node* cur = _root;
Node* parent = cur;
//去找合适的插入位置，直到遇到空截至
while (cur)
{
parent = cur;//把上一个节点保存起来，方便找到空后连接
if (key < cur->_key)
{
cur = cur->_left;
}
else if (key > cur->_key)
{
cur = cur->_right;
}
else
{
return false;//不允许相同大小的数出现
}
}
if (key < parent->_key)
{
parent->_left = temp;
}
else
{
parent->_right = temp;
}
return true;
}
}2.2插入递归实现
递归实现可以有效地简化代码，这里用到一个很巧妙的思想，root用引用传参，直接传递了父节点的左右指针，和非递归实现相比更加简洁，不需要再新加一个prev记录。
代码如下：
//root用引用传参，相当于root是上一个节点的左右指针，直接指向要插入的节点即可
bool _insertR(Node*& root, const T& key)
{
if (root == NULL)
{
root = new Node(key);
return true;
}
if (key < root->_key)
{
return _insertR(root->_left,key);
}
else if (key > root->_key)
{
return _insertR(root->_right,key);
}
else
{
return false;
}
}
//插入递归实现，由于用户不能拿到_root，所以这里需要嵌套实现
bool insertR(const T& key)
{
return _insertR(_root,key);
}3、删除
3.1删除非递归实现
搜索二叉树的删除有些复杂，可以分为以下三种情况：
a. 要删除的节点的左右子节点都为空。
b. 要删除节点的左右子节点有一个为空。
c. 要删除节点的左右子节点都不为空。
其中a和b可以合并为一种情况，这种情况直接删除该节点，然后让父节点直接继承子节点即可。
c情况比较麻烦，不能直接删除该节点，否则会造成整个树的结构错乱。 这时候我们可以采用替换法，根据大小关系找到一个可以顶替要删除节点位置的节点，这个节点一般是左树的最右节点或有树的最左节点，把它和要删除的节点位置进行交换，要删除的节点就成了叶子节点或者只有一个节点，此时再删除它就回归到了第一种情况，再递归一次即可。
代码如下：
bool erase(const T& key)
{
//先找到传进来的值，由于需要保存父节点，所以不能使用find函数
Node* cur = _root;
Node* parent = cur;
while (cur)
{
if (key < cur->_key)
{
parent = cur;
cur = cur->_left;
}
else if (key > cur->_key)
{
parent = cur;
cur = cur->_right;
}
else
{
//找到了，开始删除。
//情况1，左为空或右为空或都为空，直接删除，把子节点交给父节点收养
if (cur->_left == nullptr)
{
//先判断要删的是不是根节点，如果是根节点需要把根节点位置转移
if (cur == _root)
{
_root = cur->_right;
}
else
{
if (parent->_left == cur)
{
parent->_left = cur->_right;
}
else
{
parent->_right = cur->_right;
}
}
delete cur;
}
else if (cur->_right == nullptr)
{
if (cur == _root)
{
_root = cur->_right;
}
else
{
if (parent->_left == cur)
{
parent->_left = cur->_left;
}
else
{
parent->_right = cur->_left;
}
}
delete cur;
}
//情况2，左右都不为空。
//把找到的节点当成根节点，从左边找最右或者从右边找最左，替换根节点
else
{
//从右边找最左
Node* midleft = cur->_right;
while (midleft->_left)
{
midleft = midleft->_left;
}
//保存最左节点的值
T min = midleft->_key;
//递归删除最左节点
erase(min);
cur->_key = min;
}
return true;
}
}
return false;
}3.2、删除递归实现
和非递归相比，第一种情况稍微简化了一点，不需要再用prev指针记录父节点。第二种情况进行交换后再递归调用删除函数即可。
bool _eraseR(Node*& root, const T& key)
{
if (root == nullptr)
{
return false;
}
if (key < root->_key)
{
return _eraseR(root->_left, key);
}
else if (key > root->_key)
{
return _eraseR(root->_right, key);
}
else
{
//找到了，开始删除
//情况1，左右至少有一个为空
if (root->_left == nullptr)
{
Node* temp = root;
root = root->_right;
delete temp;
}
else if (root->_right == nullptr)
{
Node* temp = root;
root = root->_left;
delete temp;
}
//情况2，左右都不为空
else
{
//从右边找最左值
Node* minright = root->_right;
while (minright->_left)
{
minright = minright->_left;
}
T min = minright->_key;
//把最左值删了之后再用它代替根
_eraseR(root->_right, min);//这里必须传root->_right，不能传minright，否则构不成引用
root->_key = min;
}
return true;
}
//删除递归实现
bool eraseR(const T& key)
{
return _eraseR(_root, key);
}三、二叉搜索树的应用
1. K模型
K模型即只有key作为关键码，结构中只需要存储Key即可，关键码即为需要搜索到的值。
比如：给一个单词word，判断该单词是否拼写正确，具体方式如下：
- 以词库中所有单词集合中的每个单词作为key，构建一棵二叉搜索树
- 在二叉搜索树中检索该单词是否存在，存在则拼写正确，不存在则拼写错误。
2. KV模型
每一个关键码key，都有与之对应的值Value，即<Key, Value>的键值对。该种方式在现实生活中非常常见：
- 比如英汉词典就是英文与中文的对应关系，通过英文可以快速找到与其对应的中文，英文单词与其对应的中文<word, chinese>就构成一种键值对。
- 再比如统计单词次数，统计成功后，给定单词就可快速找到其出现的次数，单词与其出现次数就是<word, count>就构成一种键值对。
四、二叉搜索树的性能分析
二叉搜索树查找，插入，删除一般都要进行高度次，在一般情况下时间复杂度是O(logN)。但是时间复杂度要考虑最坏情况，当二叉树内所有节点的节点都只有一个时，就会近似成一条线，此时高度等于元素个数，时间复杂度为O(N)。
当二叉搜索树退化为单支树或类似单支树时，其性能就失去了，所以我们需要学习更高级的树。
总结
本章主要讲解了二叉搜索树的原理和实现，搜索二叉树虽然在一定程度上加快了搜素效率，但其仍存在缺陷（当为单支时），而之后的AVL树和红黑树就很好的解决了这一问题，在后续文章中我将进行介绍。今天的内容就到这里啦，感谢阅读。山高路远，来日方长，我们下次见~