《⼆叉搜索树》

《⼆叉搜索树》

  • 1. ⼆叉搜索树的概念
  • 2. ⼆叉搜索树的性能分析
  • 3 二叉树的功能说明及实现
    • 3.1 ⼆叉搜索树的插⼊
    • 3.2 ⼆叉搜索树的查找
    • 3.3 ⼆叉搜索树的删除
  • 4二叉搜索树的实现代码
  • 5 ⼆叉搜索树key和key/value使⽤场景
    • 5.1 key搜索场景：
    • 5.2 key/value搜索场景：
    • 5.3 key/value⼆叉搜索树代码实现
  • 结束！！！

1. ⼆叉搜索树的概念

⼆叉搜索树⼜称⼆叉排序树，它或者是⼀棵空树，或者是具有以下性质的⼆叉树:
1• 若它的左⼦树不为空，则左⼦树上所有结点的值都⼩于等于根结点的值

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

3• 它的左右⼦树也分别为⼆叉搜索树

4• ⼆叉搜索树中可以⽀持插⼊相等的值，也可以不⽀持插⼊相等的值，具体看使⽤场景定义，后续我们学习map/set/multimap/multiset系列容器底层就是⼆叉搜索树，其中map/set不⽀持插⼊相等值，multimap/multiset⽀持插⼊相等值

在这里插入图片描述

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

最优情况下，⼆叉搜索树为完全⼆叉树(或者接近完全⼆叉树)，其⾼度为： O(log2 N)

最差情况下，⼆叉搜索树退化为单⽀树(或者类似单⽀)，其⾼度为： O( 2/N)

所以综合⽽⾔⼆叉搜索树增删查改时间复杂度为： O(N)

那么这样的效率显然是⽆法满⾜我们需求的，⼆叉搜索树的变形，平衡⼆叉搜索树AVL树和红⿊树，才能适⽤于我们在内存中存储和搜索数据。

【二分查找】
也可以实现O(logN) 级别的查找效率，但是⼆分查找有两⼤缺陷：

1：有序且需支持下标随机访问
2：插⼊和删除数据效率很低，因为存储在下标随机访问的结构中，插⼊和删除数据⼀般需要挪动数据。这就体现搜索二叉树的重要性。

对于二叉搜索树有着特殊情况：
在这里插入图片描述
以上的情况，在普通搜索二叉树中会拖长，搜索时间和访问的时间都会有所延长，为了解决这种情况，就体现了⼆叉搜索树的变形，平衡⼆叉搜索树AVL树和红⿊树，才能适⽤于我们在内存中存储和搜索数据的重要性。

3 二叉树的功能说明及实现

3.1 ⼆叉搜索树的插⼊

具体实现如下：

  1. 树为空，则直接新增结点，赋值给root指针
  2. 树不空，按⼆叉搜索树性质，插⼊值⽐当前结点⼤往右⾛，插⼊值⽐当前结点⼩往左⾛，找到空位置，插⼊新结点。
  3. 如果⽀持插⼊相等的值，插⼊值跟当前结点相等的值可以往右⾛，也可以往左⾛，找到空位置，插⼊新结点。（要注意的是要保持逻辑⼀致性，插⼊相等的值不要⼀会往右⾛，⼀会往左⾛）
template<class K>
struct BSTNode
{K _key;BSTNode<K>* _left;BSTNode<K>* _right;BSTNode(const K& key):_key(key), _left(nullptr), _right(nullptr){}
template<K>
class BStree
{typedef BSTNode<K> Node;public:bool insert(const K& key){Node* cur=_root;Node* parent=nullptr;if(_root==nullptr){_root = new Node(key);}while(cur){if(cur->_key<=key){parent=cur;cur=cur->right;}else if(cur->_key>key){parent=cur;cur=cur->left;}esle{return false;}}cur=new Node(key);if(parent->_key<=key)parent->_right=cur;elseparent->_left=cur;return true;}
private:
Node* _root=nullptr;
}

3.2 ⼆叉搜索树的查找

