当前位置: 首页 > backend >正文

二叉搜索树讲解

1. 二叉搜索树的概念

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

1. 若它的左子树不为空,则左子树上的所有结点的值都小于等于根节点的值。

2. 若它的右子树不为空,则右子树上的所有结点的值都大于等于根节点的值。

3. 它的左右子树也分别为二叉搜索树。

4. 二叉搜索树中可以支持插入相等的值,也可以不支持插入相等的值,具体看使用场景定义。

2. 二叉搜索树的性能分析

最优情况下,二叉搜索树为完全二叉树(或者接近完全二叉树),其高度为:log2 N。

最差情况下,二叉搜索树退化为单支树(或者类似单支),其高度为:N。

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

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

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

2. 插入和删除数据效率很低,因为存储在下标随机访问的结构中,插入和删除数据一般需要挪动数据。

这里也就体现出了平衡二叉搜索树的价值。

3. 二叉搜索树的插入

插入的具体过程如下:

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

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

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

我给出的示例代码是不支持插入相等的值的。

bool Insert(const T& key)
{if (_root == nullptr){_root = new Node(key);return true;}Node* cur = _root;Node* parent = nullptr;while (cur){if (key > cur->_key){parent = cur;cur = cur->_right;}else if (key < cur->_key){parent = cur;cur = cur->_left;}else{return false;}}cur = new Node(key);if (key > parent->_key){parent->_right = cur;}else{parent->_left = cur;}return true;
}

4. 二叉搜索树的查找

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

2. 最多查找高度次,走到空,还没找到,那么就说明这个值不存在。

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

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

bool Find(const T& x)
{Node* cur = _root;while (cur){if (x > cur->_key){cur = cur->_right;}else if (x < cur->_key){cur = cur->_left;}else{return true;}}return false;
}

5. 二叉搜索树的删除

首先查找元素是否在二叉搜索树中,如果不存在,直接返回false。

如果查找元素存在,则分为以下四种情况分别处理:(假设要删除的结点为N)

1. N的左右孩子均为空。

2. N左孩子为空,右孩子不为空。

3. N右孩子为空,左孩子不为空。

4. N的左右孩子均不为空

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

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

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

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

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

