数据结构--二叉排序树（Binary Search Tree，简称BST）

这里写自定义目录标题

  • 二叉排序树
    • 二叉排序树与排序数组没有排序数组，链式存储链表的对比
    • 二叉排序树概念
      • 对于搜索操作，
      • 对于插入操作，
      • 对于删除操作，
    • 分析删除节点
    • 代码
    • 运行结果

二叉排序树

二叉排序树与排序数组没有排序数组，链式存储链表的对比

  • 二叉排序树（BST）：

    • 数据结构：通过链式存储方式实现，每个节点包含一个值以及左右子节点的指针。
    • 特点：满足二叉搜索树的性质，即对于树中的每个节点，其左子树中的所有节点都小于它，右子树中的所有节点都大于它。
    • 插入操作：按照大小顺序将新元素插入到树的合适位置，保持树的有序性。
    • 查询操作：通过比较节点的值与目标值的大小关系，递归地在左子树或右子树中进行查找。
    • 删除操作：根据情况，将要删除的节点替换为其子节点或后继节点，并保持树的有序性。

  • 排序数组：

    • 数据结构：通过线性数组的方式存储，元素按照升序排列。
    • 特点：数组中的元素按照从小到大的顺序排列。
    • 插入操作：通过比较元素的大小关系，找到插入位置，并将元素插入到数组中的合适位置，然后移动其他元素以保持有序性。
    • 查询操作：使用二分查找算法，在数组中快速定位目标值。
    • 删除操作：通过移动元素，将要删除的元素从数组中删除，并保持有序性。

  • 链式存储的链表：

    • 数据结构：使用节点和指针的方式进行存储，每个节点包含一个值以及指向下一个节点的指针。
    • 特点：节点之间通过指针连接，形成一个链式结构，可以是单向链表、双向链表等。
    • 插入操作：在链表中插入新节点可以在 O(1) 时间内完成，只需调整指针的指向。
    • 查询操作：需要从头节点开始依次遍历链表，时间复杂度为 O(n)。
    • 删除操作：通过调整节点之间的指针，可以在 O(1) 时间内完成删除操作。

数组排序，

  • 优点：可以使用二分查找，查找速度快，
  • 缺点：为了保证数组有序，在添加新数据时，找到插入位置后，后面的数据需整体移动，速度慢。[示意图]
    使用链式存储-链表
  • 不管链表是否有序，查找速度都慢，添加数据速度比数组快，不需要数据整体移动。[示意图]

二叉排序树概念

二叉排序树（Binary Search Tree，简称BST）是一种特殊的二叉树，它满足以下条件：

  • 左子树上所有节点的值小于根节点的值。
  • 右子树上所有节点的值大于根节点的值。
  • 左右子树也分别为二叉排序树。
    通过这种结构，我们可以快速地进行查找、插入和删除操作。

在一个二叉排序树中，每个节点都存储着一个值，并且左子节点的值小于父节点的值，右子节点的值大于父节点的值。这样的结构使得我们可以利用二叉3树的特性，在平均情况下以O(log n)的时间复杂度进行搜索、插入和删除操作。

对于搜索操作，

  • 我们从根节点开始，比较目标值与当前节点的大小关系，如果目标值小于当前节点的值，则在左子树中继续搜索；如果目标值大于当前节点的值，则在右子树中继续搜索；如果目标值等于当前节点的值，则找到了目标节点。

对于插入操作，

  • 我们从根节点开始，比较要插入节点的值与当前节点的大小关系，如果要插入节点的值小于当前节点的值，并且当前节点的左子节点为空，则将要插入的节点作为当前节点的左子节点；如果要插入节点的值大于当前节点的值，并且当前节点的右子节点为空，则将要插入的节点作为当前节点的右子节点；否则，继续在左子树或右子树中进行插入操作。

对于删除操作，

  • 我们首先找到要删除的节点。如果要删除的节点没有子节点，则直接删除即可；如果要删除的节点只有一个子节点，则将子节点替代要删除的节点；如果要删除的节点有两个子节点，则需要找到其后继节点（即右子树中最小的节点），将其值替代要删除的节点的值，然后再删除后继节点。

二叉排序树在实际应用中有广泛的应用，例如在数据库索引、字典等场景中，都可以使用二叉排序树来提高搜索效率。

分析删除节点

在这里插入图片描述
33在这里插入图片描述

代码

