二十分钟深入详解<二叉搜索树>!!!

news/2024/5/19 19:23:38/

目录

前文

一,什么是二叉搜索树?

1.1 二叉搜索树的概念

二, 二叉搜索树的常用操作及其实现

2.1 查找

2.2 插入

 2.3 删除

三,二叉搜索树的应用

3.1 K模型

3.2 KV模型

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

五,代码

总结


前文

本文主要是带领大家深入了解二叉搜索树的实现以及使用

ps:二叉搜索树的所有代码会在文末贴出(包括构造,析构,赋值等)

一,什么是二叉搜索树?

1.1 二叉搜索树的概念

二叉搜索树又称二叉排序树,它可能是个空树,或是具有以下特征的二叉树

1.若其左子树不为空,则其左子树上的所有值都小于根

2.若其右子树不为空,则其右子树上的所有值都大于根

3.其左右子树也符合二叉搜索树

二叉搜索树作为一种经典的数据结构,它既有链表的快速插入与删除操作的特点,又有数组快速查找的优势;所以应用十分广泛,例如在文件系统和数据库系统一般会采用这种数据结构进行高效率的排序与检索操作。 

二, 二叉搜索树的常用操作及其实现

上图为搜索二叉树的结点结构以及成员变量

2.1 查找

实现思路:

1.从根开始比较,比根大往右走,比根小往左走

2.最多比较树的高度次,走到空还没找到就返回false

 如上图所示,左边为非递归实现,右边是递归实现,这里递归实现需要注意,由于在类中都是通过*this指针调用成员函数,而*this指针是隐藏的无法控制递归条件,所以在类中写递归需要通过子函数完成递归调用。


2.2 插入

实现思路:

1.树为空,则直接new一个新节点给root

2.树不为空,通过二叉树查找的规则找到空位置,插入即可

 代码如下

 2.3 删除

实现思路:

利用二叉树查找的规则找到目标节点,不存在则返回false,但是删除的时候需要考虑以下四种情况

1.目标节点没有左右孩子

2.目标节点有左孩子,没右孩子

3.目标节点有右孩子,没有左孩子

4.目标节点左右孩子都有

 因为只有左孩子或者只有右孩子的处理方式都可以处理左右孩子都没有的情况,所以我们将左右孩子都没有的处理方式和只有左孩子的处理方式合并

处理方式如下:

2.删除该节点,并且被删除节点的父节点指向被删除节点的左孩子——直接删除

 3.删除该节点,并且被删除节点的父节点指向被删除节点的右孩子——直接删除

 4.找到能够替代其位置的值,也就是要满足左子树小于该值,右子树大于该值,我们可以找左子树的最大值或者右子树的最小值,然后被删除节点赋值成找到的最大值或最小值,在删除最大值或最小值节点。

 

 如上图左边是非递归写法,右边是递归写法,有看不懂的可以私信我

三,二叉搜索树的应用

3.1 K模型

K模型即只有key作为关键码,结构中只需要存储Key即可,关键码即为需要搜索到的值

实际运用:

给一个单词,判断该单词是否拼写正确,具体方式:

具体方式如下:

1.以词库中所有单词集合中的每个单词作为key,构建一棵二叉搜索树
2.在二叉搜索树中检索该单词是否存在,存在则拼写正确,不存在则拼写错误

3.2 KV模型

每一个关键码key,都有与之对应的值Value,即<Key, Value>的键值对。该种方式在现实生活中非常常见:

1.比如英汉词典就是英文与中文的对应关系,通过英文可以快速找到与其对应的中文,英文单词与其对应的中文<word, chinese>就构成一种键值对;

2.再比如统计单词次数,统计成功后,给定单词就可快速找到其出现的次数,单词与其出现次数就是<word, count>就构成一种键值对

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

在二叉搜索树中查找是绕不过去的功能,无论是插入还是删除都必须先查找,因此查找的效率和二叉搜索树的性能直接挂钩

 尽管是同一组序列,但是不同的插入顺序构造出的搜索二叉树也是不一样的,如上图所示,左边是比较正常的树,右边是极端情况下的歪脖子树。

最优情况下,也就是类似于左边情况,复杂度就是树的高度,也就是:logN

最差情况下,类似于右边的歪脖子树,此时树的高度接近于N,因此其复杂度就是:N、

