数据结构---二叉搜索树（二叉排序树）

 

什么是二叉排序树

二叉搜索树又是二叉排序树，当我们的是一颗空树或者具有以下性质时：

  1. 左子树不为空，左子树上的值都小于我们的根节点上的值。
  2. 右子树不为空时，右子树上的值都大于我们的根节点上的值
  3. 左右子树都是二叉搜索树（二叉排序树）。

我们的二叉搜索树可以支持插入想同的值，也可以不支持，这分情况的。我们的set和map是 不支持我们的插入相同的值的，但是我们的multiset和multimap 是支持可以插入相同的值的。 他们的底层是二叉搜索树

 二叉搜索树：

 性能分析

 我们的单独的二叉树，不具有某些性质的话，是没有很大的意义的，因为他的结构比较复杂。

而我们的二叉搜索树，左边是比根小的，右边是比根大的。当我们去中序遍历的时候，就可以是有序的。

  • 最优情况下，⼆叉搜索树为完全⼆叉树(或者接近完全⼆叉树)，其⾼度为：O(log2 N)、
  • 最差情况下，⼆叉搜索树退化为单⽀树(或者类似单⽀)，其⾼度为：O(log2 N ) 
  •  所以综合⽽⾔⼆叉搜索树增删查改时间复杂度为：O(N)

我们的二叉搜索树很受我们的插入的顺序影响，当那个我们的插入顺序不一样，我们的二叉搜索树的结构也是不一样的。 

这个明显是不能满足的我们的需求的，而平衡⼆ 叉搜索树AVL树和红⿊树，才能适⽤于我们在内存中存储和搜索数据。

我们的二分查找也可以实现我们的logN级别的查找效率，但是它是由条件的，

  • 他必须是在有序的情况下
  • 其次他要满足 随机访问，如果你所使用的容器不支持随机访问，是不可以使用我们的二分查找的

 当我们的二叉搜索树的值都在一段时就会严重影响我们的搜索效率。如果我们是使用递归可能会导致栈溢出的分险。

 二叉搜索树的实现

我们的每一个节点我们可以用一个类来分装一下，

我们的二叉搜索树，这个类里面用另一个类来封装起来，里面的成员变量就是我们的根节点。

用模板的话 可以让我们存的数据类型多样。

//节点template<class K>struct BSTNode{K _key;BSTNode<K>* _left;BSTNode<K>* _right;BSTNode(const K& key):_key(key), _left(nullptr), _right(nullptr){}};// Binary Search Tree// Keytemplate<class K>class BSTree{//typedef BSTNode<K> Node;using Node = BSTNode<K>;private:Node* _root = nullptr;};

插入

  1. 树为空，则直接新增结点，赋值给root指针、
  2.  树不空，按⼆叉搜索树性质，插⼊值⽐当前结点⼤往右⾛，插⼊值⽐当前结点⼩往左⾛，找到空位 置，插⼊新结点。
  3.  如果⽀持插⼊相等的值，插⼊值跟当前结点相等的值可以往右⾛，也可以往左⾛，找到空位置，插 ⼊新结点。（要注意的是要保持逻辑⼀致性，插⼊相等的值不要⼀会往右⾛，⼀会往左⾛。

例子：当我们么插入这个数组里面的元素时： int a[] = {8, 3, 1, 10, 6, 4, 7, 14, 13};

 

我们直接利用循环来处理，当时我们再走的时候，找到空节点的时候，还需要我们知道我们的父亲节点在哪。这样我们才能连接起来。，

代码：

        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;}

删除（难点）

⾸先查找元素是否在⼆叉搜索树中，如果不存在，则返回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){if (cur == _root){_root = cur->_right;}else{if (parent->_left == cur){parent->_left = cur->_right;}else{parent->_right = cur->_right;}}delete cur;}else if (cur->_right == nullptr){if (cur == _root){_root = cur->_left;}else{// 右为空if (parent->_left == cur){parent->_left = cur->_left;}else{parent->_right = cur->_left;}}delete cur;}else{// 左右都不为空// 右子树最左节点Node* replaceParent = cur;Node* replace = cur->_right;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;}

虽然我们在找替换的节点的时候一直在往一边走，但是我们人就要后面的判断

if (replaceParent->_left == replace)
           replaceParent->_left = replace->_right;
 else
           replaceParent->_right = replace->_right;

因为有一种情况是不满足的需要我们去进行判断；而且我们的replaceParent也不能再初始化的时候给nullptr,

查找

  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;}

赋值拷贝

我们的这里的拷贝也是要进行深拷贝的。

代码：

        BSTree(const BSTree& t){_root = Copy(t._root);}private：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;}

