搜索树基础:二叉搜索树(详解特性用途,图解实现过程)

二叉搜索树

  • 二叉搜索树的特性
  • 二叉搜索树的主要用途
  • 二叉搜索树的基本操作
    • 1、二叉搜索树的查找
    • 2、二叉搜索树的插入
    • 3、二叉搜索树的删除(难点)
      • (1)找到待删结点
      • (2)分情况删除

二叉搜索树的特性

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

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

二叉搜索树的主要用途

二叉搜索树主要用于实现高效的数据查找和排序:

  1. 查找:由于二叉搜索树的特性,可以通过比较节点的键值来快速定位目标节点。在查找操作中,对于一颗相对平衡的二叉搜索树,每次都可以将搜索范围缩小一半,因此平均时间复杂度为O(log n),其中n是树中节点的数量。
  2. 排序:对于一个无序的序列,可以利用二叉搜索树的性质进行排序。具体实现方法是,将序列中的元素依次插入到二叉搜索树中,然后进行中序遍历,即可按照升序输出有序序列。这种基于二叉搜索树的排序算法,对于一颗相对平衡的二叉搜索树,平均时间复杂度为O(nlog n)

在这里插入图片描述

需要注意的是,二叉搜索树的性能取决于树的形状。如果构建出的二叉搜索树高度不平衡(只有左树或只有右树),查找的时间复杂度可能达到O(n),导致操作效率会大幅下降。因此,在实际使用中,需要注意维护二叉搜索树的平衡性,以提高操作效率,在此基础上演化出了 AVL树、红黑树等更具平衡性的数据结构。

二叉搜索树是学习其他“搜索”数据结构的基础,下面就围绕二叉搜索树的一些操作进行展开介绍:

二叉搜索树的基本操作

为了实现二叉搜索树的相关操作,这里首先给出二叉搜索树节点的定义:

static class TreeNode {
 	 public int val;
     public TreeNode left;
     public TreeNode right;

     public TreeNode(int val) {
         this.val = val;
     }
 }
// 二叉搜索树根节点,初始时为空
public TreeNode root = null;

1、二叉搜索树的查找

实现思路(利用二叉搜索树的特性):

  1. 从根节点开始,与目标键值进行比较。
  2. 如果目标键值等于当前节点的键值,则找到了目标节点;
  3. 如果目标键值小于当前节点的键值,则继续在左子树中查找;
  4. 如果目标键值大于当前节点的键值,则继续在右子树中查找;
  5. 重复步骤2、3、4直到找到目标节点或者遍历到叶子节点。
public TreeNode find(int val) {
    // 从根节点开始查找
    TreeNode cur = root;
    while (cur != null) {
        if (cur.val == val) {
            // 找到返回结点
            return cur;
        } else if (cur.val > val) {
            // 当前结点值大于目标结点
            cur = cur.left;
        } else {
            // 当前结点小于目标结点
            cur = cur.right;
        }
    }
    // 找不到
    return null;
}

2、二叉搜索树的插入


经过简单分析,当搜索树非空时,二叉树的插入,总是插入到相应的叶子结点(由于结点之间单向联通,所以需要记录待插入位置的父节点):

  1. 从根节点开始,与要插入的键值进行比较。
  2. 如果要插入的键值小于当前节点的键值并且当前节点的左子节点为空,则将新节点作为当前节点的左子节点;
  3. 如果要插入的键值大于当前节点的键值并且当前节点的右子节点为空,则将新节点作为当前节点的右子节点。
