二叉搜索树的简单理解

1. 二叉搜索树

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

若它的左子树不为空,则左子树上所有节点的值都小于根节点的值

若它的右子树不为空,则右子树上所有节点的值都大于根节点的值

它的左右子树也分别为二叉搜索树

        如下图所示,就是一个简单的二叉搜索树,且存储的数据为:

        int[] array ={5,3,4,1,7,8,2,6,0,9};

2. 二叉搜索树的实现

2.1 二叉搜索树的创建

        简单创建一个二叉树;

package binarysearchtree;public class BinarySearchTree0 {static class TreeNode{public int value;public TreeNode left;public TreeNode right;public TreeNode(int value){this.value = value;}}
}

2.2 查找关键字key

        思路如下:

1、若根节点不为空:

        1.1如果根节点value==查找key,返回true

        1.2如果根节点value > 查找key,在其左子树查找

        1.3如果根节点value< 查找key,在其右子树查找,如果找不到,返回false

2、如果根节点为空,则返回false;以下为分析图解:

        代码实现:

 public TreeNode root ;//根节点public boolean findKey(int key){TreeNode cur = root;while (cur != null){if (cur.value == key){return true;}else if (key > cur.value){cur = cur.right;}else {cur = cur.left;}}return false;}

 2.3 插入关键字key的节点

        思路:

        插入操作可以分为以下两种情况:

  1. 如果树为空树,即根 == null,直接插入

        

        2.如果树不是空树,按照查找逻辑确定插入位置,插入新结点

        下图举个例子来分析:

        总体分析:

        1、先确定节点左右移动的方向 

  • 如果节点root.value==key,该值在搜索数中已经存在,无需插入,return flase;
  • 如果节点root.value>key,在其左子树找合适位置
  • 如果节点root.value<key,在其右子树找合适位置

        2、引入parent,该节点定义为与key值最后比较之后,接下来要进行插入节点操作的节点;

  • 如果节点parrent.value>key,新建key节点插在parent的左边
  • 如果节点parrent.value<key,新建key节点插在parent的右边

        代码如下图所示:

  public void insertkey(int key) {if(root == null) {root = new TreeNode(key);return;}TreeNode cur = root;TreeNode parent = null;while (cur != null) {if (key == cur.value) {return ;} else if (key < cur.value) {parent = cur;cur = cur.left;} else {parent = cur;cur = cur.right;}}TreeNode node = new TreeNode(key);if (key < parent.value) {parent.left = node;} else {parent.right = node;}}

 2.4删除关键字key

        假设要删除的结点为 cur, 待删除结点的双亲结点为 parent,我们分以下四种情况来分析:

        1. cur.left == null

        1.1 cur 是 root ,则 root = cur.right(图解如下)

         

        1.2 cur 不是 root,cur 是 parent.left,则 parent.left = cur.right

               

        1.3 cur 不是 root,cur 是 parent.right,则 parent.right = cur.right

                     

        2. cur.right == null(下面的三种情况与1截然相反,此处略)
        2.1  cur 是 root ,则 root = cur.left
        2.2  cur 不是 root , cur 是 parent.left ,则 parent.left = cur.left
        2.3  cur 不是 root , cur 是 parent.right ,则 parent.right = cur.left

        3. cur.left != null && cur.right != null

        思路:

我们使用target来遍历寻找子树中关键节点,targetParent用来记录target的父亲节点

找到相应节点后与待删除的cur节点的值进行替换,最后删除target结点即可

        详细的图解思路如下所示:

 

        4.cur左右孩子均不存在

        直接置为null;

        综上所述,代码实现:

    public void remove(int val) {TreeNode cur = root;TreeNode parent = null;while (cur != null) {if (val == cur.val) {removeNode(parent, cur);break;} else if (val < cur.val) {parent = cur;cur = cur.left;} else {parent = cur;cur = cur.right;}}}private void removeNode(TreeNode parent, TreeNode cur) {if (cur.left==null){if(cur==root){root=cur.right;}else if(parent.left==cur){parent.left=cur.right;}else{parent.right=cur.right;}} else if (cur.right==null) {if(cur==root){root=cur.left;}else if(parent.left==cur){parent.left=cur.left;}else{parent.right=cur.left;}}else{TreeNode target = cur.right;TreeNode targetParent = cur;while(target.left!=null){targetParent = target;target = target.left;}cur.val=target.val;if(targetParent.left==target){targetParent.left=target.right;}else{targetParent.right=target.right;}}}

