文章目录
- 前言
- 一、二叉搜索树的概念
- 定义
- 特点
- 二、二叉树的实现
- 基本框架
- 查找
- 插入
- 删除
- 当只有0 ~ 1个孩子的时候
- 当有2个孩子的时候
- 三、二叉树的应用
- K模型
- KV模型
- 四、二叉树的性能分析
- 总结
前言
这是全新的一个篇章呢，二叉搜索树是我们接下来学习set、map的前提
迈过它吧，关关难过关关过！
正文开始！
一、二叉搜索树的概念
定义
二叉搜索树（Binary search tree）是基于二叉树的一种改进版本。因为 普通二叉树没有实际价值，无法进行插入、删除等操作（无意义），但二叉搜索树就不一样了，二叉搜索树对于数据的存储有严格要求：左节点比根小，右节点比根大
因此 二叉搜索树 的查找效率极高，具有一定的实际价值
所以将数据存入 二叉搜索树 中进行查找时，理想情况下只需要花费 logN 的时间（二分思想）
这就是 二叉搜索树 名字的由来，搜索（查找）速度很快
特点
二叉树的基本特点：左比根小，右比根大
- 若某个节点的 左 节点不为空，则 左 节点的值一定比当前节点的值 小，且其 左 子树的所有节点都比它 小
- 若某个节点的 右 节点不为空，则 右 节点的值一定比当前节点的值 大，且其 右 子树的所有节点都比它 大
- 二叉搜索树的每一个节点的 根、左 、右 都满足基本特点
另外，中序遍历的结果为升序
二、二叉树的实现
二叉搜索树的源代码
基本框架
跟普通的二叉树一样，二叉搜索树也需要节点类，同时将节点指针作为二叉搜索树的成员变量
template <class K>
struct BSTNode
{
K _key;
BSTNode<K>* _left;
BSTNode<K>* _right;
BSTNode(const K& key = K())
:_key(key)
,_left(nullptr)
,_right(nullptr)
{}
};
template <class K>
class BSTree
{
typedef BSTNode<K> Node;
public:
BSTree()
:_root(nullptr)
{}
private:
Node* _root;
};
查找
得益于二叉搜索树的特性，我们可以比较插入数字和当前节点的值，当比当前节点大的时候的时候往右走，反之则往左，若 cur 为空，那么返回 false ，若找到，则返回 true
bool Find(const K& key)
{
Node* cur = _root;
while (cur) {
if (key > cur->_key)
cur = cur->_right;
else if (key < cur->_key)
cur = cur->_left;
else return true;
}
return false;
}
插入
插入其实过程和查找差不多，只不过如果中途找到了就返回 false 表示二叉搜索树中已经有该数字，如果成功走到空了就开始插入
只不过我们需要注意，当搜索树为空树的时候，我们必须新建立一个节点，将指针赋给这个根节点，另外，我们需要申请一个指针变量 parent 来记录父节点，方便后续链接
bool Insert(const K& key)
{
// 如果为空树，则直接建立一个节点
// 将其地址存放在_root上
if (_root == nullptr)
{
_root = new Node(key);
return true;
}
Node* parent = nullptr;
Node* cur = _root;
// 一直循环到cur为空
while (cur) {
if (key > cur->_key) {
parent = cur;
cur = cur->_right;
}
else if (key < cur->_key) {
parent = cur;
cur = cur->_left;
}
else {
// 如果中途发现BS树已有key，则插入失败
// BS树中没有重复元素，依据定义
return false;
}
}
// 此时建立一个节点，将其地址赋值给cur
cur = new Node(key);
// 此时需要根据值的大小来判断parent左链还是右链
if (key > parent->_key)
parent->_right = cur;
else parent->_left = cur;
return true;
}
删除
删除可就复杂了，要考虑很多情况！
我们发现如果我们要删除一个节点，并且在二叉搜索树中已经确定找到了该节点，可能有三种情况：
- 该节点没有孩子，即要删除的是叶子节点
- 该节点只有一个孩子，可能是左孩子为空，也有可能是有孩子为空
- 该节点有两个孩子，这种情况比较复杂，要考虑比较复杂的情况
当只有0 ~ 1个孩子的时候
我们先来看第二种情况，当找到要删除的节点且该节点只有一个孩子后，此时显然父节点链上当前节点的子节点就可以了，这样不会破坏二叉搜索树的结构
二叉搜索树的右子树的值一定大于该节点的值，同样的，左子树的值一定小于该节点的值
于是，我们就想着再销毁当前节点之前，先判断是父节点的左边链接还是右边链接，这很简单，我们检查一下 parent 左右指针哪个指向 cur 就行，同时，我们也要思考一下子节点与 cur 的链接关系，很简单，这也是直接判断一下就可以
其实，这种方法囊括了第一第二种情况，你可以思考一下为什么
// 如果左孩子为空
// 这时候就要parent就要链到cur的右边去
if (cur->_left == nullptr) {
if (parent->_left == cur)
parent->_left = cur->_right;
else parent->_right = cur->_right;
// 删除
delete cur;
cur = nullptr;
return true;
}
// 如果右孩子为空
// 这时候就要parent就要链到cur的左边去
else if (cur->_right == nullptr) {
if (parent->_left == cur)
parent->_left = cur->_left;
else parent->_right = cur->_left;
// 删除
delete cur;
cur = nullptr;
return true;
}
右子树为空
左子树为空
当有2个孩子的时候
当左右孩子节点都不为空的时候，我们也要想想，万一把 cur 给删掉了，要换那一个替上来？
关于这个问题，我们还是要把握二叉搜索树的一个核心特性，就是左子树所有节点的值一定比根节点小，右子树所有节点的值一定比根节点大
那么只要将左子树最大的值和右子树最小的值找到，此时我们又要想，将两个其中之一的值替代父节点的值即可，然后再销毁节点，那么这样会不会破坏二叉树的结构呢？
显然不会，只要能正确销毁并正确链接，那么就没关系，在这里我们选择找到右子树的最小值，这很简单，因为一个二叉搜索树的最小值就是最左边那个，那么我们同样用 rightMin 标记右子树的最小节点 ，用 rightMinP 标记其父节点，又为了防止 rightMinP 进不去循环，我们给 rightMinP 赋值 cur
Node* rightMinP = cur;
Node* rightMin = cur->_right;
// 找到右子树的最小节点
while (rightMin->_left) {
rightMinP = rightMin;
rightMin = rightMin->_left;
}
// 替代，这时候转换成就要删除rightMin这个节点了
// 这个时候就需要有它的父亲
cur->_key = rightMin->_key;
// 因为rightMin必然是最左节点
// 所以rightMinP必然是链接rightMin的右孩子
// 同时rightMinP是左链还是右链这不确定，需要判断一下
if (rightMinP->_left == rightMin)
rightMinP->_left = rightMin->_right;
else rightMinP->_right = rightMin->_right;
delete rightMin;
rightMin = nullptr;
return true;
但是但是！！我们发现写到这里后，当删到最后只剩几个节点之后，报错了！
我们再回看代码，发现我们的逻辑是先找到删除节点，再用父亲节点去链接当前节点的子节点，关键是，有没有可能一开始我们就找到了要删除的节点，父亲节点没进循环，也就是说，没有父亲节点，这很不好，针对这种情况，我们就要移动根节点
if (parent == nullptr) {
_root = _root->_right;
delete cur;
cur = nullptr;
return true;
}
三、二叉树的应用
K模型
K模型即只有key作为关键码，结构中只需要存储Key即可，关键码即为需要搜索到的值。
我们上述代码实现的也就是这种
举个例子，给一个单词word，判断该单词是否拼写正确，具体方式如下：
- 以词库中所有单词集合中的每个单词作为key，构建一棵二叉搜索树
- 在二叉搜索树中检索该单词是否存在，存在则拼写正确，不存在则拼写错误
KV模型
每一个关键码key，都有与之对应的值Value，即<Key, Value>的键值对
比如英汉词典就是英文与中文的对应关系，通过英文可以快速找到与其对应的中文，英文单词与其对应的中文<word, chinese>就构成一种键值对
再比如统计单词次数，统计成功后，给定单词就可快速找到其出现的次数，单词与其出现次数就是<word, count>就构成一种键值对
KV模型也就是在K模型的基础上加上value的值，请试试吧！
四、二叉树的性能分析
如果我问你二叉搜索树的查找时间复杂度为多少，你可能会不假思索的回答出是O(logN)，但是，假如我给一个递减数列呢，是不是就退化成单支树了？
所以理想状态下是O(logN)，最坏情况下是O(N)
总结
看了性能分析，你可能会想怎么让二叉树的性能达到最优？不急，AVL树和红黑树已经在路上了！~