  1. 从根开始⽐较，查找x，x⽐根的值⼤则往右边⾛查找，x⽐根值⼩则往左边⾛查找。

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

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

没有重复的元素的普通查找

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;}elsereturn true;}return false;
}
  1. 如果⽀持插⼊相等的值，意味着有多个x存在，⼀般要求查找中序的第⼀个x。如下图，查找3，要
    找到1的右孩⼦的那个3返回

有重复元素的查找，那就的依靠中序来遍历第一个元素

在这里插入图片描述

3.3 ⼆叉搜索树的删除

⾸先查找元素是否在⼆叉搜索树中，如果不存在，则返回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，可以直接删除。
bool erase(const K& key)
{Node* parent = nullptr;Node* cur = _root;while (cur)//找到对应元素{if (cur->_key < key){parent = cur;cur = cur->_right;}else if (cur->_key > key){parent = cur;cur = cur->_left;}else//删除节点(左右节点为空是被包含在，左节点为空或右节点为空的情况下的，所以不用考虑这种情况){if (cur->_left == nullptr)//1:左节点为空{if (parent == nullptr)//判断是否删除的是根节点{_root = cur->_right;}else{if (parent->_left == cur){parent->_left = cur->_right;}else{parent->_right = cur->_right;}}delete cur;return true;}else if (cur->_right == nullptr)//2:右节点为空{if (parent == nullptr){_root = cur->_left;}else{if (parent->_left == cur){parent->_left = cur->_left;}else{parent->_right = cur->_left;}}delete cur;return true;}else//3:双节点{Node* replace = cur->_right;Node* replaceparent = cur;while (replace->_left)//找到替换节点{replaceparent = replace;replace = replace->_left;}cur->_key = replace->_key;if (replaceparent->_left == replace)replaceparent->_left = replace->_right;elsereplaceparent->_right = replace->_right;delete replace;return true;}return false;}}
}

4二叉搜索树的实现代码

template<class K>
struct BSTNode
{
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 Find(const K& key){Node* cur = _root;while (cur){if (cur->_key < key){cur = cur->_right;}else if (cur->_key > key){cur = cur->_left;}elsereturn true;}return false;}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->_right;}else if (cur->_key > key){parent = cur;cur = cur->_left;}else{return false;}}cur = new Node(key);if (parent->_key < key){parent->_right = cur;}else{parent->_left = cur;}return true;}void _inorder(){inorder(_root);cout << endl;}bool erase(const K& key){Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_key < key){parent = cur;cur = cur->_right;}else if (cur->_key > key){parent = cur;cur = cur->_left;}else{if (cur->_left == nullptr)//左节点为空{if (parent == nullptr)//判断是否删除的是根节点{_root = cur->_right;}else{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{if (parent->_left == cur){parent->_left = cur->_left;}else{parent->_right = cur->_left;}}delete cur;return true;}else//双节点{Node* replace = cur->_right;Node* replaceparent = cur;while (replace->_left)//找到替换节点{replaceparent = replace;replace = replace->_left;}cur->_key = replace->_key;if (replaceparent->_left == replace)replaceparent->_left = replace->_right;elsereplaceparent->_right = replace->_right;delete replace;return true;}return false;}}}private:void inorder(Node * root){if (root == nullptr){return;}inorder(root->_left);cout << root->_key << " ";inorder(root->_right);}private:Node* _root = nullptr;
};

5 ⼆叉搜索树key和key/value使⽤场景

5.1 key搜索场景：

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

场景1：⼩区⽆⼈值守⻋库，⼩区⻋库买了⻋位的业主⻋才能进⼩区，那么物业会把买了⻋位的业主的
⻋牌号录⼊后台系统，⻋辆进⼊时扫描⻋牌在不在系统中，在则抬杆，不在则提⽰⾮本⼩区⻋辆，⽆
法进⼊。场景2：检查⼀篇英⽂⽂章单词拼写是否正确，将词库中所有单词放⼊⼆叉搜索树，读取⽂章中的单
词，查找是否在⼆叉搜索树中，不在则波浪线标红提⽰。

在这里插入图片描述

5.2 key/value搜索场景：