public boolean insert(int val) {
    // 如果当前根节点为空,则插入到根节点
    if (root == null) {
        root = new TreeNode(val);
        return true;
    }
    TreeNode cur = root;
    // 记录插入位置的父节点
    TreeNode parent = null;
    // 寻找插入位置
    while (cur != null) {
        if (cur.val > val) {
        	// 当前结点值大于目标结点
            parent = cur;
            cur = cur.left;
        } else if (cur.val < val) {
        	// 当前结点值小于目标结点
            parent = cur;
            cur = cur.right;
        } else {
            // 如果二叉搜索树中已存在,直接返回
            System.out.println("已存在:" + val);
            return false;
        }
    }
    // 构造插入结点
    TreeNode node = new TreeNode(val);
    // 此时 parent 结点指向插入位置的父节点
    if (parent.val > val) {
        parent.left = node;
    } else {
        parent.right = node;
    }
    return true;
}

3、二叉搜索树的删除(难点)

(1)找到待删结点

二叉搜索树的删除,首先需要找到待删除结点,然后执行删除操作(由于结点之间单向联通,所以需要记录待删结点的父节点):

public void remove(int val) {
	// 待删结点,从root开始找
    TreeNode cur = root;
    // 待删结点的父节点
    TreeNode parent = null;
    while (cur != null) {
        if (cur.val == val) {
        	// 找到目标结点,调用删除操作
            removeNode(cur, parent);
            return;
        } else if (cur.val > val) {
        	// 当前结点值大于目标结点
            parent = cur;
            cur = cur.left;
        } else {
        	// 当前结点值小于目标结点
            parent = cur;
            cur = cur.right;
        }
    }
    System.out.println("不存在:" + val);
}

(2)分情况删除

二叉搜索树的删除操作,是一个相对复杂的操作,需要考虑多种不同情况:

设待删除结点为 cur, 待删除结点的双亲结点为 parent

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

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

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

思路

此时需要使用替换法进行删除。可以选择用其左子树cur.left的最大值节点,或右子树cur.right的最小值节点的值填补到被删除节点中,然后删除这个最大或最小值节点。

上面这两种选哪个都行,下面我就以选择右子树 cur.right 中的最小值结点替换删除为例:

  • 当右子树的根节点有左孩子,那么 minParent.left 是右子树的最小值

  • 当右树根结点没有左孩子,那么 minParent.right 是右子树的最小值

最终实现代码:

private void removeNode(TreeNode cur, TreeNode parent) {
    if (cur.left == null) {
        // 1.如果待删除结点左孩子为空
        if (cur == root) {
            //左孩子为空的前提下,cur为根节点
            cur = cur.right;
        } else if (parent.left == cur) {
            //左孩子为空的前提下,cur为父节点的左树
            parent.left = cur.right;
        } else {
            //左孩子为空的前提下,cur为父节点的右树
            parent.right = cur.right;
        }
    } else if (cur.right == null) {
        // 2.如果待删除结点右孩子为空
        if (cur == root) {
            //右孩子为空的前提下,cur为根节点
            cur = cur.left;
        } else if (parent.left == cur) {
            //右孩子为空的前提下,cur为父节点的左树
            parent.left = cur.left;
        } else {
            //右孩子为空的前提下,cur为父节点的右树
            parent.right = cur.left;
        }
    } else {
        // 3.如果待删除结点左右孩子都不为空

        //这里是cur.left!=null && cur.right!=null的情况
        //替换删除:(找到右树里的最小值替换删除/找到左树的最大值替换删除)
        //下面展示找到右树里的最小值替换删除
        TreeNode minParent = cur;
        TreeNode min = cur.right;
        while (min.left != null) {
            minParent = min;
            min = min.left;
        }
        //此时 min 的左边一定为空
        //值替换
        cur.val = min.val;
        if (minParent.right == min) {
            // 当右树根结点没有左孩子,那么 minParent.right 是右子树的最小值
            minParent.right = min.right;
        } else {
            // 当右子树的根节点有左孩子,那么 minParent.left 是右子树的最小值
            minParent.left = min.right;
        }
    }
}

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

升级还是不升级?iPhone 15和iPhone 14 Plus性能比较

