当前位置: 首页 > 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…...

Qt Widget类解析与代码注释

#include "widget.h" #include "ui_widget.h"Widget::Widget(QWidget *parent): QWidget(parent), ui(new Ui::Widget) {ui->setupUi(this); }Widget::~Widget() {delete ui; }//解释这串代码&#xff0c;写上注释 当然可以&#xff01;这段代码是 Qt …...

Frozen-Flask :将 Flask 应用“冻结”为静态文件

Frozen-Flask 是一个用于将 Flask 应用“冻结”为静态文件的 Python 扩展。它的核心用途是&#xff1a;将一个 Flask Web 应用生成成纯静态 HTML 文件&#xff0c;从而可以部署到静态网站托管服务上&#xff0c;如 GitHub Pages、Netlify 或任何支持静态文件的网站服务器。 &am…...

Nginx server_name 配置说明

Nginx 是一个高性能的反向代理和负载均衡服务器&#xff0c;其核心配置之一是 server 块中的 server_name 指令。server_name 决定了 Nginx 如何根据客户端请求的 Host 头匹配对应的虚拟主机&#xff08;Virtual Host&#xff09;。 1. 简介 Nginx 使用 server_name 指令来确定…...

【Web 进阶篇】优雅的接口设计:统一响应、全局异常处理与参数校验

系列回顾&#xff1a; 在上一篇中&#xff0c;我们成功地为应用集成了数据库&#xff0c;并使用 Spring Data JPA 实现了基本的 CRUD API。我们的应用现在能“记忆”数据了&#xff01;但是&#xff0c;如果你仔细审视那些 API&#xff0c;会发现它们还很“粗糙”&#xff1a;有…...

UR 协作机器人「三剑客」:精密轻量担当(UR7e)、全能协作主力(UR12e)、重型任务专家(UR15)

UR协作机器人正以其卓越性能在现代制造业自动化中扮演重要角色。UR7e、UR12e和UR15通过创新技术和精准设计满足了不同行业的多样化需求。其中&#xff0c;UR15以其速度、精度及人工智能准备能力成为自动化领域的重要突破。UR7e和UR12e则在负载规格和市场定位上不断优化&#xf…...

自然语言处理——循环神经网络

自然语言处理——循环神经网络 循环神经网络应用到基于机器学习的自然语言处理任务序列到类别同步的序列到序列模式异步的序列到序列模式 参数学习和长程依赖问题基于门控的循环神经网络门控循环单元&#xff08;GRU&#xff09;长短期记忆神经网络&#xff08;LSTM&#xff09…...

GC1808高性能24位立体声音频ADC芯片解析

1. 芯片概述 GC1808是一款24位立体声音频模数转换器&#xff08;ADC&#xff09;&#xff0c;支持8kHz~96kHz采样率&#xff0c;集成Δ-Σ调制器、数字抗混叠滤波器和高通滤波器&#xff0c;适用于高保真音频采集场景。 2. 核心特性 高精度&#xff1a;24位分辨率&#xff0c…...

laravel8+vue3.0+element-plus搭建方法

创建 laravel8 项目 composer create-project --prefer-dist laravel/laravel laravel8 8.* 安装 laravel/ui composer require laravel/ui 修改 package.json 文件 "devDependencies": {"vue/compiler-sfc": "^3.0.7","axios": …...

html css js网页制作成品——HTML+CSS榴莲商城网页设计(4页)附源码

目录 一、&#x1f468;‍&#x1f393;网站题目 二、✍️网站描述 三、&#x1f4da;网站介绍 四、&#x1f310;网站效果 五、&#x1fa93; 代码实现 &#x1f9f1;HTML 六、&#x1f947; 如何让学习不再盲目 七、&#x1f381;更多干货 一、&#x1f468;‍&#x1f…...

C# 表达式和运算符(求值顺序)

求值顺序 表达式可以由许多嵌套的子表达式构成。子表达式的求值顺序可以使表达式的最终值发生 变化。 例如&#xff0c;已知表达式3*52&#xff0c;依照子表达式的求值顺序&#xff0c;有两种可能的结果&#xff0c;如图9-3所示。 如果乘法先执行&#xff0c;结果是17。如果5…...