【C++篇】二叉树进阶：二叉搜索树
前言
本文我们补充二叉树的知识——二叉搜索树。在之前学习初阶数据结构时，我们还留下了这部分知识没有讲解，具体原因是由于C语言的限制，会大大增大我们的学习成本，因此，在学会C++后学习会事半功倍。
1. 二叉搜索树的概念
二叉搜索树又称二叉排序树，它可以是一颗空树。 它是具有以下性质的二叉树： 如果树不为空时：
- 非空左子树的所有节点的值小于其根节点的值。
- 非空左子树的所有节点的值小于其根节点的值。
- 左右子树都是二叉搜索树
- 节点的值都是唯一的，不存在相等值的两个节点
为什么又可以叫二叉排序树呢？ 因为二叉搜索树的中序遍历的结果一定是一个升序序列
那么，二叉搜索树应该是链式结构还是顺序结构呢？ 其实很容易想到，这棵树需要具备增删的功能，若是顺序结构，每次都得挪动数据，效率太差。 因此，二叉搜索树是链式结构。
2. 二叉搜索树的操作及模拟实现
这里操作的实现可以有两种方式：递归和非递归（迭代）。这里我们两者一起实现。
2.1 查找
- 从根开始比较，查找，比根大则往右边走查找，比根小则往左边走查找。
- 最多查找高度次，走到到空，还没找到，这个值不存在。
非递归：
bool Find(const K& key)
{
Node* cur = _root;
while (cur)
{
if (cur->_key > key)//比根小就往左走
{
cur = cur->_left;
}
else if (cur->_key < key)//比根大就往右走
{
cur = cur->_right;
}
else//与根相等就找到了
{
return true;
}
}
return false;
}递归：
bool _FindR(Node* root, const K& key)
{
if (root == nullptr)
{
return false;
}
if (root->_key > key)//比根小了,就在左子树上查找
{
_FindR(root->_left, key);
}
else if (root->_key < key)//比根大了,就在右子树上查找
{
_FindR(root->_right, key);
}
else
{
return true;
}
}2.2 插入
插入的具体过程分两种情况： a. 树为空，则直接新增节点，赋值给root指针 b. 树不空，按二叉搜索树性质查找插入位置，插入新节点
如果有重复的节点，则插入失败，返回false。
非递归：
bool Insert(const K& key)
{
Node* cur = _root;
Node* parent = nullptr;
if (_root == nullptr)
{
_root = new Node(key);
return true;
}
else
{
//查找插入的位置
while (cur)
{
if (cur->_key > key)
{
parent = cur;
cur = cur->_left;
}
else if (cur->_key < key)
{
parent = cur;
cur = cur->_right;
}
else
{
return false;
}
}
//插入
cur = new Node(key);
if (parent->_key > key)
{
parent->_left = cur;
}
else
{
parent->_right = cur;
}
return true;
}
}递归：
- 小于根节点，化子问题为在左子树插入
- 大于根节点，化子问题为在右子树插入
设计参数：
bool _InsertR(Node*& root, const K& key)这里root参数巧用&引用，可以达到效果是：递归的每层root都是同一个，以达到每一层递归都是作用在一颗树上。 后面的删除也是如此。
bool _InsertR(Node*& root, const K& key)
{
if (root == nullptr)
{
root = new Node(key);
return true;
}
if (root->_key > key)
{
_InsertR(root->_left, key);
}
else if (root->_key < key)
{
_InsertR(root->_right, key);
}
else
{
return false;
}
}2.3 删除
删除就比较复杂了，情况分为：
- 删除的节点没有孩子，也就是叶子节点，直接删即可。
- 删除的节点有一个孩子，将这个孩子交给父亲，也就是托孤。注意区分左右孩子。
- 删除的节点有两个孩子，替换法，将其与左子树最大的节点或右子树最小的节点进行替换，转换为一个孩子或两个孩子的节点进行删除。 求法： 左子树最大节点——左子树的最右节点； 右子树最小节点——右子树的最左节点。
还有一个很容易疏忽的一个情况：LeftMax存在左孩子的情况 删除8：
如果替换后直接删除的话，LeftMax的左孩子就丢失了，因此这里需要托孤。
if (parent->_left == LeftMax)
{
parent->_left = LeftMax->_left;
}
else
{
parent->_right = LeftMax->_left;
}完整代码（非递归）：
bool Erase(const K& key)
{
Node* cur = _root;
Node* parent = nullptr;
while (cur)
{
if (cur->_key > key)
{
parent = cur;
cur = cur->_left;
}
else if (cur->_key < key)
{
parent = cur;
cur = cur->_right;
}
else
{
//左为空
if (cur->_left == nullptr)
{
if (cur == _root)
{
_root = cur->_left;
}
else
{
if (parent->_left == cur)
{
parent->_left = cur->_left;
}
else
{
parent->_right = cur->_left;
}
}
}
//右为空
else if (cur->_right == nullptr)
{
if (cur == _root)
{
_root = cur->_right;
}
else
{
if (parent->_right == cur)
{
parent->_right = cur->_right;
}
else
{
parent->_left = cur->_right;
}
}
}
//左右都不为空
else
{
Node* LeftMax = cur->_left;
parent = cur;
//找最右节点
while (LeftMax->_right)
{
parent = LeftMax;
LeftMax = LeftMax->_right;
}
swap(cur->_key, LeftMax->_key);
//处理LeftMax存在左孩子的情况
if (parent->_left == LeftMax)
{
parent->_left = LeftMax->_left;
}
else
{
parent->_right = LeftMax->_left;
}
cur = LeftMax;
}
delete cur;
return true;
}
}
return false;
}递归：
- 小于根节点，化子问题为在左子树删除
- 大于根节点，化子问题为在右子树删除
- 等于根节点，进行删除操作（同上） 好处是无需控制父节点了，也避免了许多复杂的情况。
bool _EraseR(Node*& root, const K& key)
{
if (root == nullptr)
{
return false;
}
if (root->_key > key)
{
return _EraseR(root->_left, key);
}
else if (root->_key < key)
{
return _EraseR(root->_right, key);
}
else
{
Node* del = root;
//左为空
if (root->_left == nullptr)
{
root = root->_right;
}
//右为空
else if (root->_right == nullptr)
{
root = root->_left;
}
//右两个孩子：转化为一个或没有孩子的问题
else
{
Node* LeftMax = root->_left;
while (LeftMax->_right)
{
LeftMax = LeftMax->_right;
}
swap(root->_key, LeftMax->_key);
return _EraseR(root->_left, key);
}
delete del;
return true;
}
}
Node* _root;
};3. 二叉搜索树的应用
3.1 K模型（Key）
K模型即只有key作为关键码，结构中只需要存储Key即可，关键码即为需要搜索到的值。 应用场景案例： 给一个单词word，判断该单词是否拼写正确 具体方式如下：
- 以词库中所有单词集合中的每个单词作为key，构建一棵二叉搜索树
- 在二叉搜索树中检索该单词是否存在，存在则拼写正确，不存在则拼写错误。
3.2 KV模型（Key_Value）
每一个关键码key，都有与之对应的值Value，即<Key, Value>的键值对。 这种模型在现实生活中更为常见：
- 英汉词典就是英文与中文的对应关系 通过英文可以快速找到与其对应的中文，英文单词与其对应的中文<word, chinese>就构成一种键值对；
- 统计单词次数，统计成功后，给定单词就可快速找到其出现的次数 单词与其出现次数就是<word, count>就构成一种键值对。
4. 二叉搜索树查找的时间复杂度分析
二叉搜索树的操作都用到了查找 那对于查找，它的时间复杂度是多少呢？
对有n个结点的二叉搜索树，若每个元素查找的概率相等，则二叉搜索树平均查找长度是结点在树的深度。 但二叉搜索树为完全二叉树时就是最好的情况了，查找的时间复杂度为
但是，时间复杂度计算的最坏情况，并非平均。我们需要寻找极端情况。
极端情况：
这种趋于线性的二叉搜索树，查找的时间复杂是
。
那能不能将此类情况优化呢？？
有的有的，后继我们将要学习的AVL树、红黑树，它们的最多查找次数就是树的高度次，敬请期待吧！
腾讯云开发者
