当前位置： 首页 > news >正文

【C++第十七章】二叉搜索树

news 2025/8/22 22:45:33

【C++第十七章】二叉搜索树

二叉搜索树的介绍🧐

  二叉搜索树又称二叉排序树，它可能是空树，也可能是具有以下性质的二叉树：

  1. 若它的左子树不为空，则左子树上的所有节点的值小于根节点的值
  2. 若它的右子树不为空，则右子树上的所有节点的值大于根节点的值
  3. 它的左右子树也分别为二叉搜索树

  如我们将如下数组放入二叉搜索树中，会得到这样的结构，可以发现，它的中序是有序排列的。

int a[] = {8, 3, 1, 10, 6, 4, 7, 14, 13};

image-20241006113049718

二叉搜索树的查找🧐

  从根开始比较查找，比根大就往右走，比根小就往左走，最多走树的高度次，如果走到空了还没找到，就是不存在。

参考代码：

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

二叉搜索树的插入🧐

  当树为空时，直接增加新的节点，赋值给root指针，如果不为空，则按性质插入，小于根在左，大于根在右。

image-20241006113802253

参考代码

bool Insert(const K& key)
{if (_root == nullptr) //第一次插入{_root = new Node(key);return true;}Node* parent = nullptr;Node* cur = _root;while (cur){parent = cur;if (cur->_key < key){cur = cur->_right;}else if (cur->_key > key){cur = cur->_left;}else{return false;}}//链接cur = new Node(key);if (parent->_key < key){parent->_right = cur;}else if (parent->_key > key){parent->_left = cur;}return true;
}

二叉搜索树的删除🧐

  首先查找元素是否存在，不存在就直接返回，存在则要分四种情况分析：

  1. 要删除的节点没有孩子节点
  2. 要删除的节点只有左孩子节点
  3. 要删除的节点只有右孩子节点
  4. 要删除的节点有左右孩子节点

  而第一种情况可以和第二种和第三种合并起来，所以真正情况有三种：

  1. 删除该节点且使被删除的节点的双亲节点指向被删除节点的左孩子节点——直接删除
  2. 删除该节点且使被删除的节点的双亲节点指向被删除节点的右孩子节点——直接删除
  3. 在它的右子树中寻找中序下的第一个节点(最小值)，用它的值填补到被删除节点中(交换)，再处理该节点的删除——替换法删除

image-20241006114254562

参考代码

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 (cur == parent->_left){parent->_left = cur->_right;}else{parent->_right = cur->_right;}}}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;}}}else //左右都不为空{//右树的最小结点(最左结点)Node* subLeft = cur->_right;Node* parent = cur; //parent直接等于cur，防止删除根时parent为空导致交换出错while (subLeft->_left){parent = subLeft;subLeft = subLeft->_left;}swap(cur->_key, subLeft->_key); //找到了就交换if (subLeft == parent->_left) //看节点在左边还是右边{parent->_left = subLeft->_right;}else{parent->_right = subLeft->_right;}}return true;}}return false;
}

全部代码🧐

namespace key
{template<class K>struct BSTreeNode{BSTreeNode<K>* _left;BSTreeNode<K>* _right;K _key;BSTreeNode(const K& key):_left(nullptr), _right(nullptr), _key(key){}};template<class K>class BSTree{typedef BSTreeNode<K> Node;public:BSTree() = default; //c++11强制生成默认构造bool Insert(const K& key){if (_root == nullptr){_root = new Node(key);return true;}Node* parent = nullptr;Node* cur = _root;while (cur){parent = cur;if (cur->_key < key){cur = cur->_right;}else if (cur->_key > key){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 (cur == parent->_left){parent->_left = cur->_right;}else{parent->_right = cur->_right;}}}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;}}}else //左右都不为空{//右树的最小结点(最左结点)Node* subLeft = cur->_right;Node* parent = cur; //parent直接等于cur，防止删除根时parent为空导致交换出错while (subLeft->_left){parent = subLeft;subLeft = subLeft->_left;}swap(cur->_key, subLeft->_key);if (subLeft == parent->_left){parent->_left = subLeft->_right;}else{parent->_right = subLeft->_right;}}return true;}}return false;}~BSTree(){cout << "~destory" << endl;Destory(_root);}BSTree(const BSTree<K>& t){_root = Copy(t._root);}BSTree<K>& operator=(BSTree<K> t){swap(_root, t._root);return *this;}private:Node* Copy(Node* root){if (root == nullptr)return nullptr;Node* NewRoot = new Node(root->_key);NewRoot->_left = Copy(root->_left);NewRoot->_right = Copy(root->_right);return NewRoot;}void Destory(Node*& root){if (root == nullptr)return;Destory(root->_left);Destory(root->_right);delete root;root = nullptr;}Node* _root = nullptr;};
}

二叉搜索树的应用——K模型、KV模型🧐

