当前位置: 首页 > news >正文

【数据结构】初识二叉搜索树(Binary Search Tree)

文章目录

  • 1. 二叉搜索树的概念
  • 2. 二叉搜索树的操作
    • 1.1 二叉搜索树的查找
    • 1.2 二叉搜索树的插入
    • 1.3 二叉搜索树的删除

在这里插入图片描述

1. 二叉搜索树的概念

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

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

在这里插入图片描述

2. 二叉搜索树的操作

在这里插入图片描述

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

1.1 二叉搜索树的查找

  1. 从根开始比较、查找,比根大则往右边走查找,比根小则往左边走查找。
  2. 最多查找高度次,若走到空还没找到,则这个值不存在。

1.2 二叉搜索树的插入

  1. 树为空,则直接新增节点,赋值给 root 指针
  2. 树不空,按二叉搜索树性质查找插入位置,插入新节点

在这里插入图片描述

1.3 二叉搜索树的删除

首先查找元素是否在二叉搜索树中,如果不存在,就返回;否则要删除的节点可能分下面四种情况

  1. 要删除的节点无孩子节点
  2. 要删除的节点只有左孩子节点
  3. 要删除的节点只有右孩子节点
  4. 要删除的节点有左、右孩子节点

看起来待删除节点有 4 种情况,实际情况 a 可以与情况 b 或者情况 c 合并起来,因此真正的删除过程如下:

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

在这里插入图片描述


本文完

相关文章:

【数据结构】初识二叉搜索树(Binary Search Tree)

文章目录 1. 二叉搜索树的概念2. 二叉搜索树的操作1.1 二叉搜索树的查找1.2 二叉搜索树的插入1.3 二叉搜索树的删除 1. 二叉搜索树的概念 二叉搜索树又称二叉排序树,它可能是一棵空树,也可能是具有以下性质的二叉树: 若它的左子树不为空&am…...

数据库系统概念(第一周)

⚽前言 🏐四个基本概念 一、数据 定义 种类 特点 二、数据库 三、数据库管理系统(DBMS) 四、 数据库系统(DBS) 🏀数据库系统和文件系统对比 文件系统的弊端 🥎数据视图 数据抽象 …...

如何确定限流阈值:面试官问我,我怎么答?

在面试过程中,系统高并发是经常需要考察的,而熔断限流又是必考的,当面试官问及如何确定限流的阈值时,他们实际上是在考察你是否理解限流的本质及其在实际工作中是否有过经验。限流是一种常用的系统保护措施,用于防止过…...

HW干货集合 | HW面试题记录(1)

整理最近护网面试问的问题 前言 一开始会问问你在工作中负责的是什么工作(如果在职),参与过哪些项目。还有些会问问你之前有没有护网的经历,如果没有的话一般都会被定到初级(技术特牛的另说)。下面就是一…...

数据集踩的坑及解决方案汇总

数据集踩的坑及解决方案汇总 数据集各种格式构建并训练自己的数据集汇总Yolo系列SSDMask R-CNN报错 NotADirectoryError: [Errno 20] Not a directory: /Users/mia/Desktop/P-Clean/mask-RCNN/PennFudanPed2/labelme_json/.DS_StoreFaster R-CNN数据的格式转换划分数据集设定内…...

机器学习流程—数据预处理 Encoding

机器学习流程—数据预处理 Encoding 在机器学习中,我们经常会遇到分类变量,这些分量变量往往机器学习模型没有办法从中学习,往往有两种,一种是字符型,一种是数值型。通常需要对分类型变量做一些处理,常用的方法有两种:label encoding和one hot encoding。 例如,假设数…...

04-微服务 面试题

目录 1.Spring Cloud 常见的组件有哪些? 2.服务注册和发现是什么意思?(Spring Cloud 如何实现服务注册发现) 3.你们项目负载均衡如何实现的 ? 4.什么是服务雪崩,怎么解决这个问题? 5.你们服务是怎么监控的? 6.微服务限流(漏桶算法、令牌桶算法) 7.解释一下CAP…...

Qt连接所有同类部件到同一个槽函数

