`
文章目录
- 前言
- 一、搜索二叉树介绍
- 二、二叉搜索树实现
- 1.查找
- 2.插入
- 3.删除
- 三、二叉搜索树递归实现
- 1.查找
- 2.插入
- 3.删除
- 四、二叉搜索树性能分析
- 五、二叉搜索树应用
- 1.K模型
- 2.KV模型
- 总结
前言
在本篇文章中，我们将会学到数据结构中有关二叉树中一种特殊的结构-----搜索二叉树，它的主要目的就是为了搜索，我们还将会对搜索二叉树进行模拟实现。
一、搜索二叉树介绍
二叉树我们都已经学习过了，二叉搜索树就是对普通二叉树进行一些限制，有一些新的功能。
二叉搜索树又称二叉排序树，二叉查找树
如果它的左子树不为空，则左子树上所有结点的值都小于根节点的值。
如果它的右子树不为空，则右子树上所有结点的值都大于根节点的值。
左右子树也分别是一颗二叉搜索树
我们来看几个二叉树是不是二叉搜索树
这个就是一个二叉搜索树
这个就不是一个二叉搜索树，对于10这个节点，右节点的值必须大于这个10
性质：二叉搜索树中序遍历是一个递增序列
二、二叉搜索树实现
普通的数据结构就是增删查改，但是在二叉搜索树是不允许修改的。对于存储重复值也无意义。
我们先看一下二叉搜索树框架结构
template<class K>
struct TreeeNode
{
TreeeNode(const K& val)
:_left(nullptr)
,_right(nullptr)
,_val(val)
{}
struct TreeeNode* _left;
struct TreeeNode* _right;
K _val;
};
template<class K>
class BSTree
{
public:
//功能实现
private:
typedef TreeeNode<K> Node;
Node* _root=nullptr;
};
1.查找
我们利用二叉搜索树的性质查找，从根开始查找，进行一次遍历。
如果这个值比根节点大，我们就去右边查找。
如果这个值比根节点小，我们就去左边查找。
如果最后走到空，还没有找到，就说明这个值不存在。
bool find(const K& val)
{
Node* cur = _root;
while (cur)
{
if (cur->_val > val)
{
cur = cur->_left;
}
else if (cur->_val < val)
{
cur = cur->_right;
}
//相等不插入
else
{
return true;
}
}
return false;
}
2.插入
插入的逻辑也和查找的逻辑相似，我们需要分情况判断：
⭐️如果树为空，就新增节点，赋值给root，相等时我们不插入
⭐️树不为空，就按查找逻辑，找到合适的位置进行插入
我们找到合适的位置之和，还需要与上面的树进行链接，所以我们在进行查找的时候，还需要用一个父节点记录位置，方便链接
bool insert(const K& val)
{
//找到合适的位置插入
if (_root == nullptr)
{
Node* newnode = new Node(val);
_root = newnode;
return true;
}
Node* cur = _root;
//记录父亲
Node* parent = _root;
while (cur)
{
if (cur->_val > val)
{
parent = cur;
cur = cur->_left;
}
else if (cur->_val < val)
{
parent = cur;
cur = cur->_right;
}
//相等不插入
else
{
return false;
}
}
Node* newnode = new Node(val);
//判断插入哪边,用值比较
if (parent->_val >val)
{
parent->_left = newnode;
return true;
}
else
{
parent->_right = newnode;
return true;
}
}
3.删除
首先查找这个元素是不是存在，不存在我们直接返回，如果存在可能会出现下面四种情况：
🌟叶子节点：直接删除
比如删除1，找到它的父亲，删除1，再将父亲指向的这个节点制空
🌟右子树为空，左子树不为空
比如删除14，我们找到14的父节点，cur的左子树连接到父亲节点，在删除当前节点
🌟左子树为空，右子树不为空
这个也是同样的道理
这三种情况可以进行合并为两种：
删除该结点且使被删除节点的双亲结点指向被删除节点的左孩子结点–直接删除
删除该结点且使被删除节点的双亲结点指向被删除结点的右孩子结点–直接删除
🌟左右子树都存在
我们想要删除3，怎末删除呢？？删除之后这棵树还保持原有的特性
这里我们采用替换法删除，找一个可以替换的节点，交换两个位置的值，再删除这个替换节点。
什么节点可以进行替换呢？？我们有两种选择：
左子树最右节点，也就是左子树中值最大的那个节点
右子树最左节点，也就是右子树中值最小的那个节点
我们采用右子树最左节点来进行操作，
//删除
bool erase(const K&val)
{
Node* cur = _root;
//先找到删除节点
//记录父亲
Node* parent = _root;
while (cur)
{
if (cur->_val > val)
{
parent = cur;
cur = cur->_left;
}
else if (cur->_val < val)
{
parent = cur;
cur = cur->_right;
}
//相等找到了
else
{
//删除操作
}
}
}
🧐🧐我们先看前两种情况
//左子树为空
if (cur->_left == nullptr)
{
if (cur == parent->_left)
{
parent->_left = cur->_right;
}
else
{
parent->_right = cur->_right;
}
delete cur;
return true;
}
//右子树为空
else if (cur->_right == nullptr)
{
if (cur == parent->_left)
{
parent->_left = cur->_left;
}
else
{
parent->_right = cur->_left;
}
delete cur;
return true;
}
我们看一下这这段代码？？？？
一般情况确实符合，我们来看一下面这种极端情况
如果我们想要删除8，我们来走一下代码
parent和cur都指向8这个节点，这个if,else语句不成立，根本就不会进去，就把这个节点给删除了，那我们也拿不到后面的节点了。
所以我们需要特殊处理。root直接指向它的孩子
if (cur->_left == nullptr)
{
if (_root == cur)
{
_root = _root->_right;
}
else
{
if (cur == parent->_left)
{
parent->_left = cur->_right;
}
else
{
parent->_right = cur->_right;
}
}
delete cur;
return true;
}
//右子树为空
else if (cur->_right == nullptr)
{
if (_root == cur)
{
_root = _root->_left;
}
else
{
if (cur == parent->_left)
{
parent->_left = cur->_left;
}
else
{
parent->_right = cur->_left;
}
}
delete cur;
return true;
}
🧐🧐我们看一下两个节点都存在的情况
替换法：找到右子树的最左节点进行，找到后交换两者的值，最后删除这个替换节点，再通过这个替换节点的父亲把这个替换节点维护起来（可能存在右孩子）
我们以删除3为例子
首先找到替换节点4，标记为RightMin，顺表找到它的父亲节点RightParent 。交换两个节点的值
接下来我们就可以对3进行删除，同时维护这个节点
我们看一下代码实现`
else
{
//替换法删除
//先找到替换的位置和父亲,右子树最左节点
Node* RightMin = cur->_right;
Node* RightParent = cur;
while (RightMin->_left)
{
RightParent = RightMin;
RightMin = RightMin->_left;
}
//交换
std::swap(cur->_val, RightMin->_val);
RightParent->_left = RightMin->_right;
delete RightMin;
return true;
}
这样我们就实现了这个删除操作，但是我们看一下是不是有什么情况没有考虑呢？？
我们看一下这种情况，我们要删除8
我们交换了之后
我们发现没有左子树，这句代码RightParent->_left = RightMin->_right;就会崩溃，空指针的访问。
我们先还需要特殊处理
else
{
//替换法删除
//先找到替换的位置和父亲,右子树最左节点
Node* RightMin = cur->_right;
Node* RightParent = cur;
while (RightMin->_left)
{
RightParent = RightMin;
RightMin = RightMin->_left;
}
//交换
std::swap(cur->_val, RightMin->_val);
if (RightParent->_left == RightMin)
RightParent->_left = RightMin->_right;
else
RightParent->_right = RightMin->_right;
delete RightMin;
return true;
}
完整代码
template<class K>
class BSTree
{
public:
//强制生成默认构造
BSTree() = default;
//插入
bool insert(const K& val)
{
//找到合适的位置插入
if (_root == nullptr)
{
Node* newnode = new Node(val);
_root = newnode;
return true;
}
Node* cur = _root;
//记录父亲
Node* parent = _root;
while (cur)
{
if (cur->_val > val)
{
parent = cur;
cur = cur->_left;
}
else if (cur->_val < val)
{
parent = cur;
cur = cur->_right;
}
//相等不插入
else
{
return false;
}
}
Node* newnode = new Node(val);
//判断插入哪边,用值比较
if (parent->_val >val)
{
parent->_left = newnode;
return true;
}
else
{
parent->_right = newnode;
return true;
}
}
//查找
bool find(const K& val)
{
Node* cur = _root;
while (cur)
{
if (cur->_val > val)
{
cur = cur->_left;
}
else if (cur->_val < val)
{
cur = cur->_right;
}
//相等不插入
else
{
return true;
}
}
return false;
}
//中序遍历
//采用递归，必须要进行参数传递，封装一层；
void Inorder()
{
_Inorder(_root);
}
//删除
bool erase(const K&val)
{
Node* cur = _root;
//先找到删除节点
//记录父亲
Node* parent = _root;
while (cur)
{
if (cur->_val > val)
{
parent = cur;
cur = cur->_left;
}
else if (cur->_val < val)
{
parent = cur;
cur = cur->_right;
}
//相等找到了
else
{
//左子树为空
if (cur->_left == nullptr)
{
if (_root == cur)
{
_root = _root->_right;
}
else
{
if (cur == parent->_left)
{
parent->_left = cur->_right;
}
else
{
parent->_right = cur->_right;
}
}
delete cur;
return true;
}
//右子树为空
else if (cur->_right == nullptr)
{
if (_root == cur)
{
_root = _root->_left;
}
else
{
if (cur == parent->_left)
{
parent->_left = cur->_left;
}
else
{
parent->_right = cur->_left;
}
}
delete cur;
return true;
}
//两个孩子
else
{
//替换法删除
//先找到替换的位置和父亲,右子树最左节点
Node* RightMin = cur->_right;
Node* RightParent = cur;
while (RightMin->_left)
{
RightParent = RightMin;
RightMin = RightMin->_left;
}
//交换
std::swap(cur->_val, RightMin->_val);
if(RightParent->_left==RightMin)
RightParent->_left = RightMin->_right;
else
RightParent->_right = RightMin->_right;
delete RightMin;
return true;
}
}
}
return false;
}
private:
typedef TreeeNode<K> Node;
Node* _root=nullptr;
};
三、二叉搜索树递归实现
1.查找
我们查好就很容易完成了，这个值大，就去右边找。这个值小就去左边找。找到空了就返回。逻辑很简单。
不同的是我们需要封装一层，外边传递的参数不符合我们递归的参数。
bool Rfind(const K& val)
{
return _Rfind(val, _root);
}
bool _Rfind(const K& val, Node* root)
{
if (root == nullptr)
{
return false;
}
if (root->_val > val)
{
return _Rfind(val, root->_left);
}
else if (root->_val < val)
{
return _Rfind(val, root->_right);
}
else
{
return true;
}
}
2.插入
找到合适的位置进行插入就可以.
void Rinsert(const K& val)
{
_Rinsert(val,_root);
}
我们需要注意的是如何进行链接并且返回。
我们想要插入15，我们如何通过递归找到这个父节点？？？
bool _Rinsert(const K& val,Node*& root)这就可以完成
传参传递的是引用，这里的root是上一层root->right的别名。
所以实际上就是让14指向了15。这个引用只在最后一层起作用。
bool _Rinsert(const K& val,Node*& root)
{
if (root == nullptr)
{
//开节点插入
root= new Node(val);
return true;
}
if (root->_val > val)
{
return _Rinsert(val, root->_left);
}
else if(root->_val < val)
{
return _Rinsert(val, root->_right);
}
else
{
return false;
}
}
3.删除
找到合适的位置删除，但是这里的删除要分情况删除。
一个孩子的情况很简单，我们主要看一下两个孩子的情况
我们还是需要用到替换法删除，但是我们不需要找父亲了；我们这里有引用。
我们这里转换成去这棵树进行删除。直接将要删除的节点有两个孩子，变成只有一个孩子或是没有孩子的情况
void Rerase(const K& val)
{
_Rerase(val, _root);
}
bool _Rerase(const K& val, Node*& root)
{
//这里所有情况都包含，我们不用找父亲了。
if (root == nullptr)
{
return false;
}
if (root->_val > val)
{
return _Rerase(val, root->_left);
}
else if (root->_val < val)
{
return _Rerase(val, root->_right);
}
//找到了
else
{
Node* del = root;
//判断一个孩子情况
if (root->_left == nullptr)
{
root = root->_right;
}
else if (root->_right == nullptr)
{
root = root->_left;
}
//两个孩子
else
{
//替换法删除.右子树最左节点
Node* RightMin = root->_right;
while (RightMin->_left)
{
RightMin = RightMin->_left;
}
//交换
std::swap(RightMin->_val, root->_val);
//转换成去这棵树删除
return _Rerase(val, root->_right);
}
delete del;
}
return true;
}
四、二叉搜索树性能分析
插入和删除之前都必须先进行查找，那么查找的效率就是二叉搜索树中操作的性能。
我们可以发现，最差就是查找高度次，有人说，这不就是logn吗！！
但是对于同一个关键码集合，插入的顺序不同，极有可能得到不同的·二叉搜索树。
💗最优的情况：二叉搜索树为完全二叉树，平均比较次数就是logn
💗最差的情况：就像右图所示，退化为类似单只，平均比较次数就是n
如果退化成单支树，二叉搜索树的性能就失去了。那能否进行改进，不论按照什么次序插
入关键码，二叉搜索树的性能都能达到最优？那么我们后续章节学习的AVL树和红黑树就可以上
场了
五、二叉搜索树应用
1.K模型
k模型只有key作为关键字，在结构中只需要存储key就可以。
使用：
🌟日常生活中我们开车进入小区中，会进行车牌的扫描，快速查找，看你是否是这个小区的车型，若果是抬杆，进去。如果不存在，就进不去
🌟查看一个单词是否拼写错误，在词库中所有单词构建一颗二叉搜索树，在二叉搜索树中查找该单词是否存在。
2.KV模型
每一个对应的key都有一个与之对应的value,即<K,V>键值对
使用：
🌟高铁刷身份进站，每一个乘客都有一个身份证号，如果在平台上买票了，就会更新这个身份信息。
🌟查找某个单词的意思，<中文，英文>也构成了键值对
🌟统计单词出现的个数，统计成功后，给定单词就可快速找到其出现的次数，单词与其出
现次数就是<word, count>就构成一种键值对。
总结
以上就是今天要讲的内容，本文仅仅详细介绍了二叉搜索树的相关内容。希望对大家的学习有所帮助，仅供参考 如有错误请大佬指点我会尽快去改正 欢迎大家来评论~~ 😘 😘 😘