析构

我们对于内置类型的，的确是不需要我们去写析构，但是我们这里是一个模板，里面存放的数据类型不止有我们的内置类型的，也会有我们的自定义类型，而且我们这里节点的空间都是动态申请的。

我们通过自己写一个Destory的函数去帮助我们释放空间，因为我们释放空间，也需要我们去利用递归，并需要访问我们的root，在类外不能访问我们的root，所以不好传参数，在要我们的析构去调用。

代码：

       ~BSTree(){Destroy(_root);_root = nullptr;}private:void Destroy(Node* root){if (root == nullptr)return;Destroy(root->_left);Destroy(root->_right);delete root;}

中序遍历

对于我们的中序遍历我们不能在类外访问我们的root，所以需要我们去写一个已经在类内实现的中序遍历_Inorder，我们再用Inorder里面调用这个函数，利用我们的封装的思想，我们的中序遍历可以实现有序。

代码：

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

 完整的实现代码

template<class K>struct BSTNode{K _key;BSTNode<K>* _left;BSTNode<K>* _right;BSTNode(const K& key):_key(key), _left(nullptr), _right(nullptr){}};// Binary Search Tree// Keytemplate<class K>class BSTree{//typedef BSTNode<K> Node;using Node = BSTNode<K>;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->_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;}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->_right;}else if (cur->_key > key){parent = cur;cur = cur->_left;}else{// 删除// 左为空if (cur->_left == nullptr){if (cur == _root){_root = cur->_right;}else{if (parent->_left == cur){parent->_left = cur->_right;}else{parent->_right = cur->_right;}}delete cur;}else if (cur->_right == nullptr){if (cur == _root){_root = cur->_left;}else{// 右为空if (parent->_left == cur){parent->_left = cur->_left;}else{parent->_right = cur->_left;}}delete cur;}else{// 左右都不为空// 右子树最左节点Node* replaceParent = cur;Node* replace = cur->_right;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;}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;};

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

key搜索场景

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

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

key/value搜索场景：

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

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

我们的额key的情况和key、value的代码基本一样。

代码：

template<class K, class V>struct BSTNode{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){}};// Binary Search Tree// Key/valuetemplate<class K, class V>class BSTree{//typedef BSTNode<K> Node;using Node = BSTNode<K, V>;public:// 强制生成构造BSTree() = default;BSTree(const BSTree& t){_root = Copy(t._root);}BSTree& operator=(BSTree tmp){swap(_root, tmp._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 (cur == _root){_root = cur->_right;}else{if (parent->_left == cur){parent->_left = cur->_right;}else{parent->_right = cur->_right;}}delete cur;}else if (cur->_right == nullptr){if (cur == _root){_root = cur->_left;}else{// 右为空if (parent->_left == cur){parent->_left = cur->_left;}else{parent->_right = cur->_left;}}delete cur;}else{// 左右都不为空// 右子树最左节点Node* replaceParent = cur;Node* replace = cur->_right;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;}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/146289.html

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

相关文章

Java异常架构与异常关键字

Java异常架构与异常关键字

1. Java异常简介 Java 异常是 Java 提供的一种识别及响应错误的一致性机制。 Java 异常机制可以使程序中异常处理代码和正常业务代码分离&#xff0c;保证程序代码更加优雅&#xff0c;并提高程 序健壮性。在有效使用异常的情况下&#xff0c;异常能清晰的回答 what, where,…
阅读更多...
2023北华大学程序设计新生赛部分题解

2023北华大学程序设计新生赛部分题解

