【C++】15.二叉搜索树

news/2024/9/18 20:56:27/ 标签: c++, 开发语言, c语言

一、二叉搜索树的概念

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

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

二、二叉搜索树的分析与实现

我们接下来的操作以这张图为例：
在这里插入图片描述

2.1 查找

  • 从根开始比较，查找，比根大则往右边走查找，比根小则往左边走查找
  • 最多查找高度次，走到到空，还没找到，这个值不存在
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;
}

2.2 插入

  • 树为空，则直接新增节点，赋值给root指针
  • 树不空，按二叉搜索树性质查找插入位置，插入新节点
bool Insert(const K& key)
{if (root == nullptr){root = new Node(key);return true;}Node* cur = root;Node* parent = nullptr;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 (cur->_key < parent->_key)parent->_left = cur;elseparent->_right = cur;return true;}

2.2 删除

首先查找元素是否在二叉搜索树中，如果不存在，则返回, 否则要删除的结点可能分下面四种情况：

  1. 要删除的结点无孩子结点
  2. 要删除的结点只有左孩子结点
  3. 要删除的结点只有右孩子结点
  4. 要删除的结点有左、右孩子结点

看起来有待删除节点有4中情况，实际情况a可以与情况b或者c合并起来，因此真正的删除过程如下：

  • 删除该结点且使被删除节点的双亲结点指向被删除节点的左孩子结点–直接删除
  • 删除该结点且使被删除节点的双亲结点指向被删除结点的右孩子结点–直接删除
  • 在它的右子树中寻找中序下的第一个结点(关键码最小)，用它的值填补到被删除节点中，再来处理该结点的删除问题–替换法删除