预览iPhone 15 Pro Max与三星Galaxy S23 Ultra之战是有正当理由的。显然,三星的旗舰智能手机为2023年的所有其他旗舰产品定下了基调——由于其超长的电池寿命和一流的摄像头,证明了它是最受欢迎的产品。 毫不奇怪,Galaxy S23 Ultra不仅是最好的照相手机之一,也是花钱能买到…

【JVM基础】JVM入门基础

目录 JVM的位置三种 JVMJVM体系结构类加载器双亲委派机制概念例子作用 沙箱安全机制组成沙箱的基本组件 NativeJNI&#xff1a;Java Native Interface&#xff08;本地方法接口&#xff09;Native Method Stack&#xff08;本地方法栈&#xff09; PC寄存器&#xff08;Program…

自动驾驶SLAM技术第四章习题2

在g2o的基础上改成ceres优化&#xff0c;高博都写好了其他的部分, 后面改ceres就很简单了. 这块我用的是ceres的自动求导&#xff0c;很方便&#xff0c;就是转化为模板仿函数的时候有点麻烦&#xff0c; 代码部分如下 ceres_type.h : ceres优化核心库的头文件 这个文件写的内…

openGauss学习笔记-48 openGauss 高级数据管理-函数

文章目录 openGauss学习笔记-48 openGauss 高级数据管理-函数48.1 数学函数48.2 三角函数列表48.3 字符串函数和操作符48.4 类型转换相关函数 openGauss学习笔记-48 openGauss 高级数据管理-函数 openGauss常用的函数如下&#xff1a; 48.1 数学函数 abs(x) 描述&#xff1a;…

IDEA中使用Docker插件构建镜像并推送至私服Harbor

一、开启Docker服务器的远程访问 1.1 开启2375远程访问 默认的dokcer是不支持远程访问的&#xff0c;需要加点配置&#xff0c;开启Docker的远程访问 # 首先查看docker配置文件所在位置 systemctl status docker# 会输出如下内容&#xff1a; ● docker.service - Docker Ap…

测试框架pytest教程(10)自定义命令行-pytest_addoption

pytest_addoption pytest_addoption是pytest插件系统中的一个钩子函数&#xff0c;用于向pytest添加自定义命令行选项。 在pytest中&#xff0c;可以使用命令行选项来控制测试的行为和配置。pytest_addoption钩子函数允许您在运行pytest时添加自定义的命令行选项&#xff0c;…

【VS Code插件开发】消息通信(四)

&#x1f431; 个人主页&#xff1a;不叫猫先生&#xff0c;公众号&#xff1a;前端舵手 &#x1f64b;‍♂️ 作者简介&#xff1a;前端领域优质作者、阿里云专家博主&#xff0c;共同学习共同进步&#xff0c;一起加油呀&#xff01; &#x1f4e2; 资料领取&#xff1a;前端…

adb 命令

1.adb shell dumpsys activity top | find "ACTIVITY" 查看当前运行的activity包名 2.adb shell am start -n 包名/页面名 打开应用的页面 3.查看将要启动或退出app的包名 adb shell am monitor 只有在启动或退出的时候才会打印 4.查看当前启动应用的包名 ad…

AR室内导航技术之技术说明与效果展示

随着科技的飞速发展&#xff0c;我们周围的环境正在经历着一场数字化的革命。其中&#xff0c;AR室内导航技术以其独特的魅力&#xff0c;为我们打开了一扇通往全新数字化世界的大门。本文将为您详细介绍这一技术的实现原理、工具应用以及成品展示&#xff0c;带您领略AR室内导…

mybatis-plus--配置-(sql)日志输出-自动填充-分页-多数据源-逻辑删除

写在前面&#xff1a; 本文主要介绍mybatis-plus的配置&#xff0c;以后在有的时候在补充。欢迎交流。 文章目录 日志输出自动填充分页全局字段配置多数据源 日志输出 调试的时候需要看执行的sql&#xff0c;这时候就很需要日志来记录查看了。 mybatis-plus的日志配置在yml…