void MainWindow::AutoConnectSignals() {// 查找所有 QSpinBoxconst auto spinBoxes findChildren<QSpinBox*>();for (auto *spinBox : spinBoxes){connect(spinBox, static_cast<void(QSpinBox::*)(int)>(&QSpinBox::valueChanged), this, &ParameterW…...

spring boot 使用 webservice

spring boot 使用 webservice 使用 java 自带的 jax-ws 依赖 如果是jdk1.8,不需要引入任何依赖&#xff0c;如果大于1.8 <dependency><groupId>javax.jws</groupId><artifactId>javax.jws-api</artifactId><version>1.1</version&g…...

【嵌入式】嵌入式系统稳定性建设:最后的防线

&#x1f9d1; 作者简介&#xff1a;阿里巴巴嵌入式技术专家&#xff0c;深耕嵌入式人工智能领域&#xff0c;具备多年的嵌入式硬件产品研发管理经验。 &#x1f4d2; 博客介绍&#xff1a;分享嵌入式开发领域的相关知识、经验、思考和感悟。提供嵌入式方向的学习指导、简历面…...

【算法】一类支持向量机OC-SVM

【算法】一类支持向量机OC-SVM 前言一类支持向量机OC-SVM 概念介绍示例编写数据集创建实现一类支持向量机OC-SVM完整的示例输出 前言 由于之前毕设期间主要的工具就是支持向量机&#xff0c;从基础的回归和分类到后来的优化&#xff0c;在接触到支持向量机还有一类支持向量机的…...

深入学习默认成员函数——c++指南

前言&#xff1a;类和对象是面向对象语言的重要概念。 c身为一门既面向过程&#xff0c;又面向对象的语言。 想要学习c&#xff0c; 首先同样要先了解类和对象。 本节就类和对象的几种构造函数相关内容进行深入的解析。 目录 类和对象的基本概念 封装 类域和类体 访问限定符…...

psutil, 一个超级有用的Python库

Python的psutil是一个跨平台的库&#xff0c;可以用于获取系统运行时的各种信息&#xff0c;包括CPU使用率、内存使用情况、磁盘和网络信息等。它主要用来做系统监控&#xff0c;性能分析&#xff0c;进程管理。它实现了同等命令行工具提供的功能&#xff0c;如ps、top、lsof、…...

[Python]`threading.local`创建线程本地数据

在Python中&#xff0c;threading.local是一个用于创建线程本地数据的工具。它允许每个线程拥有自己独立的变量副本&#xff0c;这样可以在多线程程序中避免共享变量带来的问题。 通过使用threading.local&#xff0c;你可以为每个线程创建一个独立的变量空间&#xff0c;这样…...

删除数据表

oracle从入门到总裁:​​​​​​https://blog.csdn.net/weixin_67859959/article/details/135209645 删除数据表属于数据库对象的操作 drop table 表名称; 删除 emp30 表 SQL> drop table emp30;表已删除。 上面这个语句运行后&#xff0c;就会把数据表 emp30 删除 在…...

前端自带的base64转化方法

前端html的base64使用方法window.btoa()和window.atob()_html用window.btoa();-CSDN博客...

图论(二)之最短路问题

最短路 Dijkstra求最短路 文章目录 最短路Dijkstra求最短路栗题思想题目代码代码如下bellman-ford算法分析只能用bellman-ford来解决的题型题目完整代码 spfa求最短路spfa 算法思路明确一下松弛的概念。spfa算法文字说明&#xff1a;spfa 图解&#xff1a; 题目完整代码总结ti…...

.NET Core 日志记录功能详解

在软件开发和运维过程中&#xff0c;日志记录是一个非常重要的功能。它可以帮助开发者跟踪应用程序的运行状况、诊断和监控问题。.NET Core 提供了一个灵活且易于使用的日志系统&#xff0c;本文将详细介绍.NET Core日志的相关概念、配置和使用方法。 1. 什么是日志记录以及它…...

docker——启动各种服务

1.Mysql 2.Redis 3.nginx 4.ES 注意&#xff1a;ES7之后环境为 -e ELASTICSEARCH_HOSTS http://ip地址:9200...

git远程仓库使用

赋值这个地址clone 克隆之后 cd slam_oncloud/ git remote add chenxnew ssh://git192.168.3.40:1022/chenxiao/slam_oncloud.git 查看一下 linuxchenxiao:/media/linux/mydisk/cloud_slam/slam_oncloud$ git remote add chenxnew ssh://git192.168.3.40:1022/chenxiao/sla…...

内存分配函数malloc kmalloc vmalloc

内存分配函数malloc kmalloc vmalloc malloc实现步骤: 1)请求大小调整:首先,malloc 需要调整用户请求的大小,以适应内部数据结构(例如,可能需要存储额外的元数据)。通常,这包括对齐调整,确保分配的内存地址满足特定硬件要求(如对齐到8字节或16字节边界)。 2)空闲…...