3. 二叉搜索树性能分析

        插入和删除操作都必须先查找,查找效率代表了二叉搜索树中各个操作的性能。

        对有n个结点的二叉搜索树,若每个元素查找的概率相等,则二叉搜索树平均查找长度是结点在二叉搜索树的深度的函数,即结点越深,则比较次数越多。

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

        最优情况下,二叉搜索树为完全二叉树,其平均比较次数为:log (2^n)

        最差情况下,二叉搜索树退化为单支树,其平均比较次数为:N/2

ps:二叉搜索树的内容就到这里了,大家喜欢的话就请一键三连哦!!!

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

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

相关文章

监听器中GUI的理解

文章目录 前言一、Panel窗口关闭Demo总结 前言 比如登录拦截&#xff1a;用户登录后&#xff0c;会被拦截掉。就可以用监听器来处理。 一、Panel窗口关闭Demo 先创建一个窗口&#xff0c;发现点击关闭后&#xff0c;关闭不掉&#xff0c;就要添加监听事件&#xff1a; pub…

The method show() from the type Window is deprecated

java.awt.Window.show() java.awt.Component.setVisible(true); Window.show() java.awt.JFrame java.awt.Frame java.awt.Windows java.awt.Component.setVisible(true);

亿赛通电子文档安全管理系统 SQL注入漏洞复现

0x01 产品简介 亿赛通电子文档安全管理系统&#xff08;简称&#xff1a;CDG&#xff09;是一款电子文档安全加密软件&#xff0c;该系统利用驱动层透明加密技术&#xff0c;通过对电子文档的加密保护&#xff0c;防止内部员工泄密和外部人员非法窃取企业核心重要数据资产&…

Elasticsearch:为现代搜索工作流程和生成式人工智能应用程序铺平道路

作者&#xff1a;Matt Riley Elastic 的创新投资支持开放的生态系统和更简单的开发者体验。 在本博客中&#xff0c;我们希望分享 Elastic 为简化你构建 AI 应用程序的体验而进行的投资。 我们知道&#xff0c;开发人员必须在当今快速发展的人工智能环境中保持灵活性。 然而&a…

联邦蒸馏中的分布式知识一致性 | TIST 2024

联邦蒸馏中的分布式知识一致性 | TIST 2024 联邦学习是一种隐私保护的分布式机器学习范式&#xff0c;服务器可以在不汇集客户端私有数据的前提下联合训练机器学习模型。通信约束和系统异构是联邦学习面临的两大严峻挑战。为同时解决上述两个问题&#xff0c;联邦蒸馏技术被提…

激活Windows过程及报错解决: 0x803f7001 在运行Microsoft Windows 非核心版本的计算机上, 运行“ slui.exe 0x2a 0x803f7001 “以显示错误文本

激活Windows过程及报错问题解决: 0x803f7001 在运行Microsoft Windows 非核心版本的计算机上&#xff0c;运行“ slui.exe 0x2a 0x803f7001 “以显示错误文本。 前言 最近在激活Windows过程中&#xff0c;遇到了报错: 0x803f7001 在运行Microsoft Windows 非核心版本的计算机上…

人工智能|深度学习——知识蒸馏

一、引言 1.1 深度学习的优点 特征学习代替特征工程&#xff1a;深度学习通过从数据中自己学习出有效的特征表示&#xff0c;代替以往机器学习中繁琐的人工特征工程过程&#xff0c;举例来说&#xff0c;对于图片的猫狗识别问题&#xff0c;机器学习需要人工的设计、提取出猫的…

Axure的使用

1.Axure是什么&#xff1f;&#xff1f;&#xff1f; Axure是一款功能强大的原型设计工具&#xff0c;它可以让用户快速地创建交互式原型&#xff0c;并针对原型进行测试和改进。Axure的主要特点包括可定制的界面元素库、交互动画效果、条件逻辑、团队协作等功能&#xff0c;适…

LabVIEW开发远程结构健康监测系统

LabVIEW开发远程结构健康监测系统 工程师依赖于振动监测来评估建筑物、桥梁和其他大型结构的完整性。传统的振动监测工具在数据收集上存在限制&#xff0c;无法长时间收集高保真波形。随着内存存储、处理器速度和宽带无线通信技术的进步&#xff0c;出现了对能够长时间收集并实…

Spark与PySpark(1.概述、框架、模块)

目录 1.Spark 概念 2. Hadoop和Spark的对比 3. Spark特点 3.1 运行速度快 3.2 简单易用 3.3 通用性强 3.4 可以允许运行在很多地方 4. Spark框架模块 4.1 Spark Core 4.2 SparkSQL 4.3 SparkStreaming 4.4 MLlib 4.5 GraphX 5. Spark的运行模式 5.1 本地模式(单机) Local运行模…