时光如流水般逝去&#xff0c;我已在校园中奋战大二&#xff01;(≧▽≦) 今天&#xff0c;静静回顾去年的新生赛&#xff0c;心中涌起无尽感慨&#xff0c;仿佛那段青春岁月如烟花般绚烂。✧&#xff61;(≧▽≦)&#xff61;✧ 青春就像一场燃烧的盛宴&#xff0c;激情澎湃&…
阅读更多...
《高等代数》线性相关和线性无关（应用）

《高等代数》线性相关和线性无关（应用）

说明&#xff1a;此文章用于本人复习巩固&#xff0c;如果也能帮到大家那就更加有意义了。 注&#xff1a;1&#xff09;线性相关和线性无关的证明方法中较为常用的方法是利用秩和定义来证明。 2&#xff09;此外&#xff0c;线性相关和线性无关的证明常常也会用到反证法。 3&…
阅读更多...
2.5 数据库索引机制

2.5 数据库索引机制

我们往数据表里面保存数据记录越来越多&#xff0c;一旦达到上千万条&#xff0c;那怎么提高检索速度就需要认真考虑了。我们打开手机上的APP都希望能快些加载出内容&#xff0c;这里的因素有很多&#xff0c;但是如何减少数据查找的时间是其中的重要一环。索引机制就是提升数据…
阅读更多...
怎么给视频加字幕？6种给视频加字幕最简单的方法，不怕你学不会！

怎么给视频加字幕？6种给视频加字幕最简单的方法，不怕你学不会！

在这个快节奏的时代&#xff0c;越来越多的人会在公共场所观看视频&#xff0c;但为了不影响其它人&#xff0c;大多数人往往会将声音关闭。统计数据显示&#xff0c;高达69%的人在这样的环境中会静音观看视频&#xff0c;而有字幕的情况下&#xff0c;80%的人更倾向于完整观看…
阅读更多...
刷题训练之栈

刷题训练之栈

> 作者&#xff1a;დ旧言~ > 座右铭&#xff1a;松树千年终是朽&#xff0c;槿花一日自为荣。 > 目标&#xff1a;熟练掌握字符串算法。 > 毒鸡汤&#xff1a;学习&#xff0c;学习&#xff0c;再学习 ! 学&#xff0c;然后知不足。 > 专栏选自&#xff1a;刷题…
阅读更多...
C++之spring

C++之spring

C之spring string类对象的访问及遍历操作 operator[] 返回pos位置的字符&#xff0c;const string类对象调用 这是一个既可以写也可以读的库函数&#xff0c;const修饰的内容是不可以更改的&#xff0c;所以是读 C类与对象里要想普通对象和const修饰的对象同时重载 第二种访…
阅读更多...
2024华为杯研究生数学建模，代码思路和参考文章

2024华为杯研究生数学建模，代码思路和参考文章

F题X射线脉冲星光子到达时间建模&#xff0c; E题高速公路应急车道紧急启用模型&#xff0c; D题大数据驱动的地理综合问題&#xff0c; C题数据驱动下磁性元件的磁芯损耗建模&#xff0c; B题W LAN 组网中网络吞吐量建模&#xff0c; A题风电场有功功率优化分配&#xff…
阅读更多...
Python画笔案例-057 绘制蜘蛛网

Python画笔案例-057 绘制蜘蛛网

1、绘制蜘蛛网 通过 python 的turtle 库绘制 蜘蛛网&#xff0c;如下图&#xff1a; 2、实现代码 绘制蜘蛛网&#xff0c;以下为实现代码&#xff1a; """蜘蛛网.py """ import turtledef draw_circle(pos,r):"""pos:圆的中心点…
阅读更多...
力扣最热一百题——搜索二维矩阵

力扣最热一百题——搜索二维矩阵

目录 题目链接&#xff1a;240. 搜索二维矩阵 II - 力扣&#xff08;LeetCode&#xff09; 题目描述 解法一&#xff1a;暴力不解释 Java写法&#xff1a; 运行时间 C写法&#xff1a; 运行时间 时间复杂度以及空间复杂度 解法二&#xff1a;利用自带的大小关系进行Z型走…
阅读更多...
电商ISV 电商SaaS 是什么

电商ISV 电商SaaS 是什么