那么针对右边的歪脖子树有什么优化方法呢?

肯定是有的,后续学习的AVL树和红黑树就会起到极大的效果

五,代码

//K模型
namespace key
{template<class K>struct BSTreeNode{BSTreeNode(K key):_left(nullptr), _right(nullptr), _key(key){}BSTreeNode<K>* _left;BSTreeNode<K>* _right;K _key;};template<class K>class BSTree{typedef BSTreeNode<K> Node;public://构造函数BSTree():_root(nullptr){}//拷贝构造函数,用copy函数前序遍历拷贝BSTree(BSTree<K>& t){_root = copy(t._root);}Node* copy(Node* root){if (root == nullptr)return nullptr;Node* ret = new Node(root->_key);copy(root->_right);copy(root->_left);return ret;}//赋值重载BSTree<K>& operator=(BSTree<K> t){swap(_root, t._root);return *this;}//析构函数,调用Destory后续遍历销毁即可~BSTree(){Destory(_root);}void Destory(Node*& root){if (root == nullptr)return;Destory(root->_right);Destory(root->_left);delete root;root = nullptr;}//查找bool Find(const K& key){if (_root == nullptr)return false;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 Findr(const K& key){_Findr(_root, key);}bool _Findr(Node*& root, const K& key){if (root == nullptr){return false;}if (root->_key < key){return _Findr(root->_right, key);}else if (root->_key > key){return _Findr(root->_left, key);}else//找到了{return true;}return false;}//删除(erase)bool Erase(const K& key){if (_root == nullptr)return false;Node* cur = _root;Node* parent = nullptr;//找val的位置while (cur){if (cur->_key < key){parent = cur;cur = cur->_right;}else if (cur->_key > key){parent = cur;cur = cur->_left;}else{if (cur->_right == nullptr)//目标位置没有右孩子{if (cur == _root)//删除根的情况{_root = cur->_left;delete cur;}else{if (parent->_left == cur){parent->_left = cur->_left;delete cur;}else{parent->_right = cur->_left;delete cur;}}}else if (cur->_left == nullptr){if (cur == _root)//删除根的情况{_root = cur->_right;delete cur;}else{if (parent->_left == cur){parent->_left = cur->_right;delete cur;}else{parent->_right = cur->_right;delete cur;}}}else{//我们这里寻找左子树的最大值Node* maxLeft = cur->_left;Node* pmaxLeft = cur;while (maxLeft->_right){pmaxLeft = maxLeft;maxLeft = maxLeft->_right;}cur->_key = maxLeft->_key;if (pmaxLeft->_left == maxLeft){pmaxLeft->_left = maxLeft->_left;delete maxLeft;}else if (pmaxLeft->_right == maxLeft){pmaxLeft->_right = maxLeft->_left;delete maxLeft;}}return true;}}return false;}//递归删除bool Eraser(const K& key){return _Eraser(_root, key);}bool _Eraser(Node*& root, const K& key){if (root == nullptr){return false;}if (root->_key < key){return _Eraser(root->_right, key);}else if (root->_key > key){return _Eraser(root->_left, key);}else{//找到要删除的位置了Node* cur = root;if (root->_right == nullptr){/*Node* cur = root;*/root = root->_left;/*delete cur;*/}else if (root->_left == nullptr){/*Node* cur = root;*/root = root->_right;/*delete cur;*/}else//左右子树都存在{Node* pcur = cur;cur = cur->_left;while (cur->_right)//找左树最大值{pcur = cur;cur = cur->_right;}root->_key = cur->_key;/*if (pcur->_left == cur){pcur->_left = cur->_left;}else if (pcur->_right==cur){pcur->_right = cur->_left;}*/return _Eraser(root->_left, root->_key);}delete cur;return true;}return false;}//插入,成功插入返回true,失败也就是已有所要插入的数字则返回falsebool Insert(const K& key){if (_root == nullptr){_root = new Node(key);}else{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 (parent->_key < key){parent->_right = cur;}else{parent->_left = cur;}}return true;}//递归插入bool Insertr(const K& key){return _Insertr(_root, key);}bool _Insertr(Node*& root, const K& key){if (root == nullptr){root = new Node(key);return true;}if (root->_key < key){return _Insertr(root->_right, key);}else if (root->_key > key){return _Insertr(root->_left, key);}return false;}//中层遍历void InOrder(){_Inorder(_root);cout << endl;}void _Inorder(Node* root){if (root == nullptr)return;_Inorder(root->_left);cout << root->_key << " ";_Inorder(root->_right);}private:Node* _root = nullptr;};
}

总结

本篇文章主要讲解二叉树的基本概念,实现以及应用场景,希望铁子们能有所收货


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

相关文章

【设计模式】Java 的三种代理模式

文章目录 一、前言二、正文1、静态代理2、动态代理3、Cglib代理Spring中AOP使用代理 三、总结 一、前言 代理(Proxy)模式是一种结构型设计模式&#xff0c;提供了对目标对象另外的访问方式&#xff1b;即通过代理对象访问目标对象。 这样做的好处是&#xff1a;可以在目标对…

更全面的对比GPT4和Claude对MLIR的掌握能力

本文构造了20个MLIR基础概念的问题以及使用OneFlow IR转换为Tosa IR的5个代码段来评测GPT4和Claude对于MLIR的掌握能力&#xff0c;我的结论是对于基础概念的理解Claude整体上和GPT4持平&#xff0c;而在阅读相关代码片段时Claude表现出了比GPT4更强一点的理解能力。 0x0. 前言…

vue2使用sync修饰符父子组件的值双向绑定

1、使用场景 当我需要对一个 prop 进行“双向绑定的时候&#xff0c;通常用在封装弹窗组件的时候来进行使用&#xff0c;当然也会有其他的使用场景&#xff0c;只要涉及到父子组件之间需要传参的都可以使用&#xff0c;尽量不要使用watch监听来进行修改值&#xff0c;也不要尝试…

如何给厂区做导航地图?智能工厂导航地图解决方案公司

如何给厂区做导航地图&#xff1f;在智慧园区中&#xff0c;基于园区的电子地图地图使用的重要性越来越凸显。但目前在园区信息化应用形式中&#xff0c;广泛缺乏专业电子地图的使用&#xff0c;主要原因是&#xff1a;一是地图系统(GIS)实现繁复&#xff0c;与其他展会业务系统…

大数据实战 --- 美团外卖平台数据分析

目录 开发环境 数据描述 功能需求 数据准备 数据分析 RDD操作 Spark SQL操作 创建Hbase数据表 创建外部表 统计查询 开发环境 HadoopHiveSparkHBase 启动Hadoop&#xff1a;start-all.sh 启动zookeeper&#xff1a;zkServer.sh start 启动Hive&#xff1a; nohup …

DelphiMVCFrameWork 源码分析(一)

Delphi 基础Web Service Application 见&#xff1a; Delphi Web Server 流程分析_看那山瞧那水的博客-CSDN博客 DataSnap的见&#xff1a; Delphi DataSnap 流程分析(一)_看那山瞧那水的博客-CSDN博客 Delphi DataSnap 流程分析(二)_看那山瞧那水的博客-CSDN博客 DelphiMVC…

@SpringBootApplication注解

启动类的 SpringBootApplication // // Source code recreated from a .class file by IntelliJ IDEA // (powered by Fernflower decompiler) //package org.springframework.boot.autoconfigure;import java.lang.annotation.Documented; import java.lang.annotation.Elem…

homebrew安装mysql

安装指定版本的软件 我们可以用版本号来安装指定版本的软件,例如: brew install mysql5.7这会安装MySQL 5.7版本。 查看软件Versions 我们可以用brew info命令查看一个软件的所有版本,例如: brew info mysql会显示MySQL所有可安装版本,然后选择想要的版本号安装。 升级软…

设计模式 -- 命令模式

前言 月是一轮明镜,晶莹剔透,代表着一张白纸(啥也不懂) 央是一片海洋,海乃百川,代表着一块海绵(吸纳万物) 泽是一柄利剑,千锤百炼,代表着千百锤炼(输入输出) 月央泽,学习的一种过程,从白纸->吸收各种知识->不断输入输出变成自己的内容 希望大家一起坚持这个过程,也同…

【Leetcode -342. 4的幂 -344.反转字符串 -345.反转字符串中的元音字母】

Leetcode Leetcode -342. 4的幂Leetcode -344.反转字符串Leetcode -345.反转字符串中的元音字母 Leetcode -342. 4的幂 题目&#xff1a;给定一个整数&#xff0c;写一个函数来判断它是否是 4 的幂次方。如果是&#xff0c;返回 true &#xff1b;否则&#xff0c;返回 false …

item_get-获得aliexpress商品详情API的调用参数说明

item_get-获得aliexpress商品详情 aliexpress.item_get 公共参数 名称类型必须描述keyString是调用key&#xff08;免&#xff09;&#xff08;测&#xff09;&#xff08;试&#xff09;secretString是调用密钥api_nameString是API接口名称&#xff08;包括在请求地址中&…

Android入门

一、Android系统架构 Android大致可以分为4层架构&#xff1a;Linux内核层、系统运行库层、应用框架层和应用层 1.1Linux内核层 Android系统是基于Linux内核的&#xff0c;这一层为Android设备的各种硬件提供了如显示、音频、照相机、蓝牙、Wi-Fi等底层的驱动。 1.2系统运行层…

ELK简介

ELK 1. ELK2. Elasticsearch&#xff08;ES&#xff09;3. Logstash4. Kibana5. Filebeat6. 缓存/消息队列&#xff08;redis、kafka、RabbitMQ等&#xff09; 1. ELK ELK是三个开源软件的首字母缩写&#xff0c;分别表示&#xff1a;Elasticsearch , Logstash, Kibana , 它们…

腾讯云COS+ElmentUI+SpringBoot视频上传功能实现

文章目录 第一步&#xff1a;选择合适的组件并整合到项目中第二步&#xff1a;前端校验第三步&#xff1a;绑定上传成功方法第四步&#xff1a;腾讯云cos后端接口配置 今天在做项目的时候需要完成一个视频上传的功能&#xff0c;这里做一个记录&#xff01; 第一步&#xff1a;…

MongoDB实现---事务机制

事务机制 原子性是MongoDB实现事务的难点&#xff0c;隔离性和持久性则是MongoDB事务机制的亮点 ACID支持&#xff1a;由于前面说过MongoDB是基于大数据、提供高度可扩展和高可用&#xff1b;所以其事务机制不仅仅是一般ACID还是结合了BASE理论下的ACID 原子性&#xff1a;保…

GreenPlum (一) 初识

在开始了解GreenPlum之前&#xff0c;应该对这种产品的诞生有基本的了解&#xff0c;搭建一个基本的知识框架。对以下历史有基本了解之后应对下文术语进行基本阅读。 ​ 阅读目标: 阅读完成后需要对相关术语以及greenplum有基础理解。 文案基本互联网相关blog进行整体汇总&…

【RabbitMQ学习日记】—— 再见RabbitMQ

一、发布确认高级篇 在生产环境中由于一些不明原因&#xff0c;导致 rabbitmq 重启&#xff0c;在 RabbitMQ 重启期间生产者消息投递失败&#xff0c;导致消息丢失&#xff0c;需要手动处理和恢复如何才能进行 RabbitMQ 的消息可靠投递呢&#xff1f; 特别是在这样比较极端的情…

uniapp 之 将marker 渲染在地图上 点击弹层文字时显示当前信息

目录 效果图 总代码 分析 1.template 页面 地图显示代码 2. onload ①经纬度 ②取值 ③注意 ④ 3.methods ① 先发送 getStationList 请求 获取 数组列表信息 ② regionChange 视野发生变化时 触发 分页逻辑 ③ callouttap 点击气泡时触发 查找 当前 marker id 等…

java ssm高校学术会议论文管理系统

在研究课题--学术会议论文管理系统的实现与设计&#xff0c;对操作使用的便利性&#xff0c;系统的可制定性和安全性以及管理的全面性等多个方面研究。其中主要研究的内容是将学术会议论文管理系统功能划分为: 通知类型、通知信息、部门信息、用户信息用户反馈、会议类型、会议…

编译和链接

目录 1. 程序的翻译环境和执行环境 2. 详解编译链接 2.1 翻译环境 2.2 编译本身也分为几个阶段&#xff1a; 2.2.1汇编过程的简略图 2.3讲解汇编过程的具体过程和要点 2.4运行环境 1. 程序的翻译环境和执行环境 在ANSIC的任何一种实现中&#xff0c;存在两个不同的环境。…