【数据结构】什么是二叉搜索(排序)树?

🦄个人主页:修修修也

🎏所属专栏:数据结构

⚙️操作环境:Visual Studio 2022


目录

📌二叉搜索(排序)树的概念

📌二叉搜索(排序)树的操作

🎏二叉搜索树的查找

🎏二叉搜索树的插入

🎏二叉搜索树的删除

结语


📌二叉搜索(排序)树的概念

        我们今天要介绍的树是一种非常适合于搜索/排序的树, 当然二叉搜索(排序)树的前提是它是一颗树,并且是一颗二叉树。因此对于树以及二叉树的定义还有不太了解的朋友建议先移步这两篇博客补充一下数据结构树的相关前置知识:

【数据结构】什么是树?icon-default.png?t=O83Ahttps://blog.csdn.net/weixin_72357342/article/details/134973723?spm=1001.2014.3001.5502

【数据结构】什么是二叉树?icon-default.png?t=O83Ahttps://blog.csdn.net/weixin_72357342/article/details/135162895?sharetype=blogdetail&sharerId=135162895&sharerefer=PC&sharesource=weixin_72357342&spm=1011.2480.3001.8118

        二叉搜索树(BST, Binary Search Tree) 也称二叉排序树或二叉查找树。它或是一颗空树,或是具有下列性质的二叉树:

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

        下图罗列了部分属于/不属于二叉搜索树的二叉树以供参考:

        对于二叉搜索树而言,其中序遍历的结果恰好是树中所有结点值的有序排列,因此特性也称其为二叉排序树。构造一棵二叉排序树的目的,其实并不是为了排序,而是为了提高查找和插入删除关键字的速度。不管怎么说,在一个有序数据集上的查找,速度总是要快于无序的数据集的,而二叉排序树这种非线性的结构,同样有利于插入和删除操作的实现


📌二叉搜索(排序)树的操作

        以如下二叉搜索树为例, 分别剖析二叉搜索树的查找,插入和删除操作:

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

🎏二叉搜索树的查找

        二叉搜索树的查找过程如下:

  1. 从根节点开始比较查找, 如果查找值比根结点值大,则往右子树继续查找; 如果查找值比根结点值小,则往左子树继续查找;
  2. 最多查找高度次, 即查找到叶子节点, 如果还没找到, 则该值不存在于此树中。

🎏二叉搜索树的插入

        二叉搜索树的插入过程如下:

  1. 树为空,则直接新增节点,赋值给根节点指针
  2. 树不为空,则按二叉搜索树性质查找插入位置, 在查找到为空的位置插入新增值, 如果查找到该值已存在, 则返回查找失败(二叉搜索树不允许插入重复值)

🎏二叉搜索树的删除

        查找元素是否在二叉搜索中,如果不存在,则返回,如果存在,则待删除结点可能存在以下四种情况:

  1. 待删除结点无孩子结点
  2. 待删除结点只有左孩子结点(不管右孩子)
  3. 待删除结点只有右孩子结点(不管左孩子)
  4. 待删除结点左,右孩子结点都有

        在实际删除操作中,可以将1和2 / 3合并起来,因为我们的逻辑是哪边有孩子就管理,没有孩子就可以不管,因此无孩子结点既可以和不管右孩子结点情况合并又可以和不管左孩子情况合并,合并后实际的删除情况及过程如下三种:

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


结语

希望这篇关于 二叉搜索(排序)树 的博客能对大家有所帮助,欢迎大佬们留言或私信与我交流.

学海漫浩浩,我亦苦作舟!关注我,大家一起学习,一起进步!

相关文章推荐

【数据结构】什么是线性表?

【数据结构】线性表的链式存储结构

【数据结构】什么是栈?

【数据结构】什么是树?

【数据结构】什么是队列?

【数据结构】什么是堆?

【数据结构】什么是树?

【数据结构】什么是二叉树?


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

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

相关文章

how can I train a OpenAI fine tuned model with more prompts

题意:我如何使用更多提示来训练一个 OpenAI 微调模型? 问题背景: I fine-tuned OpenAI model with some prompts following this documentation it succeeded and created a new model in the playground. How I can retrain (fine-tune) th…

邮件营销:助力企业转换客户,提升曝光率

邮件营销:独立站推广的关键策略 在独立站推广的众多方法中,邮件营销占据着重要地位。本文将为刚刚接触独立站运营的新手介绍邮件营销的基础知识。在信息泛滥的时代,开设一个店铺和成功地引流并不意味着一劳永逸。对于绝大多数中小型电商企业…

AIGC实战之如何构建出更好的大模型RAG系统

大家好,我是爱编程的喵喵。双985硕士毕业,现担任全栈工程师一职,热衷于将数据思维应用到工作与生活中。从事机器学习以及相关的前后端开发工作。曾在阿里云、科大讯飞、CCF等比赛获得多次Top名次。现为CSDN博客专家、人工智能领域优质创作者。…

感知器神经网络

1、原理 感知器是一种前馈人工神经网络,是人工神经网络中的一种典型结构。感知器具有分层结构,信息从输入层进入网络,逐层向前传递至输出层。根据感知器神经元变换函数、隐层数以及权值调整规则的不同,可以形成具有各种功能特点的…

matlab模拟时间有负数的信号频谱

