深入浅出C++ ——二叉搜索树

news/2024/4/19 9:36:44/文章来源:https://blog.csdn.net/weixin_55051736/article/details/127740473

文章目录

  • 一、二叉搜索树概念
  • 二、二叉搜索树操作
    • 1. 二叉搜索树的查找
    • 2. 二叉搜索树的插入
    • 3. 二叉搜索树的删除
  • 三、二叉搜索树的实现
  • 四、二叉搜索树的性能分析

一、二叉搜索树概念

  二叉搜索树又称二叉排序树/二次查找树，它是一棵空树或者是每颗子树都具有以下性质的二叉树

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

在这里插入图片描述

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

二、二叉搜索树操作

1. 二叉搜索树的查找

  • 从根开始比较，查找，比根大则往右边走查找，比根小则往左边走查找。
  • 最多查找高度次，走到到空，还没找到，这个值不存在。

2. 二叉搜索树的插入

  • 树为空，则直接新增节点，赋值给root指针。
  • 树不空，按二叉搜索树性质查找插入位置，插入新节点。

3. 二叉搜索树的删除

  1. 左为空，父亲指向他的右。 也就是说左子节点为空，让它父节点指向该节点的右子节点，再直接删除该节点。
  2. 右为空，父亲指向他的左。 也就是说右子节点为空，让它父节点指向该节点的左子节点，再直接删除该节点。
  3. 左右子节点都不为空时，使用替换法删除

  在第一节的例子中，删除1、4、7、13、14、10节点属于前两种情况，删除3、8、10、6节点属于第三种情况。

替换法删除

  找到左子树的最右节点或者右子树的最左节点，替换该节点赋值给删除节点，直接删除替换节点，因为替换节点没子节点或者只有一个子节点，再归类到前两种情况。

修改

   K模型的搜索二叉树不支持修改，增删查的时间复杂度为O(h)，h是树的高度，最坏的情况是h为N。

三、二叉搜索树的实现

  1. K模型：K模型即只有key作为关键码，结构中只需要存储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> //key