每⼀个关键码key，都有与之对应的值value，value可以任意类型对象。树的结构中(结点)除了需要存
储key还要存储对应的value，增/删/查还是以key为关键字⾛⼆叉搜索树的规则进⾏⽐较，可以快速查
找到key对应的value。key/value的搜索场景实现的⼆叉树搜索树⽀持修改，但是不⽀持修改key，修
改key破坏搜索树结构了，可以修改value。

 场景1：简单中英互译字典，树的结构中(结点)存储key(英⽂)和vlaue(中⽂)，搜索时输⼊英⽂，则同时查找到了英⽂对应的中⽂。场景2：商场⽆⼈值守⻋库，⼊⼝进场时扫描⻋牌，记录⻋牌和⼊场时间，出⼝离场时，扫描⻋牌，查找⼊场时间，⽤当前时间-⼊场时间计算出停⻋时⻓，计算出停⻋费⽤，缴费后抬杆，⻋辆离场。场景3：统计⼀篇⽂章中单词出现的次数，读取⼀个单词，查找单词是否存在，不存在这个说明第⼀次出现，（单词，1），单词存在，则++单词对应的次数。

在这里插入图片描述

5.3 key/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: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(){Destroy(_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->_right;}else if (cur->_key > key){parent = cur;cur = cur->_left;}else{return false;}}cur = new Node(key, value);if (parent->_key < key){parent->_right = cur;}else{parent->_left = 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){Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_key < key){parent = cur;cur = cur->_right;}else if (cur->_key > key){parent = cur;cur = cur->_left;}else{if (cur->_left == nullptr){if (parent == nullptr){_root = cur->_right;}else{if (parent->_left == cur)parent->_left = cur -> _right;elseparent->_right = cur -> _right;}delete cur;return true;}else if (cur->_right == nullptr){if (parent == nullptr){_root = cur->_left;}else{if (parent->_left == cur)parent->_left = cur -> _left;elseparent->_right = cur -> _left;}delete cur;return true;}else{ Node * rightMinP = cur;Node* rightMin = cur->_right;while (rightMin->_left){rightMinP = rightMin;rightMin = rightMin->_left;}cur->_key = rightMin->_key;if (rightMinP->_left == rightMin)rightMinP->_left = rightMin -> _right;elserightMinP->_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);}void Destroy(Node* root){if (root == nullptr)return;Destroy(root->_left);Destroy(root->_right);delete root;}Node* Copy(Node* root){if (root == nullptr)return nullptr;Node* newRoot = new Node(root->_key, root->_value);newRoot->_left = Copy(root->_left);newRoot->_right = Copy(root->_right);return newRoot;}
private:Node* _root = nullptr;
};

在这里插入图片描述

在这里插入图片描述

结束！！！

压力不是有人比你努力，而是比你牛叉几倍的人依然在努力。每个优秀的人，都有一段沉默的时光继承就讲到这里谢谢大家的观看！！！

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.xdnf.cn/news/10881.html

如若内容造成侵权/违法违规/事实不符，请联系一条长河网进行投诉反馈，一经查实，立即删除！

相关文章

stm32 踩坑笔记

stm32 踩坑笔记

串口问题&#xff1a; 问题&#xff1a;会改变接收缓冲的下一个字节 串口的初始化如下&#xff0c;位长度选择了9位。因为要奇偶校验&#xff0c;要选择9位。但是接收有用数据只用到1个字节。 问题原因&#xff1a; 所以串口接收时会把下一个数据更改
阅读更多...
卫星授时服务器，单北斗授时服务器，北斗卫星时钟服务器

卫星授时服务器，单北斗授时服务器，北斗卫星时钟服务器

当前NTP授时服务器已经实现内部的元器件及芯片实现采用国产化&#xff0c;已经证明了国产产品已经摆脱需要依靠进口元器件及芯片才能实现的产品研发、也证明了大国崛起。下来我们来分析下国产化服务器具备的优势。 1、采用国产操作系统&#xff1a;使用国产化系统Linux更加可靠…
阅读更多...
Windows11免密码自动登录

Windows11免密码自动登录

按winR&#xff0c;打开运行&#xff0c;输入Control Userpasswords2&#xff0c;打开用户账户。 打开该设置&#xff0c;取消选中该选项&#xff0c;点击应用&#xff0c;输入想要自动登录的账户和密码&#xff0c;即可开机后自动登录Windows。 若此界面无该选项&#xff0c;…
阅读更多...
C++使用开源ConcurrentQueue库处理自定义业务数据类