package com.atguigu.binarysorttree;public class BinarySortTreeDemo {public static void main(String[] args) {int[] arr = {7, 3, 10, 12, 5, 1, 9, 2};BinarySortTree binarySortTree = new BinarySortTree();//循环的添加结点到二叉排序树for(int i = 0; i< arr.length; i++) {binarySortTree.add(new Node(arr[i]));}//中序遍历二叉排序树System.out.println("中序遍历二叉排序树~");binarySortTree.infixOrder(); // 1, 3, 5, 7, 9, 10, 12//测试一下删除叶子结点binarySortTree.delNode(12);binarySortTree.delNode(5);binarySortTree.delNode(10);binarySortTree.delNode(2);binarySortTree.delNode(3);binarySortTree.delNode(9);binarySortTree.delNode(1);binarySortTree.delNode(7);System.out.println("root=" + binarySortTree.getRoot());System.out.println("删除结点后");binarySortTree.infixOrder();}}//创建二叉排序树
class BinarySortTree {private Node root;public Node getRoot() {return root;}//查找要删除的结点public Node search(int value) {if(root == null) {return null;} else {return root.search(value);}}//查找父结点public Node searchParent(int value) {if(root == null) {return null;} else {return root.searchParent(value);}}//编写方法: //1. 返回的 以node 为根结点的二叉排序树的最小结点的值//2. 删除node 为根结点的二叉排序树的最小结点/*** * @param node 传入的结点(当做二叉排序树的根结点)* @return 返回的 以node 为根结点的二叉排序树的最小结点的值*/public int delRightTreeMin(Node node) {Node target = node;//循环的查找左子节点，就会找到最小值while(target.left != null) {target = target.left;}//这时 target就指向了最小结点//删除最小结点delNode(target.value);return target.value;}//删除结点public void delNode(int value) {if(root == null) {return;}else {//1.需求先去找到要删除的结点  targetNodeNode targetNode = search(value);//如果没有找到要删除的结点if(targetNode == null) {return;}//如果我们发现当前这颗二叉排序树只有一个结点if(root.left == null && root.right == null) {root = null;return;}//去找到targetNode的父结点Node parent = searchParent(value);//如果要删除的结点是叶子结点if(targetNode.left == null && targetNode.right == null) {//判断targetNode 是父结点的左子结点，还是右子结点if(parent.left != null && parent.left.value == value) { //是左子结点parent.left = null;} else if (parent.right != null && parent.right.value == value) {//是由子结点parent.right = null;}} else if (targetNode.left != null && targetNode.right != null) { //删除有两颗子树的节点int minVal = delRightTreeMin(targetNode.right);targetNode.value = minVal;} else { // 删除只有一颗子树的结点//如果要删除的结点有左子结点 if(targetNode.left != null) {if(parent != null) {//如果 targetNode 是 parent 的左子结点if(parent.left.value == value) {parent.left = targetNode.left;} else { //  targetNode 是 parent 的右子结点parent.right = targetNode.left;} } else {root = targetNode.left;}} else { //如果要删除的结点有右子结点 if(parent != null) {//如果 targetNode 是 parent 的左子结点if(parent.left.value == value) {parent.left = targetNode.right;} else { //如果 targetNode 是 parent 的右子结点parent.right = targetNode.right;}} else {root = targetNode.right;}}}}}//添加结点的方法public void add(Node node) {if(root == null) {root = node;//如果root为空则直接让root指向node} else {root.add(node);}}//中序遍历public void infixOrder() {if(root != null) {root.infixOrder();} else {System.out.println("二叉排序树为空，不能遍历");}}
}//创建Node结点
class Node {int value;Node left;Node right;public Node(int value) {this.value = value;}//查找要删除的结点/*** * @param value 希望删除的结点的值* @return 如果找到返回该结点，否则返回null*/public Node search(int value) {if(value == this.value) { //找到就是该结点return this;} else if(value < this.value) {//如果查找的值小于当前结点，向左子树递归查找//如果左子结点为空if(this.left  == null) {return null;}return this.left.search(value);} else { //如果查找的值不小于当前结点，向右子树递归查找if(this.right == null) {return null;}return this.right.search(value);}}//查找要删除结点的父结点/*** * @param value 要找到的结点的值* @return 返回的是要删除的结点的父结点，如果没有就返回null*/public Node searchParent(int value) {//如果当前结点就是要删除的结点的父结点，就返回if((this.left != null && this.left.value == value) || (this.right != null && this.right.value == value)) {return this;} else {//如果查找的值小于当前结点的值, 并且当前结点的左子结点不为空if(value < this.value && this.left != null) {return this.left.searchParent(value); //向左子树递归查找} else if (value >= this.value && this.right != null) {return this.right.searchParent(value); //向右子树递归查找} else {return null; // 没有找到父结点}}}@Overridepublic String toString() {return "Node [value=" + value + "]";}//添加结点的方法//递归的形式添加结点，注意需要满足二叉排序树的要求public void add(Node node) {if(node == null) {return;}//判断传入的结点的值，和当前子树的根结点的值关系if(node.value < this.value) {//如果当前结点左子结点为nullif(this.left == null) {this.left = node;} else {//递归的向左子树添加this.left.add(node);}} else { //添加的结点的值大于 当前结点的值if(this.right == null) {this.right = node;} else {//递归的向右子树添加this.right.add(node);}}}//中序遍历public void infixOrder() {if(this.left != null) {this.left.infixOrder();}System.out.println(this);if(this.right != null) {this.right.infixOrder();}}}

运行结果

E:\jdk\jdk1.8.0_161\bin\java.exe "-javaagent:D:\IDEA\IntelliJ IDEA 2022.2.1\lib\idea_rt.jar=62543:D:\IDEA\IntelliJ IDEA 2022.2.1\bin" -Dfile.encoding=UTF-8 -classpath E:\jdk\jdk1.8.0_161\jre\lib\charsets.jar;E:\jdk\jdk1.8.0_161\jre\lib\deploy.jar;E:\jdk\jdk1.8.0_161\jre\lib\ext\access-bridge-64.jar;E:\jdk\jdk1.8.0_161\jre\lib\ext\cldrdata.jar;E:\jdk\jdk1.8.0_161\jre\lib\ext\dnsns.jar;E:\jdk\jdk1.8.0_161\jre\lib\ext\jaccess.jar;E:\jdk\jdk1.8.0_161\jre\lib\ext\jfxrt.jar;E:\jdk\jdk1.8.0_161\jre\lib\ext\localedata.jar;E:\jdk\jdk1.8.0_161\jre\lib\ext\nashorn.jar;E:\jdk\jdk1.8.0_161\jre\lib\ext\sunec.jar;E:\jdk\jdk1.8.0_161\jre\lib\ext\sunjce_provider.jar;E:\jdk\jdk1.8.0_161\jre\lib\ext\sunmscapi.jar;E:\jdk\jdk1.8.0_161\jre\lib\ext\sunpkcs11.jar;E:\jdk\jdk1.8.0_161\jre\lib\ext\zipfs.jar;E:\jdk\jdk1.8.0_161\jre\lib\javaws.jar;E:\jdk\jdk1.8.0_161\jre\lib\jce.jar;E:\jdk\jdk1.8.0_161\jre\lib\jfr.jar;E:\jdk\jdk1.8.0_161\jre\lib\jfxswt.jar;E:\jdk\jdk1.8.0_161\jre\lib\jsse.jar;E:\jdk\jdk1.8.0_161\jre\lib\management-agent.jar;E:\jdk\jdk1.8.0_161\jre\lib\plugin.jar;E:\jdk\jdk1.8.0_161\jre\lib\resources.jar;E:\jdk\jdk1.8.0_161\jre\lib\rt.jar;D:\课程\java课程\guiGu_suanFa\out\production\guiGu_suanFa com.atguigus.binarysorttree.BinarySortTreeDemo
中序遍历二叉排序树~
Node [value=1]
Node [value=2]
Node [value=3]
Node [value=5]
Node [value=7]
Node [value=9]
Node [value=10]
Node [value=12]
root=null
删除结点后
二叉排序树为空，不能遍历Process finished with exit code 0

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

如若内容造成侵权/违法违规/事实不符，请联系瞎胡闹网进行投诉反馈，一经查实，立即删除！

相关文章

【React源码 - 调度任务循环EventLoop】

【React源码 - 调度任务循环EventLoop】

我们知道在React中有4个核心包、2个关键循环。而React正是在这4个核心包中运行&#xff0c;从输入到输出渲染到web端&#xff0c;主要流程可简单分为一下4步&#xff1a;如下图&#xff0c;本文主要是介绍两大循环中的任务调度循环。 4个核心包&#xff1a; react&#xff1a;…
阅读更多...
SpringMVC了解

SpringMVC了解

1.springMVC概述 Spring MVC&#xff08;Model-View-Controller&#xff09;是基于 Java 的 Web 应用程序框架&#xff0c;用于开发 Web 应用程序。它通过将应用程序分为模型&#xff08;Model&#xff09;、视图&#xff08;View&#xff09;和控制器&#xff08;Controller&a…
阅读更多...
SpringMVC 学习（八）之文件上传与下载

SpringMVC 学习（八）之文件上传与下载

目录 1 文件上传 2 文件下载 1 文件上传 SpringMVC 对文件的上传做了很好的封装&#xff0c;提供了两种解析器。 CommonsMultipartResolver&#xff1a;兼容性较好&#xff0c;可以兼容 Servlet3.0 之前的版本&#xff0c;但是它依赖了 commons-fileupload …
阅读更多...
kubectl 命令行管理K8S（上）

kubectl 命令行管理K8S（上）

目录 陈述式资源管理方式 介绍 命令 项目的生命周期 创建 kubectl create命令 发布 kubectl expose命令 更新 kubectl set 回滚 kubectl rollout 删除 kubectl delete 应用发布策略 金丝雀发布 陈述式资源管理方式 介绍 1.kubernetes 集群管理集群资源…
阅读更多...
python 基础知识点（蓝桥杯python科目个人复习计划53）

python 基础知识点（蓝桥杯python科目个人复习计划53）

今日复习内容&#xff1a;做题 例题1&#xff1a;最大的卡牌价值 问题描述&#xff1a; 给定n副卡牌&#xff0c;每张卡牌具有正反面&#xff0c;正面朝上数字为ai&#xff0c;背面朝上数字为bi。一副卡牌的价值为正面朝上数字之和&#xff0c;一开始所有卡牌都是正面朝上的…
阅读更多...
【已解决】用ArcGIS处理过的数据在QGIS中打开发生偏移怎么办？| 数据在ArcGIS中打开位置正常，在QGIS中偏移

【已解决】用ArcGIS处理过的数据在QGIS中打开发生偏移怎么办？| 数据在ArcGIS中打开位置正常，在QGIS中偏移

1. 问题描述 栅格或者矢量数据用ArcGIS打开时位置正确&#xff08;可以和其他数据对应上&#xff09;。但是用QGIS打开后发现位置不对 2. 问题的原因 因为该数据用了ArcGIS自定义的坐标系&#xff0c;QGIS不支持&#xff0c;识别有误。因此在数据QGIS中的坐标系参数有误&a…
阅读更多...
HTTP 的 multipart 类型

HTTP 的 multipart 类型

上一篇文章讲到 http 的 MIME 类型 http MIME 类型 里有一个 multipart 多部分对象集合类型&#xff0c;这个类型 http 指南里有讲到&#xff1a;MIME 中的 multipart&#xff08;多部分&#xff09;电子邮件报文中包含多个报文&#xff0c;它们合在一起作为单一的复杂报文发送…
阅读更多...
【生态适配】亚信安慧AntDB数据库与FT-2000+/64处理器完成兼容互认

【生态适配】亚信安慧AntDB数据库与FT-2000+/64处理器完成兼容互认

日前&#xff0c;亚信安慧AntDB数据库完成了与FT-2000/64处理器的兼容互认。经湖南亚信安慧科技有限公司&#xff08;简称“亚信安慧”&#xff09;与飞腾信息技术有限公司&#xff08;简称“飞腾公司”&#xff09;的严格测试&#xff0c;亚信安慧AntDB数据库V6.2在FT-2000/64…
阅读更多...
《大模型时代-ChatGPT开启通用人工智能浪潮》精华摘抄

《大模型时代-ChatGPT开启通用人工智能浪潮》精华摘抄

原书很长&#xff0c;有19.3w字&#xff0c;本文尝试浓缩一下其中的精华。 知识点 GPT相关 谷歌发布LaMDA、BERT和PaLM-E&#xff0c;PaLM 2 Facebook的母公司Meta推出LLaMA&#xff0c;并在博客上免费公开LLM&#xff1a;OPT-175B。 在GPT中&#xff0c;P代表经过预训练(…
阅读更多...
一看就会：使用nvm实现多个版本的node自由切换

一看就会：使用nvm实现多个版本的node自由切换

一、介绍 使用nvm可以方便的在同一台设备上进行多个node版本之间切换&#xff0c;解决不同的项目所使用的node版本不一样的问题 二、安装nvm 如果已安装node环境先卸载后再安装nvm&#xff0c;防止出现不确定错误 1、卸载node环境&#xff0c;并清除node环境变量配置 通过…
阅读更多...
【README 小技巧】 展示gitee中开源项目start

【README 小技巧】 展示gitee中开源项目start

【README 小技巧】 展示gitee中开源项目start <a target"_blank" hrefhttps://gitee.com/wujiawei1207537021/wu-framework-parent><img srchttps://gitee.com/wujiawei1207537021/wu-framework-parent/badge/star.svg altGitee star/></a>
阅读更多...
我在使用 Copilot 时遇到了许可证验证错误。

我在使用 Copilot 时遇到了许可证验证错误。

如果使用的是 Copilot&#xff0c;并收到以下错误消息&#xff0c;请按以下步骤进行操作&#xff1a; We encountered a problem validating your Copilot license. For more information, see https://aka.ms/copilotlicensecheck 请确保使用的是正确的帐户 请确保已使用具…
阅读更多...
Flink动态分区裁剪

Flink动态分区裁剪

1 原理 1.1 静态分区裁剪与动态分区裁剪 静态分区裁剪的原理跟谓词下推是一致的&#xff0c;只是适用的是分区表&#xff0c;通过将where条件中的分区条件下推到数据源达到减少分区扫描的目的   动态分区裁剪应用于Join场景&#xff0c;这种场景下&#xff0c;分区条件在joi…
阅读更多...
kafka平滑升级过程指导

kafka平滑升级过程指导

一、前言 Apache Kafka作为常用的开源分布式流媒体平台&#xff0c;可以实时发布、订阅、存储和处理数据流,多用于作为消息队列获取实时数据&#xff0c;构建对数据流的变化进行实时反应的应用程序&#xff0c;已被数千家公司用于高性能数据管道、流分析、数据集成和任务关键型…
阅读更多...
算法day01_ 27. 移除元素、977.有序数组的平方

算法day01_ 27. 移除元素、977.有序数组的平方

推荐阅读 从零开始学数组&#xff1a;深入浅出&#xff0c;带你掌握核心要点 初探二分法 再探二分法 系统的纪录一下刷算法的过程&#xff0c;之前一直断断续续的刷题&#xff0c;半途而废&#xff0c;现在重新开始。话不多说&#xff0c;开冲&#xff01; 27.移除元素 题目 给…
阅读更多...
js 面试 什么是WebSockets？HTTP和HTTPS有什么不同？web worker是什么？

js 面试 什么是WebSockets？HTTP和HTTPS有什么不同？web worker是什么？

概念&#xff1a; webSocket 是一种在客户端和服务端之间建立持久连接的协议&#xff0c;它提供全双工通信通道&#xff0c;是服务器可以主动向客户端推送数据&#xff0c;同时也可以接受客户端发送的数据。 1 webSocket与https区别&#xff1f; 在网络通信中&#xff0c;We…
阅读更多...
Acceptor监听套接字管理类实现(模块七)

Acceptor监听套接字管理类实现(模块七)

目录 类功能 类定义 类实现 编译测试 类功能 类定义 // 监听套接字管理类 class Acceptor { private:Socket _socket; // 用于创建监听套接字EventLoop *_loop; // 用于对监听套接字进行事件监控Channel _channel; // 用于对监控套接字进行事件管理using AcceptCallback…
阅读更多...
11 PLL IP核

11 PLL IP核

PLL IP 核简介 锁相环&#xff08;PLL&#xff09;作为一种反馈控制电路&#xff0c;其特点是利用外部输入的参考信号来控制环路内部震荡信号的频率和相位。因为锁相环可以实现输出信号频率对输入信号频率的自动跟踪&#xff0c;所以锁相环通常用于闭环跟踪电路。锁相环在工作…
阅读更多...
36.云原生之SpringCloud+k8s实践

36.云原生之SpringCloud+k8s实践

云原生专栏大纲 文章目录 SpringCloudk8s介绍spring-cloud-kubernetes服务发现配置管理负载均衡选主 spring-cloud-bookinfo案例构建项目环境配置namespace部署与验证productpagegatewaybookinfo-admindetailsratingsreviewsreviews-v1reviews-v2 总结 SpringCloudk8s介绍 ht…
阅读更多...
React UI框架Antd 以及 如何按需引入css样式配置（以及过程中各种错误处理方案）

React UI框架Antd 以及 如何按需引入css样式配置（以及过程中各种错误处理方案）

一、react UI框架Antd使用 1.下载模块 npm install antd -S 2.引入antd的样式 import ../node_modules/antd/dist/reset.css; 3.局部使用antd组件 import {Button, Calendar} from antd; import {PieChartTwoTone} from ant-design/icons; {/* 组件汉化配置 */} import l…
阅读更多...
最新文章

Copyright @ 2022~2023