真实还原频谱,要做一次fftshift 直接fft,得到的频谱有线性偏移

高级大数据开发学习路线指南

掌握大数据技术是一项系统性工程,涉及到广泛的技能和专业知识。为了帮助初学者构建坚实的基础,并逐步成长为大数据领域的专家,下面详细阐述了一条全面而深入的学习路线: 1. Java 编程基础 - 打造坚实的底层技能 关键知识点&…

C++对象拷贝时的优化编译

在现代编译器中,当我们在 C中进行对象的拷贝操作时,编译器并非只是机械地执行逐字节的复制。相反,它会进行优化,避免不必要的拷贝构造等等,这种优化包括“返回值优化”(RVO),“拷贝省…

kubernetes调度2

1、各种缩写的应用 [rootk8s-master test]# kubectl get rsNAME DESIRED CURRENT READY AGEtest001-64c7957b5c 2 2 2 8m59stest001-698b98bb8f 0 0 0 12m[rootk8s-master test]# kubectl get replicas…

XML映射器-动态sql

01-动态sql 1.实现动态条件SQL 第一种方法在sql语句中加入where 11其他条件都加and就行,这样就可以根据if条件来判断要传递的参数可以有几个 第二种方法用where标签给if语句包起来 where标签的作用如下图 第三种方法用trim标签解释如下图 用choose也可以实现条件查询如下图,…

【RabbitMQ】死信队列、延迟队列

死信队列 死信,简单理解就是因为种种原因,无法被消费的消息。 有死信,自然就有死信队列。当一个消息在一个队列中变成死信消息之后,就会被重新发送到另一个交换器中,这个交换器就是DLX(Dead Letter Excha…

C++入门 之 类和对象(下)

目录 一、初始化列表 二、隐式类型转换与explict 三、静态成员——static 四、友元 五、内部类 六、匿名对象 七.对象拷贝时的编译器优化 一、初始化列表 之前我们实现构造函数时,初始化成员变量主要使用函数体内赋值,构造函数初始化还有一种方式&…

信奥初赛解析:1-3-计算机软件系统

知识要点 软件系统是计算机的灵魂。没有安装软件的计算机称为“裸机”,无法完成任何工作硬件为软件提供运行平台。软件和硬件相互关联,两者之间可以相互转化,互为补充 计算机软件系统按其功能可分为系统软件和应用软件两大类 一、系统软件 系统软件是指…

SpringCloud微服务实现服务降级的最佳实践

Spring Cloud是一种用于快速构建分布式系统的框架,它提供了许多有用的功能,其中包括服务降级。 服务降级是一种保护机制,它可以在面临高并发或故障时保持服务的稳定性。当系统资源不足或服务出现故障时,服务降级可以通过关闭一些功…

react 组件化开发_生命周期_表单处理

组件基本介绍 我们从上面可以清楚地看到,组件本质上就是类和函数,但是与常规的类和函数不同的是,组件承载了渲染视图的 UI 和更新视图的 setState 、 useState 等方法。React 在底层逻辑上会像正常实例化类和正常执行函数那样处理的组件。 因…

Unsupervised Deep Representation Learning for Real-Time Tracking

摘要 我们的无监督学习的动机是稳健的跟踪器应该在双向跟踪中有效。具体来说,跟踪器能够在连续帧中前向定位目标对象,并回溯到其在第一帧中的初始位置。基于这样的动机,在训练过程中,我们测量前向和后向轨迹之间的一致性&#xf…

95、k8s之rancher可视化

一、ranker 图形化界面 图形化界面进行k8s集群的管理 rancher自带监控----普罗米修斯 [rootmaster01 opt]# docker load -i rancher.tar ##所有节点 [rootmaster01 opt]# docker pull rancher/rancher:v2.5.7 ##主节点[rootmaster01 opt]# vim /etc/docker/daemon.jso…

C++初阶学习——探索STL奥秘——反向迭代器

适配器模式是 STL 中的重要组成部分,除了容器适配器外,还有 选代器适配器,借助 选代器适配器 ,可以轻松将各种容器中的普通迭代器转变为反向迭代器,这正是适配器的核心思想 注:库中的反向迭代器在设计时,为…

HashMap线程不安全|Hashtable|ConcurrentHashMap

文章目录 常见集合线程安全性HashMap为什么线程不安全?怎么保证HashMap线程安全 HashtableConcurrentHashMap 引入细粒度锁代码中分析总结 小结 常见集合线程安全性 ArrayList、LinkedList、TreeSet、HashSet、HashMap、TreeMap等都是线程不安全的。 HashTable是线…

【Python报错已解决】To update, run: python.exe -m pip install --upgrade pip

🎬 鸽芷咕:个人主页 🔥 个人专栏: 《C干货基地》《粉丝福利》 ⛺️生活的理想,就是为了理想的生活! 专栏介绍 在软件开发和日常使用中,BUG是不可避免的。本专栏致力于为广大开发者和技术爱好者提供一个关于BUG解决的经…

【C++篇】~类和对象(中)

类和对象(中) 1.类的默认成员函数​ 默认成员函数就是用户没有显式实现,编译器会自动生成的成员函数称为默认成员函数。一个类,我们不写的情况下编译器会默认生成以下6个默认成员函数,需要注意的是这6个中最重要的是前…