自动化部署及监测平台基本架构

声明 本文是学习 政务计算机终端核心配置规范. 而整理的学习笔记,分享出来希望更多人受益,如果存在侵权请及时联系我们 核心配置自动化部署及监测技术要求 自动化部署及监测平台基本架构 对于有一定规模的政务终端核心配置应用&#xff0c;需要配备自动化部署及监测平台&am…

01-jupyter notebook的使用方法

一、Tab补全 在shell中输入表达式&#xff0c;按下Tab&#xff0c;会搜索已输入变量&#xff08;对象、函数等等&#xff09;的命名空间&#xff1a; 除了补全命名、对象和模块属性&#xff0c;Tab还可以补全其它的。当输入看似文件路径时 &#xff08;即使是Python字符串&…

浅拷贝与深拷贝

作者简介&#xff1a; zoro-1&#xff0c;目前大一&#xff0c;正在学习Java&#xff0c;数据结构等 作者主页&#xff1a; zoro-1的主页 欢迎大家点赞 &#x1f44d; 收藏 ⭐ 加关注哦&#xff01;&#x1f496;&#x1f496; 浅拷贝与深拷贝 浅拷贝浅拷贝定义浅拷贝代码演示浅…

优秀产品奖!移远5G RedCap模组,让5G真正“轻”下来

8月24日&#xff0c;在通信世界全媒体主办的“5G RedCap技术与物联网应用创新研讨会”上&#xff0c;“5G RedCap优秀产品和解决方案”获奖名单发布&#xff0c;移远通信5G RedCap模组Rx255C系列以其在创新性、实用性、经济性、成熟性等方面的综合领先优势&#xff0c;获此殊荣…

更高效稳定 | 基于ACM32 MCU的编程直流电源应用方案

随着电子设备的多样化发展&#xff0c;面对不同的应用场景&#xff0c;需要采用特定的供电电源。因此&#xff0c;在电子产品的开发测试过程中&#xff0c;必不可少使用编程直流电源来提供测试电压&#xff0c;协助完成初步的开发测试过程。 编程直流电源概述 编程直流电源结构…

李沐pytorch学习-经典CNN的原理及代码实现

一、LeNet 1.1 模型结构 LeNet结构如图1所示&#xff0c;汇聚层即池化层&#xff0c;这里池化Stride&#xff08;步幅&#xff09;与池化层长宽一致&#xff0c;因此使得池化后大小减半。 图1. LeNet结构 1.2 代码实现 代码实现如下&#xff1a; import torch from torch imp…

Arnold置乱

一、Arnold置乱概述 Arnold变换是俄国数学家弗拉基米尔阿诺德&#xff08;Vladimir Igorevich Arnold&#xff09;提出&#xff0c;Arnold将其应用在遍历理论研究中。由于Arnold本人最初对一张猫的图片进行了此种变换&#xff0c;因此它又被称为猫脸变换&#xff08;cat映射&am…

基于Citespace、vosviewer、R语言的文献计量学可视化分析技术及全流程文献可视化SCI论文高效写作方法

文献计量学是指用数学和统计学的方法&#xff0c;定量地分析一切知识载体的交叉科学。它是集数学、统计学、文献学为一体&#xff0c;注重量化的综合性知识体系。特别是&#xff0c;信息可视化技术手段和方法的运用&#xff0c;可直观的展示主题的研究发展历程、研究现状、研究…

HCIP-OpenStack组件之neutron

neutron&#xff08;ovs、ovn&#xff09; OVS OVS(Open vSwitch)是虚拟交换机&#xff0c;遵循SDN(Software Defined Network&#xff0c;软件定义网络)架构来管理的。 OVS介绍参考&#xff1a;https://mp.weixin.qq.com/s?__bizMzAwMDQyOTcwOA&mid2247485088&idx1…