C++进阶：二叉搜索树

🕗 发布于 2024-10-10 23:54 数据结构 c++ 二叉树

一.二叉搜索树的概念

二.二叉搜索树的性能

三.二叉搜索树的插入

四.二叉搜索树的查找

五.二叉搜索树的删除

六.二叉搜索树key和key/value使用场景和实现代码

一.二叉搜索树的概念

二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有以下性质的二叉树:

• 若它的左子树不为空，则左子树上所有结点的值都小于等于根结点的值

• 若它的右子树不为空，则右子树上所有结点的值都大于等于根结点的值

• 它的左右子树也分别为二叉搜索树

• 二叉搜索树中可以支持插入相等的值，也可以不支持插入相等的值，具体看使用场景定义，map/set/multimap/multiset系列容器底层就是二叉搜索树，其中map/set不支持插入相等值，multimap/multiset支持插入相等值。

比如：

二.二叉搜索树的性能

最优情况下，二叉搜索树为完全二叉树(或者接近完全二叉树)，其高度为：O(log2N)最差情况下，二叉搜索树退化为单支树(或者类似单支)，其高度为：O(N/2)

所以综合而言二叉搜索树增删查改时间复杂度为：O(N)

另外需要说明的是，二分查找也可以实现O(logN) 级别的查找效率，但是二分查找有两大缺陷：

• 需要存储在支持下标随机访问的结构中，并且有序。

• 插入和删除数据效率很低，因为存储在下标随机访问的结构中，插⼊和删除数据⼀般需要挪动数据。这里也就体现出了平衡二叉搜索树的价值。

三.二叉搜索树的插入

插入的具体过程如下：

1. 树为空，则直接新增结点，赋值给root指针

2. 树不空，按二叉搜索树性质，插入值比当前结点大往右走，插⼊值比当前结点小往左走，找到空位置，插入新结点。

3. 如果支持插入相等的值，插入值跟当前结点相等的值可以往右走，也可以往左走，找到空位置，插入新结点。（要注意的是要保持逻辑一致性，插入相等的值不要⼀会往右走，⼀会往左走）

这是一个节点的结构：

using namespace std;
template<class K>
class BSTNode
{
K _val;
BSTNode<K>* _left;
BSTNode<K>* _right;
BSTNode(const K& key)
:_key(key)
,_left(nullptr)
,_right(nullptr)
{}
}

这里来正式实现插入：

bool Insert(const K& key)
{
if (_root == nullptr)
{
_root = new Node(key);
return true;
}
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
if (cur->_val > key)
{
parent = cur;
cur = cur->left;
}
else if (aur->val < key)
{
parent = cur;
aur = cur->right;
}
else
{
return false;
}
}
cur = new Node(key);
if (parent->_val > key)
{
parent->_left = cur;
}
else
{
parent->_right = cur;
}
return true;
}

四.二叉搜索树的查找

1. 从根开始比较，查找x，x比根大的则往右边走查找，x比根值小则往左边走查找。

2. 最多查找高度次，走到到空，还没找到，这个值不存在。

3. 如果不支持插入相等的值，找到x即可返回

4. 如果支持插入相等的值，意味着有多个x存在，⼀般要求查找中序的第一个x。如下图，查找3，要找到1的右孩子的那个3返回。

bool Find(const K& key)
{
Node* cur = _root;
while (cur)
{
if (cur->_key < key)
{
cur = cur->_right;
}
else if (cur->_key > key)
{
cur = cur->_left;
}
else

{
return true;
}
}
return false;
}

五.二叉搜索树的删除

首先查找元素是否在二叉搜索树中，如果不存在，则返回false。如果查找元素存在则分以下四种情况分别处理：（假设要删除的结点为N）

1. 要删除结点N左右孩子均为空

2. 要删除的结点N左孩子为空，右孩子结点不为空

3. 要删除的结点N右孩子为空，左孩子结点不为空

4. 要删除的结点N左右孩子结点均不为空

对应以上四种情况的解决方案：

1. 把N结点的父亲对应孩子指针指向空，直接删除N结点（情况1可以当成2或者3处理，效果是⼀样的）

2. 把N结点的父亲对应孩子指针指向N的右孩子，直接删除N结点

3. 把N结点的父亲对应孩子指针指向N的左孩子，直接删除N结点

4. 无法直接删除N结点，因为N的两个孩子无处安放，只能用替换法删除。找N左子树的值最大结点R(最右结点)或者N右子树的值最小结点R(最左结点)替代N，因为这两个结点中任意⼀个，放到N的位置，都满足二叉搜索树的规则。替代N的意思就是N和R的两个结点的值交换，转而变成删除R结点，R结点符合情况2或情况3，可以直接删除。