bool Erase(const T& key)
{Node* cur = _root;Node* parent = nullptr;while (cur){if (key > cur->_key){parent = cur;cur = cur->_right;}else if (key < cur->_key){parent = cur;cur = cur->_left;}else{// 开始删除if (cur->_left == nullptr){if (cur == _root){_root = cur->_right;}else{if (cur == parent->_left){parent->_left = cur->_right;}else{parent->_right = cur->_right;}}delete cur;}else if (cur->_right == nullptr){if (cur == _root){_root = cur->_left;}else{if (cur == parent->_left){parent->_left = cur->_left;}else{parent->_right = cur->_left;}}delete cur;}else{// 找右子树的最小节点(最左节点)替代Node* replace_parent = cur;Node* replace = cur->_right;while (replace->_left){replace_parent = replace;replace = replace->_left;}swap(cur->_key, replace->_key);if (replace == replace_parent->_left){replace_parent->_left = replace->_right;}else{replace_parent->_right = replace->_right;}delete replace;}return true;}}return false;
}

6. 完整的实现代码

#include<iostream>using namespace std;template<class T>
struct BinarySearchTreeNode
{T _key;BinarySearchTreeNode<T>* _left;BinarySearchTreeNode<T>* _right;BinarySearchTreeNode(const T& key):_key(key),_left(nullptr),_right(nullptr){ }
};template<class T>
class BSTree
{typedef BinarySearchTreeNode<T> Node;
public:bool Insert(const T& key){if (_root == nullptr){_root = new Node(key);return true;}Node* cur = _root;Node* parent = nullptr;while (cur){if (key > cur->_key){parent = cur;cur = cur->_right;}else if (key < cur->_key){parent = cur;cur = cur->_left;}else{return false;}}cur = new Node(key);if (key > parent->_key){parent->_right = cur;}else{parent->_left = cur;}return true;}bool Find(const T& x){Node* cur = _root;while (cur){if (x > cur->_key){cur = cur->_right;}else if (x < cur->_key){cur = cur->_left;}else{return true;}}return false;}bool Erase(const T& key){Node* cur = _root;Node* parent = nullptr;while (cur){if (key > cur->_key){parent = cur;cur = cur->_right;}else if (key < cur->_key){parent = cur;cur = cur->_left;}else{// 开始删除if (cur->_left == nullptr){if (cur == _root){_root = cur->_right;}else{if (cur == parent->_left){parent->_left = cur->_right;}else{parent->_right = cur->_right;}}delete cur;}else if (cur->_right == nullptr){if (cur == _root){_root = cur->_left;}else{if (cur == parent->_left){parent->_left = cur->_left;}else{parent->_right = cur->_left;}}delete cur;}else{// 找右子树的最小节点(最左节点)替代Node* replace_parent = cur;Node* replace = cur->_right;while (replace->_left){replace_parent = replace;replace = replace->_left;}swap(cur->_key, replace->_key);if (replace == replace_parent->_left){replace_parent->_left = replace->_right;}else{replace_parent->_right = replace->_right;}delete replace;}return true;}}return false;}void _InOrder(Node* root){if (root == nullptr){return;}_InOrder(root->_left);cout << root->_key << ' ';_InOrder(root->_right);}void InOrder(){_InOrder(_root);cout << endl;}private:Node* _root = nullptr; 
};int main()
{BSTree<int> tree;int arr[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };for (auto& e : arr){tree.Insert(e);}tree.InOrder();cout << tree.Find(10) << endl;cout << tree.Find(100) << endl;tree.Erase(10);tree.Erase(6);tree.InOrder();return 0;
}
http://www.xdnf.cn/news/5363.html

相关文章:

  • [思维模式-25]:《本质思考力》-6- 马克思主义哲学的五对基本哲学范畴,以及在计算机领域的体现
  • 用c语言实现——一个交互式的中序线索二叉树系统,支持用户动态构建、线索化、遍历和查询功能
  • 理性地倾听与表达:检索算法的语言学改进
  • 《P1226 【模板】快速幂》
  • 开疆智能Profinet转canopen网关连接易福门(IFM)传感器配置案例
  • QB/T 1649-2024 聚苯乙烯泡沫塑料包装材料检测
  • 大模型MCP更高效的通信:StreamableHTTP协议
  • 欧拉计划 Project Euler 69(欧拉总计函数与最大值)题解
  • 炫酷粒子系统动画实战:Matplotlib实现银河漩涡效果
  • SierraNet M1288网络损伤功能显著助力GPU互联网络的测试验证,包含包喷洒,LLR等复杂特性的验证测试
  • GMS 与非 GMS:有何区别?
  • Java基础:代理
  • KNOWLEDGE-BASED SYSTEMS(KBS期刊)投稿经验分享
  • # 深度学习实操 附录B 深入解析 tensorflow 自动微分
  • 纯惯性导航、非线性最小二乘法纯uwb测距导航定位、惯性uwb松组合导航、惯性uwb紧组合导航,四种方法对比
  • 圆角边框 盒子阴影 文字阴影
  • Linux进程间通信(四)之补充【日志】
  • PCB设计实践(十三)PCB设计中差分线间距与线宽设置的深度解析
  • 蓝牙GAP协议概述
  • AI赋能研究工作:我的深度学习助手使用体验(DeepResearch)
  • 认识 Linux 内存构成:Linux 内存调优之内存分配机制和换页行为认知
  • ERP学习(二):用友软件产品之系统管理
  • 学习黑客5 分钟深入浅出理解SCP
  • 【从零实现JsonRpc框架#3】线程模型与性能优化
  • 《设计数据密集型应用》——阅读小记
  • JAVA——抽象类和接口的区别
  • 【Linux基础】系统监控和进程管理指令
  • 【Reality Capture 】Reality Capture1.5中文版安装教程(附安装包下载)
  • 英语六级---2024.12卷三 仔细阅读2
  • VRRP协议-IP地址冗余配置