bool erase(const K& key)
{Node* cur = root;Node* parent=nullptr;while (cur){if (cur->_key < key)//小于向右找{parent = cur;cur = cur->_right;}else if (cur->_key > key)//大于向左找{parent = cur;cur = cur->_left;}else//等于就找到{//0-1个孩子的情况//如果左子树为空if(cur->_left==nullptr){//是否删除根节点if (parent == nullptr)root = root->_right;else{//说明cur是他的左子树if (parent->_left == cur)parent->_left = cur->_right;//说明cur是他的右子树elseparent->_right = cur->_right;}		delete cur;}//如果他的右子树为空else if(cur->_right==nullptr){if (parent = nullptr)root = root->_left;else{//说明cur是他的左子树if (parent->_left = cur)parent->_left = cur->_left;//说明cur是他的右子树elseparent->_right = cur->_left;}delete cur;}//两个结点都不为空else{parent = cur;Node* rightmid = cur->_right;while (rightmid->_left){parent = rightmid;rightmid = rightmid->_left;}cur->_key = rightmid->_key;if(parent->_right==rightmid)//右子树parent->_right = rightmid->_right;else//左子树parent->_left = rightmid->_right;delete rightmid;}return true;}}//出了循环就找不到了return false;
}

三、二叉搜素树的应用

3.1 key模型：主要用于确定key是否存在

后续的<set>容器就是key模型
比如：给一个单词word，判断该单词是否拼写正确。

代码如下：

//BSTree.h
//树节点
template<class K>
struct TreeNode
{K _key;TreeNode<K>* _left;TreeNode<K>* _right;TreeNode(const K& key = K()) :_key(key), _left(nullptr), _right(nullptr) {}
};template<class K>
class BSTree
{typedef TreeNode<K> Node;
public:BSTree() = default;BSTree(const BSTree<K>& r):root(r.root){}~BSTree(){destory(root);root = nullptr;}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 Insert(const K& key){if (root == nullptr){root = new Node(key);return true;}Node* cur = root;Node* parent = nullptr;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 (cur->_key < parent->_key)parent->_left = cur;elseparent->_right = cur;return true;}bool erase(const K& key){Node* cur = root;Node* parent = nullptr;while (cur){if (cur->_key < key)//小于向右找{parent = cur;cur = cur->_right;}else if (cur->_key > key)//大于向左找{parent = cur;cur = cur->_left;}else//等于就找到{//0-1个孩子的情况//如果左子树为空if (cur->_left == nullptr){//是否删除根节点if (parent == nullptr)root = root->_right;else{//说明cur是他的左子树if (parent->_left == cur)parent->_left = cur->_right;//说明cur是他的右子树elseparent->_right = cur->_right;}delete cur;}//如果他的右子树为空else if (cur->_right == nullptr){if (parent = nullptr)root = root->_left;else{//说明cur是他的左子树if (parent->_left = cur)parent->_left = cur->_left;//说明cur是他的右子树elseparent->_right = cur->_left;}delete cur;}//两个结点都不为空else{parent = cur;Node* rightmid = cur->_right;while (rightmid->_left){parent = rightmid;rightmid = rightmid->_left;}cur->_key = rightmid->_key;if (parent->_right == rightmid)//右子树parent->_right = rightmid->_right;else//左子树parent->_left = rightmid->_right;delete rightmid;}return true;}}//出了循环就找不到了return false;}void InOrder(){_InOrder(root);cout << endl;}
private:Node* root;void _InOrder(Node* root){if (root == nullptr){return;}_InOrder(root->_left);cout << root->_key << " ";_InOrder(root->_right);}void destory(Node* root){if (root == nullptr)return;destory(root->_left);destory(root->_right);delete root;}
};

3.2 key/value模型：主要用于通过key来找到value

后续的<map>容器就是key/value模型
比如：停车场的停车费

//树节点
template<class K,class V>
struct TreeNode
{K _key;V _value;TreeNode<K,V>* _left;TreeNode<K,V>* _right;TreeNode(const K& key = K(),const V& value=V()) :_key(key),_value(value) ,_left(nullptr), _right(nullptr) {}
};template<class K,class V>
class BSTree
{typedef TreeNode<K,V> Node;
public:BSTree() = default;BSTree(const BSTree<K,V>& r) :root(r.root) {}~BSTree(){destory(root);root = nullptr;}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 Insert(const K& key,const V& value){if (root == nullptr){root = new Node(key,value);return true;}Node* cur = root;Node* parent = nullptr;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 (cur->_key < parent->_key)parent->_left = cur;elseparent->_right = cur;return true;}bool erase(const K& key){Node* cur = root;Node* parent = nullptr;while (cur){if (cur->_key < key)//小于向右找{parent = cur;cur = cur->_right;}else if (cur->_key > key)//大于向左找{parent = cur;cur = cur->_left;}else//等于就找到{//0-1个孩子的情况//如果左子树为空if (cur->_left == nullptr){//是否删除根节点if (parent == nullptr)root = root->_right;else{//说明cur是他的左子树if (parent->_left == cur)parent->_left = cur->_right;//说明cur是他的右子树elseparent->_right = cur->_right;}delete cur;}//如果他的右子树为空else if (cur->_right == nullptr){if (parent = nullptr)root = root->_left;else{//说明cur是他的左子树if (parent->_left = cur)parent->_left = cur->_left;//说明cur是他的右子树elseparent->_right = cur->_left;}delete cur;}//两个结点都不为空else{parent = cur;Node* rightmid = cur->_right;while (rightmid->_left){parent = rightmid;rightmid = rightmid->_left;}cur->_key = rightmid->_key;if (parent->_right == rightmid)//右子树parent->_right = rightmid->_right;else//左子树parent->_left = rightmid->_right;delete rightmid;}return true;}}//出了循环就找不到了return false;}void InOrder(){_InOrder(root);cout << endl;}
private:Node* root;void _InOrder(Node* root){if (root == nullptr){return;}_InOrder(root->_left);cout << root->_key << " " << root->_value << endl;_InOrder(root->_right);}void destory(Node* root){if (root == nullptr)return;destory(root->_left);destory(root->_right);delete root;}
};

四、二叉搜索树性能分析

插入和删除操作都必须先查找，查找效率代表了二叉搜索树中各个操作的性能。
对有n个结点的二叉搜索树，若每个元素查找的概率相等，则二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数，即结点越深，则比较次数越多。
但对于同一个关键码集合，如果各关键码插入的次序不同，可能得到不同结构的二叉搜索树：
在这里插入图片描述
最优情况下，二叉搜索树为完全二叉树(或者接近完全二叉树)，其平均比较次数为： l o g 2 N log_2 N log2​N
最差情况下，二叉搜索树退化为单支树(或者类似单支)，其平均比较次数为： N 2 \frac{N}{2} 2N​


http://www.ppmy.cn/news/1475965.html

相关文章

vue中缩放比的使用

vue中缩放比的使用

大屏适用性比较大&#xff0c;后台系统不推荐 抽组件&#xff0c;scaleScreen <template><divid"screen":style"{width: ${style.width}px,height: ${style.height}px,transform: ${style.transform},}"><slot ></slot></div&g…
阅读更多...
leetcode:2833. 距离原点最远的点（python3解法）

leetcode:2833. 距离原点最远的点（python3解法）

难度&#xff1a;简单 给你一个长度为 n 的字符串 moves &#xff0c;该字符串仅由字符 L、R 和 _ 组成。字符串表示你在一条原点为 0 的数轴上的若干次移动。 你的初始位置就在原点&#xff08;0&#xff09;&#xff0c;第 i 次移动过程中&#xff0c;你可以根据对应字符选择…
阅读更多...
debian固定ip

debian固定ip

debian固定ip 前言 安装好的Debian系统后&#xff0c;为了确保每次登陆的ip不变&#xff0c;需要固定 方法 命令如下 ip addr | grep inet因为有有线网和无线网 2 种连接方式&#xff0c;因此需要区别。 其中 enp 的是有线&#xff0c;wlp 的是无线 查看网关 IP 命令如下 …
阅读更多...
Jenkins中Node节点与构建任务

Jenkins中Node节点与构建任务

目录 节点在 Jenkins 中的主要作用 1. 分布式构建 分布式处理 负载均衡 2. 提供不同的运行环境 多平台支持 特殊环境需求 3. 提高资源利用率 动态资源管理 云端集成 4. 提供隔离和安全性 任务隔离 权限控制 5. 提高可扩展性 横向扩展 高可用性 Jenkins 主服务…
阅读更多...
Elasticsearch索引管理和生命周期管理

Elasticsearch索引管理和生命周期管理

在大数据和搜索引擎技术日益成熟的今天&#xff0c;Elasticsearch作为一款基于Lucene构建的开源搜索引擎&#xff0c;凭借其强大的全文搜索能力、分布式架构以及可扩展性&#xff0c;在日志分析、实时监控、应用搜索等多个领域得到了广泛应用。然而&#xff0c;随着数据量的不断…
阅读更多...
前端框架入门之Vue _el和data的两种写法 分析MVVM模型

前端框架入门之Vue _el和data的两种写法 分析MVVM模型

目录 _el与data的两种写法 MVVM模型 _el与data的两种写法 查看vue的实例对象 我们在这边注释掉了el属性 这样的话div容器就绑定不了vue实例 当我们可以在这里写一个定时任务 然后再回头指定 这个mount有挂载的意思 就是把容器对象交给vue实例后 去给他挂载指定的对象 &…
阅读更多...
网络基础：Vlan原理与配置

网络基础：Vlan原理与配置

VLAN&#xff08;Virtual Local Area Network&#xff0c;虚拟局域网&#xff09;是一种将一个物理网络划分为多个逻辑子网的技术。它通过在网络交换机上配置&#xff0c;使得不同VLAN中的设备即使连接在同一个物理交换机上&#xff0c;也不能直接进行通信&#xff0c;从而实现…
阅读更多...
10校大满贯！中国内地高校2024年1-6月CNS发文统计出炉

10校大满贯！中国内地高校2024年1-6月CNS发文统计出炉

随着全球科研竞争的日趋激烈&#xff0c;CNS&#xff08;Cell、Nature、Science&#xff09;作为科学领域的三大顶级期刊&#xff0c;不仅是科研成果的展示平台&#xff0c;更是各国科研实力比拼的重要战场。近年来&#xff0c;中国高校在国际科研舞台上的表现愈发抢眼&#xf…
阅读更多...
vuepress 配置文件分类管理

vuepress 配置文件分类管理

背景 在.vuepress的config.js配置文件中&#xff0c;我们需要设置head, plugins, nav三项主要配置。 如果都写在config.js就会显得很臃肿&#xff0c;不便于维护。 代码 config.js const headConf require("./config/headConf"); const pluginsConf require(&q…
阅读更多...
Hadoop3：HDFS-集群安全模式

Hadoop3：HDFS-集群安全模式

一、基本介绍 1、安全模式 文件系统只接受读数据请求&#xff0c;而不接受删除、修改等变更请求 2、 二、进入安全模式场景 1、NameNode在加载镜像文件和编辑日志期间处于安全模式&#xff08;就是启动集群的时候&#xff09;&#xff1b; 2、NameNode再接收DataNode注册时…
阅读更多...
深入解析HTTP与HTTPS：定义、架构、原理、应用场景及实战指南

深入解析HTTP与HTTPS：定义、架构、原理、应用场景及实战指南

前言 在互联网技术飞速发展的今天&#xff0c;HTTP&#xff08;Hypertext Transfer Protocol&#xff09;和HTTPS&#xff08;Hypertext Transfer Protocol Secure&#xff09;已经成为Web通信的基础协议。无论是浏览网页、提交表单&#xff0c;还是进行数据交互&#xff0c;HT…
阅读更多...
Apache Omid TSO 组件源码实现原理

Apache Omid TSO 组件源码实现原理

Apache Omid TSO 组件实现原理 作用 独立进程&#xff0c;处理全局事务之间的并发冲突。 流程 TSOChannelHandler#channelRead -> AbstractRequestProcessor -> PersistenceProcessorHandler 总体流程 thread1TSOChannelHandler#channelReadAbstractRequestProcess…
阅读更多...
c语言唯一一个三目运算符

c语言唯一一个三目运算符

条件表达式由两个符号&#xff08;&#xff1f;和&#xff1a;&#xff09;组成&#xff0c;必须一起使用。要求有三个操作对象&#xff0c;称为三目运算符。 一般形式为 表达式1&#xff1f;表达式2&#xff1a;表达式3 理解如下&#xff1a; a>b?(maxa):(maxb); //相当…
阅读更多...
微调 Florence-2 - 微软的尖端视觉语言模型

微调 Florence-2 - 微软的尖端视觉语言模型

Florence-2 是微软于 2024 年 6 月发布的一个基础视觉语言模型。该模型极具吸引力&#xff0c;因为它尺寸很小 (0.2B 及 0.7B) 且在各种计算机视觉和视觉语言任务上表现出色。 Florence 开箱即用支持多种类型的任务&#xff0c;包括: 看图说话、目标检测、OCR 等等。虽然覆盖面…
阅读更多...
Win10+Docker环境使用YOLOv8 TensorRT推理加速

Win10+Docker环境使用YOLOv8 TensorRT推理加速

这一部分内容和WSL-Ubuntu20.04环境使用YOLOv8 TensorRT推理加速-CSDN博客 是基本相同的，有细微差别我也会在文中指出来。 1.TensorRTX下载 这里使用Wang-xinyu大佬维护的TensorRTX库来对YOLOv8进行推理加速的演示，顺便也验证一下前面环境配置的成果。 github地址：GitHub -…
阅读更多...
【STM32 ARM】操作寄存器控制led

【STM32 ARM】操作寄存器控制led

文章目录 前言GPIO操作方法led原理图设置时钟APB的概念 设置APB设置输出引脚设置引脚高低电平寄存器寻找寄存器地址 总结 前言 STM32是STMicroelectronics&#xff08;意法半导体&#xff09;公司的一款32位Flash微控制器产品&#xff0c;基于ARM Cortex™-M内核。STM32系列微…
阅读更多...
NDK R25b 交叉编译FFMpeg4，项目集成，附库下载地址

NDK R25b 交叉编译FFMpeg4，项目集成，附库下载地址

1.准备工作 文件下载&#xff1a; NDK R25b下载地址&#xff1a;Android NDK历史版本下载网址 - 君*邪 - 博客园 (cnblogs.com) FFmpeg4.4.4 下载地址&#xff1a;https://ffmpeg.org/releases/ffmpeg-4.4.4.tar.xz 环境配置&#xff1a; 本次编译环境是在PC虚拟机中使用U…
阅读更多...
【LeetCode力扣】006. Z 字形变换（Python）

【LeetCode力扣】006. Z 字形变换（Python）

最快解法 参考了运行时间最短的代码&#xff0c;其使用的思路就是按列排序后连接。 class Solution:def convert(self, s: str, numRows: int) -> str:if numRows < 2 : # numRows1时候&#xff0c;对应输出为原字符串return sn len(s)lst [ for _ in range(numRows…
阅读更多...
“论软件维护方法及其应用”写作框架，软考高级论文，系统架构设计师论文

“论软件维护方法及其应用”写作框架，软考高级论文，系统架构设计师论文

论文真题 软件维护是指在软件交付使用后&#xff0c;直至软件被淘汰的整个时间范围内&#xff0c;为了改正错误或满足 新的需求而修改软件的活动。在软件系统运行过程中&#xff0c;软件需要维护的原因是多种多样的&#xff0c; 根据维护的原因不同&#xff0c;可以将软件维护…
阅读更多...
深入解析PHP框架：Symfony框架详解与应用

深入解析PHP框架：Symfony框架详解与应用

文章目录 深入解析PHP框架&#xff1a;Symfony框架详解与应用一、什么是Symfony&#xff1f;Symfony的优势 二、Symfony的核心概念1. 控制器2. 路由3. 模板4. 服务容器5. 事件调度器 三、Symfony的主要功能1. 表单处理2. 数据库集成3. 安全性4. 国际化5. 调试与日志 四、开发流…
阅读更多...
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站