template<class K>
class BSTNode
{
public:
K _key;
BSTNode<K>* _left;
BSTNode<K>* _right;
BSTNode(const K& key)
: _key(key)
, _left(nullptr)
, _right(nullptr)
{}
};
template<class K>
class BSTree
{
typedef BSTNode<K> Node;
public:
bool Insert(const K& key)
{
if (_root == nullptr)
{
_root = new Node(key);
return true;
}
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
if (cur->_key > key)
{
parent = cur;
cur = cur->_left;
}
else if (cur->_key < key)
{
parent = cur;
cur = cur->_right;
}
else
{
return false;
}
}
cur = new Node(key);
if (parent->_key > key)
{
parent->_left = cur;
}
else
{
parent->_right = cur;
}
return true;
}
bool Find(const K& key)
{
Node* cur = _root;
while (cur)
{
if (cur->_key < key)
{
cur = cur->_right;
}
else if (cur->_key > key)
{
cur = cur->_left;
}
else

{
return true;
}
}
return false;
}
bool Erase(const K& key)
{
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
if (cur->_key > key)
{
parent = cur;
cur = cur->_left;
}
else if (cur->_key < key)
{
parent = cur;
cur = cur->_right;
}
else//找到了
{
//0到1个孩子的情况
if (cur->_left == nullptr)//左边为空，右边可能有
{
if (parent == nullptr)//删除的可能是根
{
_root = cur->_right;
}
else//不是根，需要找到要删除的是parent的左子树还是右子树
{
if (parent->_left == cur)
{
parent->_left = cur->_right;
}
else
{
parent->_right = cur->_right;
}
}
delete cur;
return true;
}
else if (cur->_right == nullptr)//右边为空，左边有
{
if (parent == nullptr)//删除的可能是根
{
_root = cur->_left;
}
else//不是根，需要找到要删除的是parent的左子树还是右子树
{
if (parent->_left == cur)
{
parent->_left = cur->_left;
}
else
{
parent->_right = cur->_left;
}
}
delete cur;
return true;
}
//两个孩子都存在的情况
//用替换法取删除
//取右子树的最小节点作为替换节点，也可以用左子树的最大节点
else
{
Node* rightMinP = cur;//注意这里不能给nullptr，因为可能没有进循环
//右子树的最左节点就是右子树的根，这个节点的左子树是空
Node* rightMin = cur->_right;
while (rightMin->_left)
{
rightMinP = rightMin;
rightMin = rightMin->_left;
}
cur->_key = rightMin->_key;
if (rightMinP->_left == rightMin)
{
rightMinP->_left = rightMin->_right;
}
//这里的if判断是为了避免右子树的最左节点是根结点的情况，此时的parent的_right指向rightMin
else
{
rightMinP->_right = rightMin->_right;
}
delete rightMin;
return true;
}
}
}
return false;
}
void InOrder()
{
_InOrder(_root);
cout << endl;
}

private:
void _InOrder(Node* root)
{
if (root == nullptr)
{
return;
}
_InOrder(root->_left);
cout << root->_key << " ";
_InOrder(root->_right);
}

private:
Node* _root = nullptr;
};

对于样例4，我要删除8，cur在8的位置。此时的rightMin就是右子树的最左位置，此时不会进入循环，如果把rightMinP的值赋值为nullptr的话就会报错。还有就是后面的if判断，不能确定一定的rightMinP的左边，可能是右边的情况。

六.二叉搜索树key和key/value使用场景和实现代码

只有key作为关键码，结构中只需要存储key即可，关键码即为需要搜索到的值，搜索场景只需要判断key在不在。key的搜索场景实现的二叉树搜索树支持增删查，但是不支持修改，修改key破坏搜索树结构了。

代码实现：

template<class K,class V>
class BSTNode
{
public:
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:
BSTree() = default;
BSTree(const BSTree<K, V>& t)
{
_root = Copy(t._root);
}
BSTree<K, V>& operator=(BSTree<K, V> t)
{
swap(_root, t._root);
return *this;
}
~BSTree()
{
Destory(_root);
_root = nullptr;
}
bool Insert(const K& key,const V& value)
{
if (_root == nullptr)
{
_root = new Node(key,value);
return true;
}
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
if (cur->_key > key)
{
parent = cur;
cur = cur->_left;
}
else if (cur->_key < key)
{
parent = cur;
cur = cur->_right;
}
else
{
return false;
}
}
cur = new Node(key,value);
if (parent->_key > key)
{
parent->_left = cur;
}
else
{
parent->_right = cur;
}
return true;
}
Node* Find(const K& key)
{
Node* cur = _root;
while (cur)
{
if (cur->_key < key)
{
cur = cur->_right;
}
else if (cur->_key > key)
{
cur = cur->_left;
}
else

{
return cur;
}
}
return nullptr;
}
bool Erase(const K& key,const V& value)
{
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
if (cur->_key > key)
{
parent = cur;
cur = cur->_left;
}
else if (cur->_key < key)
{
parent = cur;
cur = cur->_right;
}
else//找到了
{
//0到1个孩子的情况
if (cur->_left == nullptr)//左边为空，右边可能有
{
if (parent == nullptr)//删除的可能是根
{
_root = cur->_right;
}
else//不是根，需要找到要删除的是parent的左子树还是右子树
{
if (parent->_left == cur)
{
parent->_left = cur->_right;
}
else
{
parent->_right = cur->_right;
}
}
delete cur;
return true;
}
else if (cur->_right == nullptr)//右边为空，左边有
{
if (parent == nullptr)//删除的可能是根
{
_root = cur->_left;
}
else//不是根，需要找到要删除的是parent的左子树还是右子树
{
if (parent->_left == cur)
{
parent->_left = cur->_left;
}
else
{
parent->_right = cur->_left;
}
}
delete cur;
return true;
}
//两个孩子都存在的情况
//用替换法取删除
//取右子树的最小节点作为替换节点，也可以用左子树的最大节点
else
{
Node* rightMinP = cur;//注意这里不能给nullptr，因为可能没有进循环
//右子树的最左节点就是右子树的根，这个节点的左子树是空
Node* rightMin = cur->_right;
while (rightMin->_left)
{
rightMinP = rightMin;
rightMin = rightMin->_left;
}
cur->_key = rightMin->_key;
if (rightMinP->_left == rightMin)
{
rightMinP->_left = rightMin->_right;
}
//这里的if判断是为了避免右子树的最左节点是根结点的情况，此时的parent的_right指向rightMin
else
{
rightMinP->_right = rightMin->_right;
}
delete rightMin;
return true;
}
}
}
return false;
}
void InOrder()
{
_InOrder(_root);
cout << endl;
}