FastAPI 教程:从入门到实践

FastAPI 是一个现代、快速&#xff08;高性能&#xff09;的 Web 框架&#xff0c;用于构建 API&#xff0c;支持 Python 3.6。它基于标准 Python 类型提示&#xff0c;易于学习且功能强大。以下是一个完整的 FastAPI 入门教程&#xff0c;涵盖从环境搭建到创建并运行一个简单的…...

【CSS position 属性】static、relative、fixed、absolute 、sticky详细介绍,多层嵌套定位示例

文章目录 ★ position 的五种类型及基本用法 ★ 一、position 属性概述 二、position 的五种类型详解(初学者版) 1. static(默认值) 2. relative(相对定位) 3. absolute(绝对定位) 4. fixed(固定定位) 5. sticky(粘性定位) 三、定位元素的层级关系(z-i…...

GitHub 趋势日报 (2025年06月08日)

&#x1f4ca; 由 TrendForge 系统生成 | &#x1f310; https://trendforge.devlive.org/ &#x1f310; 本日报中的项目描述已自动翻译为中文 &#x1f4c8; 今日获星趋势图 今日获星趋势图 884 cognee 566 dify 414 HumanSystemOptimization 414 omni-tools 321 note-gen …...

如何理解 IP 数据报中的 TTL?

目录 前言理解 前言 面试灵魂一问&#xff1a;说说对 IP 数据报中 TTL 的理解&#xff1f;我们都知道&#xff0c;IP 数据报由首部和数据两部分组成&#xff0c;首部又分为两部分&#xff1a;固定部分和可变部分&#xff0c;共占 20 字节&#xff0c;而即将讨论的 TTL 就位于首…...

Mobile ALOHA全身模仿学习

一、题目 Mobile ALOHA&#xff1a;通过低成本全身远程操作学习双手移动操作 传统模仿学习&#xff08;Imitation Learning&#xff09;缺点&#xff1a;聚焦与桌面操作&#xff0c;缺乏通用任务所需的移动性和灵活性 本论文优点&#xff1a;&#xff08;1&#xff09;在ALOHA…...

关键领域软件测试的突围之路:如何破解安全与效率的平衡难题

在数字化浪潮席卷全球的今天&#xff0c;软件系统已成为国家关键领域的核心战斗力。不同于普通商业软件&#xff0c;这些承载着国家安全使命的软件系统面临着前所未有的质量挑战——如何在确保绝对安全的前提下&#xff0c;实现高效测试与快速迭代&#xff1f;这一命题正考验着…...

CSS设置元素的宽度根据其内容自动调整

width: fit-content 是 CSS 中的一个属性值&#xff0c;用于设置元素的宽度根据其内容自动调整&#xff0c;确保宽度刚好容纳内容而不会超出。 效果对比 默认情况&#xff08;width: auto&#xff09;&#xff1a; 块级元素&#xff08;如 <div>&#xff09;会占满父容器…...

JavaScript基础-API 和 Web API

在学习JavaScript的过程中&#xff0c;理解API&#xff08;应用程序接口&#xff09;和Web API的概念及其应用是非常重要的。这些工具极大地扩展了JavaScript的功能&#xff0c;使得开发者能够创建出功能丰富、交互性强的Web应用程序。本文将深入探讨JavaScript中的API与Web AP…...

RabbitMQ入门4.1.0版本(基于java、SpringBoot操作)

RabbitMQ 一、RabbitMQ概述 RabbitMQ RabbitMQ最初由LShift和CohesiveFT于2007年开发&#xff0c;后来由Pivotal Software Inc.&#xff08;现为VMware子公司&#xff09;接管。RabbitMQ 是一个开源的消息代理和队列服务器&#xff0c;用 Erlang 语言编写。广泛应用于各种分布…...