Independent Software Vendors的英文缩写&#xff0c;意为“独立软件开发商” 软件即服务(SaaS) 指一种基于云技术的软件交付模式 订阅收费 这些公司叫做ISV软件供应商&#xff0c;通过SaaS服务交付收费 为什么会有电商ISV 从商家角度划分&#xff1a;有独立品牌商家、大商…
阅读更多...
叉车限速器外接LED屏，监督厂区安全，让速度慢下来！

叉车限速器外接LED屏，监督厂区安全，让速度慢下来！

叉车限速器外接LED屏&#xff0c;可实时显示当前叉车行驶中的速度&#xff0c;单/双面电子显示屏供用户选择&#xff0c;方便企业人员监控司机当前行驶速度&#xff0c;当速度超过指定值时&#xff0c;叉车速度报警系统发出声光警示&#xff0c;提醒行人、司机&#xff0c;超速…
阅读更多...
最新适用：关于夫妻共同债务的裁判规则+司法观点

最新适用：关于夫妻共同债务的裁判规则+司法观点

✦ 重点条文 ✦ 《民法典》第一千零六十四条 夫妻双方共同签名或者夫妻一方事后追认等共同意思表示所负的债务&#xff0c;以及夫妻一方在婚姻关系存续期间以个人名义为家庭日常生活需要所负的债务&#xff0c;属于夫妻共同债务。 夫妻一方在婚姻关系存续期间以个人名义超…
阅读更多...
新手入门：小程序架构快速上手

新手入门：小程序架构快速上手

目录 新建项目和配置 项目基本结构 新建小程序页面 修改项目首页 全局配置 窗口 tabBar 页面配置 小程序基本语法 wxml 数据绑定 条件渲染 列表渲染 wxss wxss 对比 css rpx import 全局样式和局部样式 js wxs 数据请求 get和post请求 小程序和跨域 小程…
阅读更多...
特征工程与交叉验证在机器学习中的应用

特征工程与交叉验证在机器学习中的应用

数据入口&#xff1a;学生考试表现影响因素数据集 - Heywhale.com 本数据集提供了关于影响学生考试成绩的多种因素的全面概述。数据集包含了有关学习习惯、出勤率、家长参与、资源获取等方面的信息。 数据说明 字段名说明Hours_Studied每周学习的小时数Attendance出勤率&…
阅读更多...
30个GPT提示词天花板，一小时从大纲到终稿

30个GPT提示词天花板，一小时从大纲到终稿

PROMPT 1 中文&#xff1a;构建研究背景与意义&#xff0c;阐述研究问题的紧迫性和重要性。 English: Establish the research background and significance, elucidating the urgency and importance of the research question. 中文&#xff1a;设计研究目的与目标&#xff…
阅读更多...
深入解析：HTTP 和 HTTPS 的区别

深入解析：HTTP 和 HTTPS 的区别

网络安全问题正变得日益重要&#xff0c;而 HTTP 与 HTTPS 对用户数据的保护十分关键。本文将深入探讨这两种协议的特点、工作原理&#xff0c;以及保证数据安全的 HTTPS 为何变得至关重要。 认识 HTTP 与 HTTPS HTTP 的工作原理 HTTP&#xff0c;全称超文本传输协议&#xf…
阅读更多...
go 安装依赖超时

go 安装依赖超时

一、配置代理 go env -w GO111MODULEon go env -w GOPROXYhttps://goproxy.io,direct go get github.com/unidoc/unioffice
阅读更多...
对象关系映射ORM

对象关系映射ORM

目录 ORM【重要】 1、 什么是ORM 2、 实体类 3、 ORM改造登录案例 ORM【重要】 1、 什么是ORM 目前使用JDBC完成了CRUD,但是现在是进行CRUD,增删改方法要设计很多参数,查询的方法需要设计集合才能返回. 在实际开发中,我们需要将零散的数据封装到对象处理. ORM (Object Rela…
阅读更多...
十九、石英晶体振荡电路

十九、石英晶体振荡电路

石英晶体振荡电路 1、石英晶体的特点、等效电路、特性曲线; 2、石英晶体振动器的特点&#xff0c; 3、石英晶体振动器的振荡频率
阅读更多...
最新文章

Copyright @ 2022~2023