文章目录
- 前言
- 一、二叉搜索树的概念
- 定义
- 特点
- 二、二叉树的实现
- 基本框架
- 查找
- 插入
- 删除
- 当只有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;}}// 此时建立一个节点,将其地址赋值给curcur = 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树和红黑树已经在路上了!~