C++使用开源ConcurrentQueue库处理自定义业务数据类

ConcurrentQueue开源库介绍 ConcurrentQueue是一个高性能的、线程安全的并发队列库。它旨在提供高效、无锁的数据结构&#xff0c;适用于多线程环境中的数据交换。concurrentqueue 支持多个生产者和多个消费者&#xff0c;并且提供了多种配置选项来优化性能和内存使用。 Conc…
阅读更多...
中仕公考：2025年省考可以开始准备了!

中仕公考：2025年省考可以开始准备了!

“各省公务员考试”&#xff0c;是选拔和招录公务员的一种重要方式。该考试由各省级主管部门统一安排&#xff0c;编制归属于各个省份。 考试时间 各省的考试时间有所不同&#xff0c;但通常省联考的时间一般安排在3-5月之间。 户籍限制 部分岗位对考生的户籍有限制&#x…
阅读更多...
保姆级教程,免费短链平台

保姆级教程,免费短链平台

神行短链 开源代码: https://github.com/EASTCATV/openShortLink.git 保姆级教程,5分钟打造属于自己的短链 免费短链平台 免费使用 短链生成 免费使用 地址: short.godsdo.com short.godsdo.com 打包命令 sbt clean && sbt packagedocker run -d \ --name shot…
阅读更多...
三十六、Python基础语法（JSON操作）

三十六、Python基础语法（JSON操作）

JSON&#xff08;JavaScript Object Notation&#xff09;是一种基于文本&#xff0c;轻量级的数据交换格式。它易于人阅读和编写&#xff0c;同时也易于机器解析和生成&#xff0c;在自动化测试中经常用来存放测试数据。 JSON的特点&#xff1a; 基于文本&#xff0c;不包含图…
阅读更多...
linux基础-完结（详讲补充）

linux基础-完结（详讲补充）

linux基础-完结 一、Linux目录介绍 二、基础命令详细讲解 1. ls&#xff08;列出目录内容&#xff09; 2. cd&#xff08;更改目录&#xff09; 3. clear&#xff08;清除终端屏幕&#xff09; 4. pwd(显示你当前所在的目录) 5. vim(文本编辑器) 6. touch&#xff08;创…
阅读更多...
【SAP】关于权限的继承

【SAP】关于权限的继承

关于权限的父role和子role的权限继承&#xff0c;既可以 从子role主动去父role那里“取”。从父role“推”到子role 我自己之前一直用的是方法1&#xff0c;但由于子role很多&#xff0c;一个一个手工维护花了不少时间。 后来得知有方法2&#xff0c;特此测试。 我准备了父R…
阅读更多...
信息安全数学基础（46）域和Galois理论

信息安全数学基础（46）域和Galois理论

域详述 定义&#xff1a; 域是一个包含加法、减法、乘法和除法&#xff08;除数不为零&#xff09;的代数结构&#xff0c;其中加法和乘法满足交换律、结合律&#xff0c;并且乘法对加法满足分配律。同时&#xff0c;域中的元素&#xff08;通常称为数&#xff09;在加法和乘法…
阅读更多...
时序约束进阶五：Set_Max_Delay与Set_Min_Delay详解

时序约束进阶五：Set_Max_Delay与Set_Min_Delay详解

目录 一、背景 二、Max/Min_delay约束 2.1 约束设置参数 2.2 约束说明 三、场景说明 3.1 路径分段 3.1.1 无效的约束对象 3.1.2 设计代码 3.2 有效的约束对象 3.3 datapath only 3.3.1 工程设计 3.3.2 datapath only报告 3.4 clock group约束优先级 3.4.1 MAX/MIN…
阅读更多...
搭建实验仪器知识库：从产品手册到智慧资源的飞跃

搭建实验仪器知识库：从产品手册到智慧资源的飞跃