class BSTree
{typedef BSTreeNode<K> Node;
public:bool Insert(const K& key){if (_root == nullptr){_root = new Node(key);return true;}Node* parent = nullptr;	//这里父节点指针给nullptr不会报错，因为考虑极端情况只有一个节点，那也会进入下面的循环中，执行parent = cur;，所以父节点->不会报错Node* cur = _root;while (cur){if (cur->_key < key){parent = cur;cur = cur->_right;}else if (cur->_key > key){parent = cur;cur = cur->_left;}elsereturn false; //不能重复}cur = new Node(key); if (parent->_key < key)parent->_right = cur;elseparent->_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;elsereturn 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						//找到了{//开始删除//1、左为空 ，父亲指向它的右 ，把另一个孩子托管给父亲//2、右为空 ，父亲指向它的左//3、左右都不为空if (cur->_left == nullptr) // 左为空 ，父亲指向它的右{if (cur == _root)//考虑极端情况删除的是_root根节点的情况{_root = cur->_right; //左为空，更新根}else{if (cur == parent->_left) //判断该节点是父亲的左还是右parent->_left = cur->_right;elseparent->_right = cur->_right;}delete cur;cur = nullptr;}else if (cur->_right == nullptr) //右为空 ，父亲指向它的左{if (cur == _root)//考虑极端情况删除的是_root根节点的情况{_root = cur->_left;}else{if (cur == parent->_left)parent->_left = cur->_left;elseparent->_right = cur->_left;}delete cur;cur = nullptr;}else//左右都不为空{//	替换法删除，替换的节点可以是左树的最大节点或者是右树的最小节点//	这里采用 找到右树的最小节点进行替换Node* minParent = cur; //	考虑极端情况，要删除的是根节点，所以minparent不可以为空Node* min = cur->_right;while (min->_left){minParent = min;min = min->_left;}swap(cur->_key, min->_key);if (minParent->_left == min)  //判断minParent和min的关系{minParent->_left = min->_right;}elseminParent->_right = min->_right;delete min;min = nullptr;}return true;}}return false;}void InOrder()//中序遍历打印{_InOrder(_root);//套用了一层，第一次传过去了_root,后面递归就传他的子树cout << endl;}bool FindR(const K& key)//递归版本的查找{return _Find(_root, key);}bool InsertR(const K& key){return _InsertR(_root, key);}bool EraseR(const K& key){return _EraseR(_root, key);}BSTree() = default;//C++11 强制编译器生成默认的构造~BSTree(){_Destsory(_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* copyRoot = new Node(root->_key);copyRoot->_left = _Copy(root->_left);copyRoot->_right = _Copy(root->_right);return copyRoot;}void _Destsory(Node*& root){if (root == nullptr)return;_Destsory(root->_left);_Destsory(root->_right);delete root;root = nullptr;}//_InOrder(_root)   递归调用不能写这个，不然每次传过去都是根节点，只能第一次传递根节点，用一个形参cur来接收根节点，void _InOrder(Node* cur) //递归必须 显示 的传递子树，而在外面调用的时候要传根节点_root，但是拿不到私有的_root。可以写一个getroot函数去拿到_root，或者像这样{if (cur == nullptr)return;_InOrder(cur->_left);cout << cur->_key << " ";_InOrder(cur->_right);}bool _Find(Node* cur, const K& key){if (cur == nullptr)return false;if (cur->_key < key)return _Find(cur->_right, key);else if (cur->_key > key)return _Find(cur->left, key);elsereturn true; //return true 按顺序依次从开辟的栈帧返回到最外层}bool _InsertR(Node*& cur, const K& key){if (cur == nullptr){cur = new Node(key); //cur是一个局部变量，所以要用引用return true;}if (cur->_key < key)return _InsertR(cur->_right, key);else if (cur->_key > key)return	_InsertR(cur->_right, key);elsereturn false; //天然去重}bool _EraseR(Node*& cur, const K& key){if (cur == nullptr)return false;if (cur->_key < key)return _EraseR(cur->_right, key);else if (cur->_key > key)return _EraseR(cur->_left, key);else  //删除{Node* del = cur;if (cur->_left == nullptr) //左为空{cur = cur->_right;     }else if (cur->_right == nullptr) //右为空{cur = cur->_left;}else              //左右都不为空{//找右树的最左节点Node* min = cur->_right;while (min->_left){min = min->_left;}swap(cur->_key, min->_key);return _EraseR(cur->_right, key); //从这个点的右树开始删除key}delete del;del = nullptr;return true;}}Node* _root = nullptr;
};

应用：

int main()
{BSTree<int> t;int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };for (auto& e : a){t.Insert(e);}//排序+去重t.InOrder(); t.Erase(3);t.InOrder();
}
  1. KV模型：每一个关键码key，都有与之对应的值Value，即<Key, Value>的键值对。 该种方式在现实生活中也非常常见，例如：统计某物品出现的次数
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: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){//...return true;}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);}
private:Node* _root = nullptr;
};

应用：

int main()
{// 统计水果出现的次数string arr[] = { "苹果", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜",
"苹果", "香蕉", "苹果", "香蕉" };BSTree<string, int> countTree;for (const auto& str : arr){//BSTreeNode<string, int>* ret = countTree.Find(str);auto ret = countTree.Find(str);if (ret == NULL){countTree.Insert(str, 1);}else{ret->_value++;}}countTree.InOrder();
}

四、二叉搜索树的性能分析

  插入和删除操作都必须先查找，查找效率代表了二叉搜索树中各个操作的性能。对有n个结点的二叉搜索树，若每个元素查找的概率相等，则二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数，即结点越深，则比较次数越多。

  但对于同一个关键码集合，如果各关键码插入的次序不同，可能得到不同结构的二叉搜索树

  • 最优情况下，二叉搜索树为完全二叉树，或者接近完全二叉树，其平均比较次数为：log2 N
  • 最差情况下，二叉搜索树退化为单支树，或者类似单支，其平均比较次数为：N

  如果退化成单支树，二叉搜索树的性能就失去了。将二叉搜素树改进为AVL树和红黑树，不论按照什么次序插入关键码，性能都能达到最优。

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

如若内容造成侵权/违法违规/事实不符，请联系dt猫网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

[qiankun]-多页签缓存

[qiankun]-多页签缓存

[qiankun]-多页签缓存环境功能需求多页签缓存方案方案1.主服务进行html替换方案2.微服务vnode 替换方案3.每个微服务都不卸载微服务加载方式的选择微服务的路由路径选择微服务的缓存工具微服务的容器使用tab作为微服务的挂载容器使用微服务路由作为微服务的挂载容器场景描述微服…
阅读更多...
干货解答：如何设置Facebook Messenger 自动回复？

干货解答：如何设置Facebook Messenger 自动回复？

