Cpp二叉搜索树的讲解与实现(21)

---

前言

这是全新的一个篇章呢，二叉搜索树是我们接下来学习set、map的前提
迈过它吧，关关难过关关过！

正文开始！

---

一、二叉搜索树的概念

定义

  二叉搜索树（Binary search tree）是基于二叉树的一种改进版本。因为 普通二叉树没有实际价值，无法进行插入、删除等操作（无意义），但二叉搜索树就不一样了，二叉搜索树对于数据的存储有严格要求：左节点比根小，右节点比根大

因此 二叉搜索树 的查找效率极高，具有一定的实际价值

  所以将数据存入 二叉搜索树 中进行查找时，理想情况下只需要花费 logN 的时间（二分思想）

  这就是 二叉搜索树 名字的由来，搜索（查找）速度很快

特点

  二叉树的基本特点：左比根小，右比根大

1. 若某个节点的 左 节点不为空，则 左 节点的值一定比当前节点的值 小，且其 左 子树的所有节点都比它 小
2. 若某个节点的 右 节点不为空，则 右 节点的值一定比当前节点的值 大，且其 右 子树的所有节点都比它 大
3. 二叉搜索树的每一个节点的 根、左 、右 都满足基本特点

另外，中序遍历的结果为升序

二、二叉树的实现

二叉搜索树的源代码

基本框架

  跟普通的二叉树一样，二叉搜索树也需要节点类，同时将节点指针作为二叉搜索树的成员变量

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;}}// 此时建立一个节点，将其地址赋值给curcur = new Node(key);// 此时需要根据值的大小来判断parent左链还是右链if (key > parent->_key)parent->_right = cur;else parent->_left = cur;return true;
}

删除

  删除可就复杂了，要考虑很多情况！

  我们发现如果我们要删除一个节点，并且在二叉搜索树中已经确定找到了该节点，可能有三种情况：

1. 该节点没有孩子，即要删除的是叶子节点
2. 该节点只有一个孩子，可能是左孩子为空，也有可能是有孩子为空
3. 该节点有两个孩子，这种情况比较复杂，要考虑比较复杂的情况

当只有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，判断该单词是否拼写正确，具体方式如下：

1. 以词库中所有单词集合中的每个单词作为key，构建一棵二叉搜索树
2. 在二叉搜索树中检索该单词是否存在，存在则拼写正确，不存在则拼写错误

KV模型

  每一个关键码key，都有与之对应的值Value，即<Key, Value>的键值对

  比如英汉词典就是英文与中文的对应关系，通过英文可以快速找到与其对应的中文，英文单词与其对应的中文<word, chinese>就构成一种键值对

  再比如统计单词次数，统计成功后，给定单词就可快速找到其出现的次数，单词与其出现次数就是<word, count>就构成一种键值对

KV模型也就是在K模型的基础上加上value的值，请试试吧！

四、二叉树的性能分析

  如果我问你二叉搜索树的查找时间复杂度为多少，你可能会不假思索的回答出是O(logN)，但是，假如我给一个递减数列呢，是不是就退化成单支树了？

  所以理想状态下是O(logN)，最坏情况下是O(N)

---

总结

  看了性能分析，你可能会想怎么让二叉树的性能达到最优？不急，AVL树和红黑树已经在路上了！~