⭐️博主： 此生决int-@CSDN博客
速胜派就是最大的投降派！！！
🔥热门专栏🔥
深入理解 C++ 系列 ｜ 算法系列
快速复习系列 ｜ Java 速通系列
文章目录
-
- 上期回顾
- 一. 二叉搜索树
-
- 1. 二叉搜索树的概念
-
- **2，为什么**我们要引入二叉搜索树？它的优势是什么？
- 2. 二叉搜索树的性能分析
-
- 关于搜索总结：
- 二叉搜索树的模拟实现
-
- 1. 插入insert
-
- 主播的实现代码：
- 需要注意的点：
- 2.查找find
-
- 主播的实现代码：
- 3. 二叉搜索树的删除⭐️⭐️⭐️⭐️⭐️
-
- 实现要点
-
- 1，左右都为空
- 2，左为空或者右为空
- 3，左右都有孩子最复杂（交换删除法）
- 主播的实现代码
- 4，主播在这次模拟实现时犯的几个错误：
-
- 其中，在实现删除函数接口时犯的错误：
- 7. 二叉搜索树 key 和 key/value 使用场景⭐️⭐️⭐️
-
- 7.3 key/value 二叉搜索树代码实现
- 下期预告
-
- map/set的使用
- 结语
上期回顾
上一篇我们主要学习了C++模版的一些进阶内容，学习了非类型模版参数，函数模版的特化，类模版的特化等等，相较于模版初阶的内容，模版进阶引入了更多的模版的一些知识，这些在我们接下来学习的STL里面都有非常多的应用，那么，今天就让我们开始学习进阶STL的第一节二叉搜搜树吧！可以回顾一下数据结构篇二叉树的相关知识，但是，这里采用的是链式结构哦！
一. 二叉搜索树
1. 二叉搜索树的概念
顾名思义，就是一颗主要用于搜索的特殊的二叉树，所以，它肯定具有二叉树的所有性质，我们这里的二叉树就不是用数组来模拟了，而是链式结构！ 与普通二叉树的区别就是它具有一下的性质：
2，为什么我们要引入二叉搜索树？它的优势是什么？
首先，我们想要一个可以快速频繁查找的结构，我们这后面学的数据结构主要就是围绕这一点来学习，那么我们之前学习了二分查找，也非常快，但是它要求数组，并且是有序的数组，这就导致了它的缺点很明显，数组会导致它的插入删除非常不方便， 所以，就设计了二叉搜索树这一个结构，那么，它的查找效率是多少呢？
2. 二叉搜索树的性能分析
最优情况下，二叉搜索树为完全二叉树（或者接近完全二叉树），其高度为：log_2 底N 最差情况下，二叉搜索树退化为单支树（或者类似单支），其高度为：N 所以综合而言二叉搜索树增删查改时间复杂度为：O(N)
那么这样的效率显然是无法满足我们需求的，我们后续课程需要继续讲解二叉搜索树的变形，平衡二叉搜索树 AVL 树和红黑树，才能适用于我们在内存中存储和搜索数据。
关于搜索总结：
1，二分查找——效率logN，但是有两大缺陷：
2，二叉搜索树——N 插入删除方便，优化后，可以达到logN 优化后的结构：AVL树，红黑树等 3，哈希表——O（1） 
二叉搜索树的模拟实现
接下来，我们来模拟实现一个最普通的二叉搜索树的一些关键接口函数，主要是删除接口函数的实现，是本文的重点。
1. 插入insert
插入的具体过程如下：
主播的实现代码：
// 插入，判断插入是否成功即可
bool Insert(const K& key)
{
Node* newnode = new Node(key);
if (_root == nullptr)
{
_root = newnode;
return true;
}
//肯定要先找到你要插入的位置，肯定是插入到叶子节点
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
parent = cur;
//if (key < cur->_key)保证parent和cur是链接起来的
if (key < parent->_key)
{
cur = parent->_left;
}
else if (key > parent->_key)
{
cur = parent->_right;
}
else
{
//return false;防止内存泄露
delete newnode;
return false;
}
}
//找到了插入位置
//cur = newnode;
if (key < parent->_key)parent->_left = newnode;
if (key > parent->_key)parent->_right = newnode;
return true;
}
需要注意的点：
记得delete 节点
2.查找find
过程：
主播的实现代码：
// 查找,找到在不在即可
bool Find(const K& key)
{
if (_root == nullptr)return false;
Node* cur = _root;
while (cur)
{
if (key < cur->_key)
cur = cur->_left;
else if (key > cur->_key)
cur = cur->_right;
else return true;
}
return false;
}
3. 二叉搜索树的删除⭐️⭐️⭐️⭐️⭐️
醋包饺，这节最有价值的就是这个删除，最重要的也是这个删除！
实现要点
首先查找要删除的元素是否在二叉搜索树中，如果不存在，直接返回 false。
如果查找元素存在则分以下四种情况分别处理：（假设要删除的结点为 N）
其中，我们实现的时候大体可以分为两种情况： 1，N有两个孩子 2，其他 但是，2，其他这种情况更简单处理， 对于2，其他，我们只需要N的父母的指向N的指针指向N的左右里面的一个非空指针即可，如果左右都为空，那就自己指向空 对于1，我们采用了一种十分巧妙的方式：替换删除法，即找到一个可以接替N位置的节点X，把X的值给N，然后，删除X即可。 这里有一个二叉搜索树的性质： 可以接替N的节点要么是N的左子树的最大节点，要么是N右子树的最小节点 其中，N左子树的最大节点就是左子树的最右节点，N右子树的最小节点，就是右子树的最左节点。
1，左右都为空
2，左为空或者右为空
3，左右都有孩子最复杂（交换删除法）
主播的实现代码
// 删除
bool Erase(const K& key)
{
if (_root == nullptr)return false;
//根节点单独处理
if (_root->_key == key)
{
if (_root->_left == nullptr)
{
Node* tmp = _root;
_root = _root->_right;
delete tmp;
return true;
}
else if (_root->_right == nullptr)
{
Node* tmp = _root;
_root = _root->_left;
delete tmp;
return true;
}
}
//难点
//先找到要删除的节点的位置，
//节点位置有两种情况，
//1，至少有一边没有孩子，那么就把另一边链接给父亲即可
// 2，该节点左右都有孩子——交换删除法
//先找到该节点
Node* targetnode = nullptr;
Node* cur = _root;
//Node* curparent = nullptr;//非常关键啊
//Node* curparent = cur;//非常关键啊
//while (cur)
//{
//curparent = cur;
//if (key < cur->_key)
//cur = cur->_left;
//else if (key > cur->_key)
//cur = cur->_right;
//else
//{
//targetnode = cur;
//break;
//}
//}
//没有判断是否找到！
Node* curparent = cur;
while (cur)
{
if (key < cur->_key)
{
curparent = cur;
cur = cur->_left;
}
else if (key > cur->_key)
{
curparent = cur;
cur = cur->_right;
}
else
{
targetnode = cur;
break;
}
}
//if (targetnode != cur)return false;不能这么写
if (targetnode ==nullptr)return false;
//先处理第一种情况;
/*if (curparent->_left == targetnode)
{
if (targetnode->_left == nullptr)
curparent->_left = targetnode->_right;
else
curparent->_left = targetnode->_left;
}不能这么写*/
if (targetnode->_left == nullptr)
{
if (curparent->_left == targetnode)
{
curparent->_left = targetnode->_right;
}
else
curparent->_right = targetnode->_right;
delete targetnode;
return true;
}
else if(targetnode->_right==nullptr)
{
if (curparent->_left == targetnode)
{
curparent->_left = targetnode->_left;
}
else
curparent->_right = targetnode->_left;
delete targetnode;
return true;
}
else //左右都不为空，第二种情况
{
//找到左边最大的那个节点或者右边最小的节点
//左边最大也就是左边最靠右的节点，
//右边最小，也就是右边最靠左的节点
//我这里找右子树里面最靠左的节点
//Node* swapnode = targetnode;
Node* swapnode = targetnode->_right;
Node* swapnodeparent = swapnode;
while (swapnode->_left)
{
swapnodeparent = swapnode;
swapnode = swapnode->_left;
}
//找到了，先赋值
targetnode->_key = swapnode->_key;
//删除
//swapnodeparent->_left = swapnode->_right;
//虽然是去右子树里面找最左边的节点，但是不要以为全都是往左走所以swapnode一定是他父母的左节点，有一个特殊情况，就是，第一步，第一步他去右子树里面找，他就是先往右走
if (swapnodeparent->_left == swapnode)
swapnodeparent->_left = swapnode->_right;
else//swapnodeparent.right==swapnode
swapnodeparent->_right = swapnode->_right;
delete swapnode;
return true;
}
}
4，主播在这次模拟实现时犯的几个错误：
1，修改局部指针 ≠ 修改树结构 记住：改变局部指针，只改变变量；改变节点成员指针，才改变数据结构 2，父节点的移动要和子节点的移动同时进行
其中，在实现删除函数接口时犯的错误：
⭐ 第一：父节点必须在 cur 移动之前保存。 ⭐ 第二：找右子树最小节点时，虽然搜索路径是“向左”，但它第一次可能是从父节点向右走，所以替代节点不一定是父节点左孩子。 ⭐️ 第三：第二种情况要特别注意N有两个孩子，删除N时去右子树找最左边的那个孩子的时候找到的是N的右孩子的情况！，所以，这里要把swapnode的parent设为N.
7. 二叉搜索树 key 和 key/value 使用场景⭐️⭐️⭐️
这里我们就要介绍两种二叉搜索树的使用场景，也可以说是两种不同的二叉搜索树， 一种是key搜索场景，即，传入一个key，判断里面有没有即可，就是我们的后面要学习的set 还有一种是key/value搜索场景，即，每一个key都有一个value和这个key绑定！就是我们后面要学习的map 我们刚刚实现的就是key场景的二叉搜索树,我们接下来就来实现key/value的二叉搜索树，
7.3 key/value 二叉搜索树代码实现
其实非常简单，就是在刚刚的基础上，在Node节点里面多存入一个值value即可, 注意：其中的eraser和find是不用加value的，因为与他无关
template<class K, class V>
struct BSTNode
{
// pair<K, V> _kv;
K _key;
V _value;
BSTNode<K, V>* _left;
BSTNode<K, V>* _right;
BSTNode(const K& key, const V& value)
:_key(key)
, _value(value)
, _left(nullptr)
, _right(nullptr)
{}
};
template<class K, class V>
class BSTree
{
typedef BSTNode<K, V> Node;
public:
...
bool Insert(const K& key, const V& value)
{
...
}
.......
Node* Find(const K& key);
bool Erase(const K& key);
private:
Node* _root = nullptr;
};
下期预告
map/set的使用
结语
本文到此结束，感谢大家的阅读！如果觉得本文对你有所帮助，欢迎点赞、收藏、关注，也欢迎在评论区一起交流讨论。 也欢迎订阅我的 深入理解 C++系列：从语法入门到底层原理，系统掌握现代 C++ 算法系列：从入门到精通，蓝桥杯、ACM、LeetCode 与面试算法全路线 快速复习系列：知识梳理、查漏补缺，考前冲刺必备 Java 速通系列：已学 C 语言，快速上手 Java，轻松备战期末考试
愿每一次敲下键盘，都比昨天更进一步！
愿每一行代码落下，都让未来多一种可能！