Facebook Messenger 自动回复消息是提升客户体验的有效方法。在本文中&#xff0c;我们将探讨设置Facebook 自动响应和不同的创建方法 Facebook 自动回复。另外&#xff0c;我们准备了一些最受欢迎的 Facebook Messenger 自动回复消息。Facebook Messenger 自动回复&#xff1a…
阅读更多...
https加密原理详解，带你搞懂它为什么比http更安全

https加密原理详解，带你搞懂它为什么比http更安全

文章目录http的缺点对称加密非对称加密数字签名数字证书验证身份数字摘要数字签名验证内容的完整性总结http的缺点 http是超文本传输协议&#xff0c;使用http协议进行通信有如下缺点&#xff1a; http没有提供任何数据加密机制&#xff0c;数据通信使用明文通信&#xff0c;…
阅读更多...
x86架构设备的OpenWrt的空间扩容问题

x86架构设备的OpenWrt的空间扩容问题

openwrt固件是squashfs-combined-efi非exf4格式 直接将原有根分区扩容 用插件是&#xff1a;fdisk,losetup,resize2fs,blkid df -h fdisk -l fdisk /dev/sda //进入fdisk分区管理工具注意fdisk后参数是磁盘名称&#xff0c;是要根据实际情况填写 fdisk /dev/sda //进入fdi…
阅读更多...
JavaEE简单示例——＜select＞中的查询参数传递和结果集封装自动映射关系

JavaEE简单示例——＜select＞中的查询参数传递和结果集封装自动映射关系

简单介绍&#xff1a; 在之前我们在讲SQL映射文件中的映射查询语句的<select>标签的时候&#xff0c;对其中的四个常用属性的讲解并不是那么的透彻&#xff0c;今天就来详细的解释<select>的四个常用属性的具体含义以及<select>标签在进行查询的时候查询参数…
阅读更多...
Sofa-jraft的Rpc调用服务端分析

Sofa-jraft的Rpc调用服务端分析

在sofa-jraft中&#xff0c;关于RPC的服务端是RpcServer在RpcServer中的init方法中&#xff1a;初始化了连接事件监听器&#xff0c;这个里面就是一个map&#xff0c;然后可以添加事件监听的处理器&#xff0c;初始化userProcessors, codec 是一个编码和解码器的工厂&#xff0…
阅读更多...
2022-2023年营销报告（B站平台） | 5大行业势态、流量大盘全景洞察

2022-2023年营销报告（B站平台） | 5大行业势态、流量大盘全景洞察

一直以来&#xff0c;手持高活跃、高粘性用户群体的B站是行业用来观察年轻人消费习惯的重要平台。以至于用户群体的不断壮大带动了B站的商业价值。如今B站的商业舞台越来越大&#xff0c;不断地向外界招手&#xff0c;欢迎更多品牌积极加入到这个千万年轻人聚集的内容社区。为了…
阅读更多...
基于Hibernate对数据库表的单表查询

基于Hibernate对数据库表的单表查询

基于Hibernate对数据库表的单表查询 1.依赖 1.1jar包 1.2配置文件。persistence.xml <?xml version"1.0" encoding"UTF-8"?> <persistence version"2.1"xmlns"http://xmlns.jcp.org/xml/ns/persistence" xmlns:xsi"…
阅读更多...
亲身试验 Outlook防关联方法分享

亲身试验 Outlook防关联方法分享

Outlook在海外的用途是很广泛的&#xff0c;不仅可以用于收发邮件&#xff0c;还可以作为各类第三方网站的登录凭证。所以Microsoft对于Outlook的监管还是比较严格的&#xff0c;跨境卖家大量注册Outlook账号使用的话很容易被检测出关联然后被封号。龙哥针对Outlook防关联的问题…
阅读更多...
【Kubernetes 入门实战课】Day02——初识容器

【Kubernetes 入门实战课】Day02——初识容器

系列文章目录 【Kubernetes 入门实战课】Day01——搭建kubernetes实验环境(一) 文章目录系列文章目录前言一、Docker的诞生二、Docker的形态1、Docker Desktop2、Docker Engine二、Docker的安装1、服务器连接外网安装2、服务器不通外网三、Docker的使用三、Docker的架构总结前…
阅读更多...
阿里云物联网平台设备模拟器

阿里云物联网平台设备模拟器

在使用阿里云物联网平台过程中&#xff0c;如果开始调试没有实际的物理设备&#xff0c;可以考虑在阿里云物联网平台使用官方自带的模拟器进行调试。不过也可以通过叶帆科技开发的阿里云物联网平台设备模拟器AliIoTSimulator进行调试&#xff0c;AliIoTSimulator可以独立运行&a…
阅读更多...
stm32 VM8978 音乐播放

