Java中的二叉搜索树(如果想知道Java中有关二叉搜索树的知识点,那么只看这一篇就足够了!)

        前言:Java 提供了丰富的数据结构来处理和管理数据,其中 TreeSet 和 TreeMap 是基于红黑树实现的集合和映射接口。它们有序地存储数据,提供高效的搜索、插入和删除操作。


✨✨✨这里是秋刀鱼不做梦的BLOG

✨✨✨想要了解更多内容可以访问我的主页秋刀鱼不做梦-CSDN博客

先让我们看一下本文大致的讲解内容:

目录

1.二叉搜索树的认识

        (1)二叉搜索树的概念

        (2)二叉搜索树的性质

2.有关二叉搜索树的常用操作

        【1】插入操作

        【2】查找操作

        【3】删除操作

1.cur.left == null

2.cur.right == null

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

3.二叉树的应用场景

1. 数据结构和算法

2. 数据库和文件系统

3. 图形和游戏开发


1.二叉搜索树的认识

        (1)二叉搜索树的概念

        在开始学习TreeSet与TreeMap之前,我们需要先学习一下Java中的二叉搜索树,二叉搜索树是一种特殊的二叉树,其中每个节点都有一个值,并满足以下性质:

  • 对于每个节点,左子树所有节点的值都小于该节点的值。

  • 对于每个节点,右子树所有节点的值都大于该节点的值。

如图:

从上图中我们可以很明显的观察出二叉搜索树的上述两个特性。

        (2)二叉搜索树的性质

        在了解完了二叉搜索树的概念之后,我们需要学习一下有关二叉搜索树的性质,对于一棵二叉搜索树而言,其都有以下三个性质:

  • 有序性:二叉搜索树的中序遍历结果是一个递增的有序序列。

  • 动态性:二叉搜索树支持动态插入和删除操作,适用于需要频繁更新的数据集合。

  • 查找效率:在理想情况下,二叉搜索树的查找、插入和删除操作的时间复杂度为 O(log n)。

        ——这里读者可能会对其中的一些性质不是很理解,没有关系,继续向下进行阅读即可,在后续的文本中,我们会慢慢的理解其中的意思。

2.有关二叉搜索树的常用操作

        【1】插入操作

        插入操作用于向二叉搜索树中插入新值。插入过程从根节点开始,根据当前节点的值与新值的比较结果,决定将新值插入到左子树还是右子树。

以下是实现该操作的代码:

public void insertNode(int key) {// 如果根节点为空,直接插入新节点作为根节点if (root == null) {root = new TreeNode(key);return;}// 初始化当前节点为根节点,父节点为nullTreeNode cur = root;TreeNode parent = null;TreeNode node = new TreeNode(key);// 寻找合适的位置插入节点while (cur != null) {if (cur.val < key) { // 当前值小于插入值,向右子树移动parent = cur;cur = cur.right;} else if (cur.val > key) { // 当前值大于插入值,向左子树移动parent = cur;cur = cur.left;} else { // 当前值等于插入值,直接返回,不插入重复值return;}}// 根据父节点值与插入值的比较结果,插入新节点到左子树或右子树if (parent.val > key) {parent.left = node;} else {parent.right = node;}
}

读者可以跟着下面的解释来对上边的代码进行理解:

  1. 根节点为空检查

    • 如果 root 为空,直接将新节点 TreeNode(key) 作为根节点插入,并返回。
  2. 初始化当前节点和父节点

    • cur 用于遍历树,从 root 开始。
    • parent 用于记录 cur 的父节点。
  3. 寻找合适的插入位置

    • cur 不为空时,比较 cur.valkey
      • 如果 cur.val 小于 key,移动到右子树。
      • 如果 cur.val 大于 key,移动到左子树。
      • 如果 cur.val 等于 key,直接返回,不插入重复值。
  4. 插入新节点

    • 根据 parent.valkey 的比较结果,将新节点插入到 parent 的左子树或右子树。

        ——这样我们就学会了插入操作了!

        【2】查找操作

        查找操作用于在二叉搜索树中查找特定值。查找过程从根节点开始,根据当前节点的值与目标值的比较结果,决定在左子树还是右子树继续查找。

以下是实现该操作的代码:

public TreeNode search(int key) {// 初始化当前节点为根节点TreeNode cur = root;// 遍历树,直到找到目标节点或遍历到空节点while (cur != null) {if (cur.val < key) { // 当前节点值小于目标值,移动到右子树cur = cur.right;} else if (cur.val > key) { // 当前节点值大于目标值,移动到左子树cur = cur.left;  // 这里应修正为cur = cur.left;} else { // 找到目标节点return cur;}}// 如果没有找到目标节点,返回 nullreturn null;
}

读者可以跟着下面的解释来对上边的代码进行理解:

  1. 初始化当前节点

    • cur 用于遍历树,从 root 开始。
  2. 遍历树

    • cur 不为空时,比较 cur.valkey
      • 如果 cur.val 小于 key,移动到右子树 (cur = cur.right)。
      • 如果 cur.val 大于 key,移动到左子树 (cur = cur.left)。
      • 如果 cur.val 等于 key,返回当前节点。
  3. 返回结果

    • 如果遍历完整棵树没有找到目标节点,返回 null

        【3】删除操作

        删除操作用于从二叉搜索树中删除指定值。删除节点分为三种情况:叶子节点、只有一个子节点的节点和有两个子节点的节点。

        由于删除操作比较哦啊复杂,所以我们这里重点讲解一下,对于删除操作,我们可能会有以下的可能情况:

——现在我们假设待删除结点为 cur, 待删除结点的双亲结点为 parent:

1.cur.left == null

        1. cur 是 root,则 root = cur.right
        2. cur 不是 root,cur 是 parent.left,则 parent.left = cur.right
        3. cur 不是 root,cur 是 parent.right,则 parent.right = cur.right

2.cur.right == null

        1. cur 是 root,则 root = cur.left
        2. cur 不是 root,cur 是 parent.left,则 parent.left = cur.left

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

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

        这时我们就需要使用替换法进行删除,即在它的右子树中寻找中序下的第一个结点(关键码最小),用它的值填补到被删除节点中,再来处理该结点的删除问题

我们大致了解了删除的三种可能的大情况之后,现在让我们尝试着编写一下代码:

public void remove(int key) {TreeNode parent = null; // 父节点初始化为 nullTreeNode cur = root; // 当前节点初始化为根节点// 遍历树,寻找要删除的节点while (cur != null) {if (cur.val < key) { // 当前值小于目标值,移动到右子树parent = cur;cur = cur.right;} else if (cur.val > key) { // 当前值大于目标值,移动到左子树parent = cur;cur = cur.left;} else { // 找到目标节点removeNode(parent, cur); // 调用辅助方法删除节点return; // 删除节点后退出方法}}
}private void removeNode(TreeNode parent, TreeNode cur) {if (cur.right == null) { // 当前节点没有右子树if (cur == root) { // 当前节点是根节点root = root.left; // 根节点指向左子树} else if (parent.left == cur) { // 当前节点是父节点的左子节点parent.left = cur.left; // 父节点左子节点指向当前节点的左子树} else { // 当前节点是父节点的右子节点parent.right = cur.left; // 父节点右子节点指向当前节点的左子树}} else if (cur.left == null) { // 当前节点没有左子树if (cur == root) { // 当前节点是根节点root = root.right; // 根节点指向右子树} else if (parent.left == cur) { // 当前节点是父节点的左子节点parent.left = cur.right; // 父节点左子节点指向当前节点的右子树} else { // 当前节点是父节点的右子节点parent.right = cur.right; // 父节点右子节点指向当前节点的右子树}} else { // 当前节点有两个子节点TreeNode targetParent = cur; // 目标节点的父节点初始化为当前节点TreeNode target = cur.right; // 目标节点初始化为当前节点的右子节点// 寻找右子树中的最左节点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.二叉树的应用场景

        学习完二叉树的概念以及其基本的使用之后,让我们来学习一些二叉树的应用场景,二叉树(Binary Tree)在日常中有着广泛的应用。以下是一些主要的实际应用场景:

1. 数据结构和算法

  • 二叉搜索树(BST):用于实现高效的搜索、插入和删除操作,时间复杂度平均为 O(log n)。

  • 平衡树(如AVL树、红黑树):这些是自平衡二叉搜索树,确保树的高度保持在 O(log n),从而提供高效的操作。

  • 堆(Heap):二叉堆用于实现优先队列。最大堆用于实现高效的最大值查找,最小堆用于最小值查找。

2. 数据库和文件系统

  • B树和B+树:这些是多路搜索树,常用于数据库索引和文件系统索引,以提高查询和检索的效率。

  • Trie树:一种多叉树,用于实现前缀匹配,常用于字典存储和自动补全功能。

3. 图形和游戏开发

  • 四叉树和八叉树:用于空间分割,以提高碰撞检测、渲染和其他空间查询操作的效率。

  • 场景图(Scene Graph):在3D图形引擎中,场景图是一个树状结构,用于管理和渲染场景中的对象。

这样我们就大致的了解了二叉树在今后的日常中有哪些用武之地了!!!


以上就是本篇文章的主要内容了!!!

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

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

相关文章

软件测试 -- 黑盒、灰盒、白盒测试,冒烟测试、回归测试

软件测试目的&#xff1a;查找软件中缺陷&#xff08;bug&#xff09;&#xff0c;保障软件质量。

MyBatis 动态代理和映射器

一、映射器简介 1.什么是mapper动态代理? 在接口中有方法的返回值定义&#xff0c;参数的定义&#xff0c;方法名&#xff0c;在sqlMapper.xml 中也对应这接口给予了赋值&#xff0c; 这时候dao的实现类就显得多余&#xff0c;这是Mybatis可以帮助我们自动产生实现类&#xf…

HarmonyOS多目标产物构建最佳实践

背景 在Android或iOS开发时经常会有打“马甲”包的场景&#xff0c;就是一套代码打出不同主题的包&#xff0c;一个公司的产品可能针对不同用户提供不同的应用&#xff0c;比如抖音有国内版也有国外版&#xff0c;滴滴有个人版还有企业版&#xff0c;同样的在鸿蒙平台也有类似…

C++初学(9)

9.1、结构简介 虽然数组能够和存储多个元素&#xff0c;但所有元素必须相同&#xff0c;也就是说&#xff0c;同一个数组不能既存放int类型也存放float类型&#xff0c;而C的结构可以满足要求。结构是一种比数组更灵活的数据格式&#xff0c;因为同一个结构可以存储多种类型的…

QtQuick Text-文本样式

属性 Text项目的style属性可以设置文本的样式。 支持的文本样式有&#xff1a; Text.Normal&#xff08;默认&#xff09;Text.OutlineText.RaisedText.Sunken 示例 import QtQuickRow{spacing: 10padding: 10Text {font.pointSize: 40text: "Normal"}Text {font…

数据库原理之多表查询——使用Mysql进行内连接和外连接

作者&#xff1a;CSDN-PleaSure乐事 欢迎大家阅读我的博客 希望大家喜欢 使用环境&#xff1a;Idea 目录 1.内连接 1.1隐式内连接 1.1.1定义 1.1.2举例 1.1.3优缺点 1.2显式内连接 1.2.1定义 1.2.2举例 1.2.3优缺点 2.外连接 2.1左外连接 2.1.1定义 2.1.2举例 2.…

【从零开始一步步学习VSOA开发】开发环境搭建

开发环境搭建 开发 VSOA 首先需要搭建开发环境&#xff0c;这里讲解 Windows 下 C/C 开发环境搭建方法。 下载 IDE 并申请授权码 SylixOS 的开发和部署需要 RealEvo-IDE 的支持&#xff0c;因此您需要先获取 RealEvo-IDE 的安装包和注册码。 RealEvo-IDE 分为体验版和商业版…

如何确保PLC系统安全的可靠性,这几个注意事项你需要牢记

PLC&#xff08;可编程逻辑控制器&#xff09;是现代工业自动化系统中的关键组成部分。在设计 PLC 系统时&#xff0c;安全性是至关重要的考虑因素。本文将介绍 PLC 系统设计中的一些安全注意事项&#xff0c;包括电源设计、接地设计、关键数字量输入输出设计和报警设计。 一.…

vue实现简易的全局加载动画效果

效果展示 思路 封装一个组件&#xff0c;放Img&#xff0c;伪类样式&#xff0c;固定在屏幕fixed 然后App应用这个组件&#xff0c;Z index拉最大&#xff0c;防止用户在加载动画时乱点&#xff0c; v-show绑定loading&#xff0c;该数据可以放vuex还是任一的公共状态管理变…

PDF文件点击打印无反应?是何原因造成能解决吗?

PDF无法打印怎么处理&#xff1f;在我们工作中&#xff0c;经常会遇见各种各样的文件问题&#xff0c;当我们想要将PDF文件打印出来纸质版使用&#xff0c;却不知什么原因&#xff0c;显示PDF无法打印&#xff0c;这时应该怎么处理呢&#xff1f; 一般情况下&#xff0c;PDF文件…

cesium canvas广告牌

在有些业务中&#xff0c;对场景中的广告牌样式要求比较高&#xff0c;需要动态显示一些数据&#xff0c;这个时候&#xff0c;我们可以通过将复杂背景样式制作成图片&#xff0c;通过canvas绘制图片和动态数据&#xff0c;从而达到比较好的显示效果。 1 CanvasMarker 类封装 …

学Python可少不了项目练手,这8个小项目有趣又实用,小白也能做出来_python练手项目,python教程

学习之路比较科学的学习方法是理解了之后把知识点进行运用&#xff0c;找一些开源的小项目做是最好的&#xff0c;站在岸上是学不会游泳的&#xff0c;光看健身视频是减不了肥的&#xff0c;不自己动手敲代码是学不会编程的。 我在找了8个比较有趣的小项目&#xff0c;技术水平…

E5092A可配置的多端口测试仪

E5092A 可配置的多端口测试仪 多达 10 个端口的全交叉测量&#xff0c;或者最多 22 个端口的测量功能。 概述 E5092A 多端口测试仪可以灵活配置&#xff0c;并可与4 端口ENA 网络分析仪&#xff08;E5070B/E5071B/E5071C/E5080A&#xff09;结合使用&#xff0c;组成频率范…

web3 solana

网址&#xff1a;HACKQUEST 学习初衷&#xff1a; 1.web3概念较为小众&#xff0c;相比于web2&#xff0c;机会较多 2.有机会remote work&#xff0c;带着笔记本到处浪&#xff0c;听着就不错 3.面对越来越卷的国内&#xff0c;有机会并有能力拥抱国外job&#xff0c;感觉是…

鸿蒙系统开发【应用接续】基本功能

应用接续 介绍 基于ArkTS扩展的声明式开发范式编程语言编写的一个分布式视频播放器&#xff0c;主要包括一个直播视频播放界面&#xff0c;实现视频播放时可以从一台设备迁移到另一台设备继续运行&#xff0c;来选择更合适的设备继续执行播放功能以及PAD视频播放时协同调用手…

《LeetCode热题100》---<5.②普通数组篇五道>

本篇博客讲解LeetCode热题100道普通数组篇中的六道题 第三道&#xff1a;轮转数组&#xff08;中等&#xff09; 第四道&#xff1a;除自身以外数组的乘积&#xff08;中等&#xff09; 第三道&#xff1a;轮转数组&#xff08;中等&#xff09; 方法一&#xff1a;使用额外的数…

vscode+cmake+msys2工具链配置

1、msys2下载编译器和cmake工具 pacman -S mingw-w64-x86_64-toolchain pacman -S mingw-w64-x86_64-cmaketoolchain包中包含很多不必要的工具包&#xff0c;应该可以指定具体的工具g&#xff0c;gcc&#xff0c;mingw32-make的下载&#xff0c;详细命令请自行搜索。 2、将 m…

QT 应用程序输出中文乱码

一 &#xff0c;选择文本编码 1. 点击编辑再点击Select Encoding选择编码 2 .在弹出的窗口&#xff0c;选择UTF-8再点击按编码保存即可 3. 重新编译&#xff0c;可以发现中文乱码问题解决

思维+dfs,CF 269C - Flawed Flow

一、题目 1、题目描述 2、输入输出 2.1输入 2.2输出 3、原题链接 269C - Flawed Flow 二、解题报告 1、思路分析 考虑源点相连的边的方向是确定的&#xff0c;因为流量是从源点往外流的 我们设cap[u] 为 和u相连边的容量和&#xff0c;显然入边容量要和出边容量相等&…

jvm调优参数

JVM调优是指调整JVM的参数&#xff0c;以优化Java程序的性能。以下是一些常用的JVM调优方法&#xff1a; 1.堆内存大小&#xff1a;通过-Xms和-Xmx参数设置JVM的初始堆内存和最大堆内存。堆内存太小会导致频繁GC&#xff0c;太大则可能导致内存利用率不高。 2.新生代与老年…