private:
void _InOrder(Node* root)
{
if (root == nullptr)
{
return;
}
_InOrder(root->_left);
cout << root->_key << ":" << root->_value << endl;
_InOrder(root->_right);
}
//实现拷贝函数，对应上面的拷贝构造函数
Node* Copy(Node* root)
{
if (root == nullptr)
return nullptr;
//前序遍历
Node* Newnode = new Node(root->_key, root->_value);//新开一块空间
Newnode->_left = Copy(root->_left);
Newnode->_right = Copy(root->_right);
return Newnode;
}
void Destory(Node* root)
{
//函数出口
if (root == nullptr)
return;
//后序遍历
Destory(root->_left);
Destory(root->_right);
delete root;
}
private:
Node* _root = nullptr;
};

原文地址：https://blog.csdn.net/2301_81699364/article/details/142726560

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

上一篇：基于SSM的大学生勤工助学管理系统（含源码+sql+视频导入教程+文档+PPT）
下一篇：DFT中boundary scan与其他扫描技术相比有何优势？

html中＜div＞标签设置宽度和高度都有哪些方法
在 HTML 和 CSS 中，设置<div>标签的宽度和高度有多种方法，取决于你希望如何控制它的尺寸。
阅读更多2024-10-11
Java面试宝典-Java集合02
这增加了额外的内存开销，但使得在链表中间添加或删除元素的操作变得高效。通过使用WeakHashMap，可以将某些对象与其他应用逻辑分离开来，使得它们的生命周期仅由其它对象的引用决定，当没有任何对象引
阅读更多2024-10-11
一、安装VMWARE和CentOS
https://www.downxia.com/downinfo/297733.html（许可证：FC7D0-D1YDL-M8DXZ-CYPZE-P2AY6）Centos-8.1.1911-x86 6
阅读更多2024-10-11
前端自定义指令控制权限（后端Spring Security）
const pinaRoles: any = wmsStore().roles; if (Array.isArray(roles)) { return roles.some(role =>
阅读更多2024-10-11
安装 Android Studio 步骤日志
教程：https://developer.android.google.cn/codelabs/basic-android-kotlin-compose-first-app?Gradle 下载地址：h
阅读更多2024-10-11
API接口文档 Swagger&Knife4j 的用法
使用 Swagger 和 Knif4j 注释可以清晰地描述 API 的功能、参数和返回值，使得生成的文档更加易于理解和使用。通过合理使用这些注释，可以有效提升 API 的可维护性和可读性。
阅读更多2024-10-11
风口来了:有空可以考个人工智能证书！
为进一步贯彻落实中共中央印发《关于深化人才发展体制机制改革的意见》和国务院印发《关于“十四五”数字经济发展规划》等有关工作的部署要求，深入实施人才强国战略和创新驱动发展战略，加强全国数字化人才队伍建设
阅读更多2024-10-11
uniapp 锁屏显示插件 Ba-LockShow（可让vue直接具备锁屏显示能力）
Ba-LockShow 是一款可以直接使uniapp的vue界面在锁屏页展示的插件。支持使vue直接具备锁屏显示能力，支持设置锁屏显示和不显示，支持唤醒屏幕。
阅读更多2024-10-11
责任链模式
log.info("StrategyCheck task 后置校验");log.info("StrategyCheck task 前置校验");其次观察者模式中
阅读更多2024-10-11
NeurIPS‘24盛会在即：AI大佬Geoffrey E. Hinton获诺贝尔物理学奖
会议之眼快讯在人工智能领域，Geoffrey E. Hinton 的名字无疑是一个里程碑。这位科学家刚刚在2024年诺贝尔物理学奖的颁奖典礼上，再次成为全球焦点。与John J. Hopfield一
阅读更多2024-10-11

C++进阶：二叉搜索树

一.二叉搜索树的概念

二.二叉搜索树的性能

三.二叉搜索树的插入

四.二叉搜索树的查找

五.二叉搜索树的删除

六.二叉搜索树key和key/value使用场景和实现代码

相关文章