stm32 VM8978 音乐播放

一、WAV文件 1、WAV文件简介 2、WAV文件的解析 二、WM8978 1、WM8978介绍 2、WM8978特点 3、WM8978接口 4、WM8978框架 5、 WM8978 寄存器 三、IIS详解 1、IIS介绍 2、 IIS 的特点 3、IIS框架 4、 音频协议 5、 IIS Philips 标准 6、 IIS 时钟 四、音乐播放硬件…
阅读更多...
ChatGPT三个关键技术

ChatGPT三个关键技术

情景学习&#xff08;In-context learning&#xff09; 对于一些LLM没有见过的新任务&#xff0c;只需要设计一些任务的语言描述&#xff0c;并给出几个任务实例&#xff0c;作为模型的输入&#xff0c;即可让模型从给定的情景中学习新任务并给出满意的回答结果。这种训练方式能…
阅读更多...
双检测人脸防伪识别方法(活体检测+人脸识别+关键点检测+人像分割)

双检测人脸防伪识别方法(活体检测+人脸识别+关键点检测+人像分割)

双检测人脸防伪识别=人脸检测+活体检测+人脸识别 1.人脸关键点+语义分割 使用mediapipe进行视频人脸关键点检测和人像分割： import time import cv2 import mediapipe as mp import numpy as npmp_drawing = mp.solutions.drawing_utils mp_drawing_styles = mp.solution…
阅读更多...
量化交易-单因子分析-alphalens

量化交易-单因子分析-alphalens

1. 数据准备 1.1 计算因子IC重要函数 def get_clean_factor_and_forward_returns(factor,prices,groupbyNone,binning_by_groupFalse,quantiles5,binsNone,periods(1, 5, 10),filter_zscore20,groupby_labelsNone,max_loss0.35,zero_awareFalse,cumulative_returnsTrue)facto…
阅读更多...
【C语言】-程序编译的环境和预处理详解-让你轻松理解程序是怎么运行的！！

【C语言】-程序编译的环境和预处理详解-让你轻松理解程序是怎么运行的！！

作者&#xff1a;小树苗渴望变成参天大树 作者宣言&#xff1a;认真写好每一篇博客 作者gitee:gitee 如 果 你 喜 欢 作 者 的 文 章 &#xff0c;就 给 作 者 点 点 关 注 吧&#xff01; 程序的编译前言一、 程序的翻译环境和执行环境二、 详解翻译环境2.1编译环境2.1.1预编…
阅读更多...
民锋国际期货：2023，既艰难又充满希望，既纷乱又有无数机会。

民锋国际期货：2023，既艰难又充满希望，既纷乱又有无数机会。

不管是官方还是民间&#xff0c;各种信号都表明&#xff0c;2023年是一个拼经济的年份。 通货膨胀带来的需求量的增加&#xff0c;与中国经济高速发展带来的供给量增加&#xff0c;二者共同构成了我们的物价。 做一个长期主义者&#xff0c;做一个坚定看好中国未来的人&#…
阅读更多...
MapBox动态气泡图渲染教程

MapBox动态气泡图渲染教程

先来看效果： 视频效果： 屏幕录制2023-02-22 15.34.57 首先我们来介绍一下思路。对于mapbox和openlayers这样的框架来讲，气泡图中的气泡本质上就是一个div，就是将一个dom元素追加到canvas上的固定位置而已。 在mapbox中有marker的概念，官网也有示例： Attach a popup to …
阅读更多...
二叉树——路径总和

二叉树——路径总和

路径总和 链接 给你二叉树的根节点 root 和一个表示目标和的整数 targetSum 。判断该树中是否存在 根节点到叶子节点 的路径&#xff0c;这条路径上所有节点值相加等于目标和 targetSum 。如果存在&#xff0c;返回 true &#xff1b;否则&#xff0c;返回 false 。 叶子节点…
阅读更多...
数据库及缓存之MySQL（一）

数据库及缓存之MySQL（一）

思维导图 常见知识点 1.mysql存储引擎&#xff1a; 2.innodb与myisam区别&#xff1a; 3.表设计字段选择&#xff1a; 4.mysql的varchar(M)最多存储数据&#xff1a; 5.事务基本特性&#xff1a; 6.事务并发引发问题&#xff1a; 7.mysql索引&#xff1a; 8.三星索引&#xf…
阅读更多...
推荐文章
最新文章

Copyright @ 2022~2023