《PCL多线程加速处理》-滤波-统计滤波

《PCL多线程加速处理》-滤波-统计滤波 一、效果展示二、实现方式三、代码一、效果展示 提升速度随着点云越多效果越明显 二、实现方式 1、原始的统计滤波实现方式 #include <pcl/filters/statistical_outlier_removal.h>pcl::PointCloud<pcl::PointXYZ

vue2-elementUI部分组件样式修改

el-radio样式&#xff1a; /deep/ .el-radio__input .el-radio__inner {width: 20px;height: 20px;position: relative;cursor: pointer;-webkit-appearance: none;-moz-appearance: none;appearance: none;border: 1px solid #999;border-radius: 0;outline: none;transition…

【C语言】超详解strncpystrncatstrncmpstrerrorperror的使⽤和模拟实现

&#x1f308;write in front :&#x1f50d;个人主页 &#xff1a; 啊森要自信的主页 ✏️真正相信奇迹的家伙&#xff0c;本身和奇迹一样了不起啊&#xff01; 欢迎大家关注&#x1f50d;点赞&#x1f44d;收藏⭐️留言&#x1f4dd;>希望看完我的文章对你有小小的帮助&am…

张驰课堂:如何应用六西格玛法则优化你的工作流?

作为职场发展的坚实支柱&#xff0c;六西格玛不仅是企业提质增效的利器&#xff0c;同时也是那些渴望在职业生涯中脱颖而出的专业人士的的秘密武器。以下是通过培养个人技能&#xff0c;借助六西格玛优化工作与人生的途径。 团队合作&#xff1a;聚沙成塔的力量 六西格玛教我…

SQL进阶理论篇(四):索引的结构原理(B树与B+树)

文章目录 简介如何评价索引的数据结构设计好坏二叉树的局限性什么是B树什么是B树总结参考文献 简介 我们在上一节中说过&#xff0c;索引其实是一种数据结构&#xff0c;那它到底是一种什么样的数据结构呢&#xff1f;本节将简单介绍一下几个问题&#xff1a; 什么样的数据结…

Vue3-18-侦听器watch()、watchEffect() 的基本使用

什么是侦听器 个人理解&#xff1a;当有一个响应式状态&#xff08;普通变量 or 一个响应式对象&#xff09;发生改变时&#xff0c;我们希望监听到这个改变&#xff0c;并且能够进行一些逻辑处理。那么侦听器就是来帮助我们实现这个功能的。侦听器 其实就是两个函数&#xff…

Process On在线绘制流程图

目录 一.ProcessOn 1.1.介绍 1.2.直接网上使用 二.绘制门诊流程图 三.绘制住院流程图 四.绘制药库采购入库流程图 五.绘制OA会议流程图 今天就到这里了哦!!!希望能帮到你哦&#xff01;&#xff01;&#xff01; 一.ProcessOn 1.1.介绍 ProcessOn&#xff08;流程&#…

智能优化算法应用:基于蝠鲼觅食算法3D无线传感器网络(WSN)覆盖优化 - 附代码

智能优化算法应用&#xff1a;基于蝠鲼觅食算法3D无线传感器网络(WSN)覆盖优化 - 附代码 文章目录 智能优化算法应用&#xff1a;基于蝠鲼觅食算法3D无线传感器网络(WSN)覆盖优化 - 附代码1.无线传感网络节点模型2.覆盖数学模型及分析3.蝠鲼觅食算法4.实验参数设定5.算法结果6.…

Vue学习计划-Vue2--VueCLi(五)全局事件总线、消息订阅与发布(pubsub)

抛出问题:我们多级组件&#xff0c;或者任意不想关的子组件如何传递数据呢&#xff1f; 1. 全局事件总线&#xff08;$bus&#xff09; 一种组件间通信的方式&#xff0c;适用于任意组件间通信 全局事件总线示意图&#xff1a; 安装全局事件总线&#xff1a; new Vue({..…

无人机高空巡查+智能视频监控技术,打造森林防火智慧方案

随着冬季的到来&#xff0c;森林防火的警钟再次敲响&#xff0c;由于森林面积广袤&#xff0c;地形复杂&#xff0c;且人员稀少&#xff0c;一旦发生火灾&#xff0c;人员无法及时发现&#xff0c;稍有疏忽就会酿成不可挽救的大祸。无人机高空巡查智能视频监控是一种非常有效的…