在科研、教学及工业生产领域&#xff0c;实验仪器作为探索未知、验证理论、提升效率的重要工具&#xff0c;其重要性不言而喻。然而&#xff0c;随着技术的不断进步和仪器的日益复杂化&#xff0c;如何高效、准确地使用这些仪器成为了科研人员、技术人员及学生面临的共同挑战。…
阅读更多...
OA项目 python + vue3

OA项目 python + vue3

准备工作 创建django项目 在setting.py进行数据库的配置&#xff1a; DATABASES {default: {ENGINE: django.db.backends.mysql,NAME: , #数据库名字USER: , #连接的数据库的用户名PASSWORD: ,HOST: 127.0.0.1,PORT: 3306,} }安装app&#xff1a; rest_framwork: 关闭csrf…
阅读更多...
婚礼纪 9.5.57 | 解锁plus权益的全能结婚助手，一键生成结婚请柬

婚礼纪 9.5.57 | 解锁plus权益的全能结婚助手，一键生成结婚请柬

婚礼纪是一款结婚服务全能助手&#xff0c;深受9000万新人信赖的一站式结婚服务平台。解锁plus权益后&#xff0c;用户可以享受部分VIP会员功能。应用提供了丰富的结婚筹备工具和服务&#xff0c;包括一键生成结婚请柬、婚礼策划、婚纱摄影、婚宴预订等。婚礼纪旨在为新人提供全…
阅读更多...
树形结构数据

树形结构数据

树形结构数据 树形结构数据是一种基础且强大的数据结构&#xff0c;广泛应用于计算机科学和软件开发的各个领域。它模拟了自然界中树的层级关系&#xff0c;通过节点和它们之间的连接来组织数据。在本文中&#xff0c;我们将深入探讨树形结构数据的概念、特点、类型以及它们在…
阅读更多...
洛古---越狱问题【快速幂】

洛古---越狱问题【快速幂】

今天和大家讲一个洛古的算法题&#xff0c;我觉得还是比较有含金量的&#xff0c;今天给大家分享一下 题目描述 监狱有 &#x1d45b;n个房间&#xff0c;每个房间关押一个犯人&#xff0c;有 &#x1d45a; 种宗教&#xff0c;每个犯人会信仰其中一种。如果相邻房间的犯人的宗…
阅读更多...
【论文笔记】Parameter-Efficient Transfer Learning for NLP

【论文笔记】Parameter-Efficient Transfer Learning for NLP

&#x1f34e;个人主页&#xff1a;小嗷犬的个人主页 &#x1f34a;个人网站&#xff1a;小嗷犬的技术小站 &#x1f96d;个人信条&#xff1a;为天地立心&#xff0c;为生民立命&#xff0c;为往圣继绝学&#xff0c;为万世开太平。 基本信息 标题: Parameter-Efficient Tran…
阅读更多...
《PyTorch深度学习快速入门教程》学习笔记（第20周）

《PyTorch深度学习快速入门教程》学习笔记（第20周）

目录 摘要 Abstract 1. 池化层原理 2. 二维池化层 3. 二维最大池化 4. 填充、步幅与多个通道 5. 平均池化层 6. 理论总结 7. 池化层处理数据 8. 池化层处理图片 摘要 本周报的目的在于汇报《PyTorch深度学习快速入门教程》课程第六周的学习成果&#xff0c;主要聚焦于…
阅读更多...
C# 实现对指定句柄的窗口进行键盘输入的实现

C# 实现对指定句柄的窗口进行键盘输入的实现

在C#中实现对指定句柄的窗口进行键盘操作&#xff0c;可以通过多种方式来实现。以下是一篇详细的指南&#xff0c;介绍如何在C#中实现这一功能。 1. 使用Windows API函数 在C#中&#xff0c;我们可以通过P/Invoke调用Windows API来实现对指定窗口的键盘操作。以下是一些关键的…
阅读更多...
c语言简单编程练习10

c语言简单编程练习10

1、typedef和#define的区别 在用作数据类型替换时的区别&#xff1a; #include <stdio.h> #include <unistd.h>typedef char * A; //typedef需要&#xff1b; #define B char *int main(int argc, char *argv[]) {A a,b;B c,d;printf("a_size%ld\n"…
阅读更多...
最新文章

Copyright @ 2022~2023