  K模型：K模型即只有Key作为关键码，结构中只需要存储Key即可。比如给一个名字判断他在不在名单中。在上面介绍的二叉搜索树就是K模型。

  KV模型：让每一个Key都有一个对应的Value，即**<Key,Value>**的键值对。比如词典的中英对应，输入英文可以直接查找到对应的中文意思，再比如统计次数，可以快速找到一个单词出现的次数。

  KV模型只需要在K模型上进行修改即可。

namespace kv
{template<class K, class V>struct BSTreeNode{BSTreeNode<K, V>* _left;BSTreeNode<K, V>* _right;K _key;V _value;BSTreeNode(const K& key, const V& value):_left(nullptr), _right(nullptr), _key(key), _value(value){}};template<class K, class V>class BSTree{typedef BSTreeNode<K, V> Node;public:BSTree() = default; //c++11强制生成默认构造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){parent = cur;if (cur->_key < key){cur = cur->_right;}else if (cur->_key > key){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 (cur == parent->_left){parent->_left = cur->_right;}else{parent->_right = cur->_right;}}}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;}}}else //左右都不为空{//右树的最小结点(最左结点)Node* subLeft = cur->_right;Node* parent = cur; //parent直接等于cur，防止删除根时parent为空导致交换出错while (subLeft->_left){parent = subLeft;subLeft = subLeft->_left;}swap(cur->_key, subLeft->_key);if (subLeft == parent->_left){parent->_left = subLeft->_right;}else{parent->_right = subLeft->_right;}}return true;}}return false;}private:void Destory(Node*& root){if (root == nullptr)return;Destory(root->_left);Destory(root->_right);delete root;root = nullptr;}Node* _root = nullptr;};
}

Pasted image 20240902163557

二叉搜索树的性能分析🧐

  二叉搜索树插入与删除都需要先进行查找，最优情况下，二叉搜索树为完全二叉树，时间复杂度为O(logN)。最坏情况下，二叉搜索树为单支树，时间复杂度为O(N)。当为单支树时，二叉搜索树的性能优势就没有了，所以我们后续会学习AVL树和红黑树，对二叉搜索树进行优化。image-20241006122637462

结尾👍

  以上便是二叉搜索树的全部内容，如果有疑问或者建议都可以私信笔者交流，大家互相学习，互相进步！🌹

http://www.lryc.cn/news/456510.html

相关文章：

  • Springboot 文件上传
  • 简单认识redis-5 jdbc 与 jedis 使用的区别
  • Unity3d动画插件DoTween使用指南
  • 学习函数知识
  • 案例-表白墙简单实现
  • 和鲸科技创始人范向伟：拐点即将来临，AI产业当前的三个瓶颈
  • 基于函数计算FC 部署 ComfyUI实现AI生图 的优势
  • 瑞萨IDE：CS+ for CC编译过程中执行脚本文件
  • 在 CentOS 上安装 Docker 的步骤
  • 【C#生态园】探索地理信息系统软件套件与库：功能、API和应用
  • Jupyter的使用分享
  • 24龙信比赛复现
  • PHP反射机制
  • 使用阿里云试用资源快速部署web应用-dofaker为例
  • 需求11——解决字段无法清空的两个小bug
  • mysql学习教程，从入门到精通，SQL 创建索引(CREATE INDEX 语句)（35）
  • Pikachu-Cross-Site Scripting-DOM型xss_x
  • Pikachu-Cross-Site Scripting-xss之htmlspecialchars
  • CSS基础中padding详解
  • OpenGL笔记十九之相机系统
  • P-Tuning v2：一种普遍有效的提示调整方法
  • 微信小程序启动不起来，报错凡是以~/包名/*.js路径的文件，都找不到，试过网上一切方法，最终居然这么解决的，【避坑】命运的齿轮开始转动
  • C#串口温度读取
  • 2.5 Spring Boot整合Spring MVC框架
  • Java 归并排序
  • 20241008深度学习动手篇
  • 对序列化反序列化在项目中的使用优化
  • 查看 git log的过程中看到 :说明日志输出可能超出屏幕大小，系统进入了分页模式
  • Linux--信号量详解
  • 【重学 MySQL】五十一、更新和删除数据