数据结构--二叉排序树
目录
二叉排序树的定义
二叉排序树的查找
二叉排序树的插入
二叉排序树的构造
二叉排序树的删除
查找效率分析
回顾
二叉排序树的定义
二叉排序树的查找
查找成功的情况
查找失败的情况
二叉排序树的插入
注意
（1）二叉排序树不允许出现重复的值，不能插入相同的结点，所以插入的元素如果是和之前的关键字相同，则插入失败。
（2）递归实现的最坏空间复杂度是O(h)
（3）新插入的结点一定是叶子结点
二叉排序树的构造
二叉排序树的删除
（1）
（2）
比如删除13结点和60结点后的效果
（3）
方法1：
找右子树的直接后继（通过中序排列）
要删除50，用50的右子树，将右子树中序排列（60.61.63.65.66.70）最先访问的结点60，替代要删除的结点50的位置，
删除结果为
方法2：
找左子树（的直接前驱）中最大的值去替代要删除的结点，要删除的结点50的左子树最大的值30，所以用30代替50
删除后的结果如下：
查找效率分析
对比1次就是一层，2次就是第二层,依次类推......
比如：对于70的查找长度就是3次（三层）
对比次数肯定不会超过树的高度，
若树高h，找到最下层的一个结点需要对比h次
查找最好情况就是像平衡二叉树那样
（平衡二叉树：树上任一个结点左子树和右子树的深度之差不超过1）
回顾
相关文章：
数据结构--二叉排序树
目录 二叉排序树的定义 二叉排序树的查找 二叉排序树的插入 二叉排序树的构造 二叉排序树的删除 查找效率分析 回顾 二叉排序树的定义 二叉排序树的查找 查找成功的情况 查找失败的情况 二叉排序树的插入 注意 （1）二叉排序树不允许出现重复的值…...
Python | 根据子列表中的第二个元素对列表进行排序
在本文中，我们将学习如何根据主列表中存在的子列表的第二个元素对任何列表进行排序。 比如 Input : [[‘rishav’, 10], [‘akash’, 5], [‘ram’, 20], [‘gaurav’, 15]] Output : [[‘akash’, 5], [‘rishav’, 10], [‘gaurav’, 15], [‘ram’, 20]] Input …...
qsort函数详细讲解以及利用冒泡排序模拟实现qsort函数
个人主页：点我进入主页 专栏分类：C语言初阶 C语言程序设计————KTV C语言小游戏 C语言进阶 C语言刷题 欢迎大家点赞，评论，收藏。 一起努力，一起奔赴大厂。 目录 1.qsort函数 1.1qsort函数的参数 …...
C++QT day6
1> 将之前定义的栈类和队列类都实现成模板类 栈： #include <iostream> #define MAX 128 using namespace std; template<typename T> class Stack_s { private:T *pnew T[MAX];//栈的数组int top;//记录栈顶的变量 public://构造函数Stack_s(int t…...
List与ArrayList
目录 一、List及其使用 1.1 List的概念 1.2 常见接口的介绍 1.3 List的使用 二、线性表和顺序表 2.1 线性表 2.2 顺序表 三、ArrayList介绍 四、ArrayList的使用 4.1 ArrayList构造 4.2 ArrayList的常用方法 4.3 ArrayList的遍历 4.4 ArrayList的扩容机制 五、ArrayList的具…...
【C++】特殊类的设计
文章目录 1. 设计一个类, 不能被拷贝2. 设计一个类, 不能被继承3. 设计一个类, 只能在堆上创建对象3. 设计一个类, 只能在栈上创建对象4. 创建一个类, 只能创建一个对象(单例模式)饿汉模式懒汉模式 1. 设计一个类, 不能被拷贝 💕 C98方式： 在C11之前&a…...
机器学习：PCA（Principal Component Analysis主成分）降维
参考：PCA降维原理 操作步骤与优缺点_TranSad的博客-CSDN博客 PCA降维算法_偶尔努力翻身的咸鱼的博客-CSDN博客 需要提前了解的数学知识： 一、PCA的主要思想 PCA，即主成分分析方法，是一种使用最广泛的数据降维算法。PCA的主要思想…...
linux服务器slab缓存回收方案设计
背景 自己写的回收slab内存ko，insmod报错“shrink_slab:unknown symbol _x86_indirect_thunk_rax(err 0)””； 分析 1.名词解释 在 x86 架构中，函数调用通常使用 call 指令来直接跳转到目标函数的地址。但是，当需要通过函数指针或动态链接调用函数时，就需要使用__x86_…...
Apache Spark 的基本概念
Apache Spark 是一种快速、可扩展、通用的数据处理引擎。它是一种基于内存的计算框架，支持分布式数据处理、机器学习、图形计算等多种计算任务。与传统的 Hadoop MapReduce 相比，Spark 具有更高的性能和更广泛的应用场景。 Spark 中的基本概念包括&…...
通讯协议介绍CoAP 协议解析
目录 1 通讯协议 2 TCP/IP 网络模型 2.1 TCP协议 2.1.1 TCP 连接过程 2.1.2 TCP 断开连接 2.1.3 TCP协议特点 2.2 UDP协议 2.2.1 UDP 协议特点 3 应用层协议简介 3.1 HTTP 协议 3.2 CoAP 协议 3.3 MQTT 协议 4 CoAP 协议详解 4.1 REST 风格 4.2 CoAP 首部分析 4…...
React 开发一个移动端项目(2)
配置基础路由 目标：配置登录页面的路由并显示在页面中 步骤： 安装路由： yarn add react-router-dom5.3.0 5 和 6 两个版本对组件类型的兼容性和函数组件支持有所改变，在这里使用的是 5。 和路由的类型声明文件 yarn add types…...
51单片机 点阵矩阵 坤坤代码
真正的黑子 #include <REGX52.H>void Delay(unsigned int xms); void _74HC595_WriteByte(unsigned char byte); void LED(unsigned char Y,DATA); void LED_Init();sbit RCKP3^5; //RCLK sbit SCKP3^6; //SRCL sbit SERP3^4; //SER //坤坤矩阵 unsigned char code D…...
Android13-图片视频选择器
在compileSDK 33 时，谷歌在安卓新增了 图片选择器 功能，支持单选、多选、选图片、视频等操作，并且不需要额外获取照片/音频权限。 具体实现如下： 1：请求 Log.d(TAG, "Build.VERSION.SDK_INT" Build.VERS…...
【问题处理】GIT合并解决冲突后，导致其他人代码遗失的排查
GIT合并解决冲突后，导致其他人代码遗失的排查 项目场景问题描述分析与处理：1. 警告分析2. 文件分析3. 问题关键4. 验证 解决策略总结 📕作者简介：战斧，从事金融IT行业，有着多年一线开发、架构经验ÿ…...
H264视频压缩格式
H264简介 H.264从1999年开始，到2003年形成草案，最后在2007年定稿有待核实。在ITU的标准里称为H.264, 在MPEG的标准里是MPEG-4的一个组成部分-MPEG-4 Part 10，又叫Advanced Video Codec，因此常常称为MPEG-4AVC或直接叫AVC。 压缩算…...
动态的中秋爱心演示送女友用python生成爱心软件文末附c++语言写法
用python生成爱心软件 用python生成动态爱心软件 目录 用python生成爱心软件 完整代码 代码解释 逐句解释 效果展示： 如何打包 c写法 完整代码 import turtledef draw_heart():love turtle.Turtle()love.getscreen().bgcolor("black")love.…...
macOS - 使用VLC
文章目录 关于 VLC安装查看帮助流媒体 MRL 语法:URL 语法:主程序 (core)音频视频截图:窗口属性: 子画面屏幕显示（OSD）:字幕:覆盖:轨道设置:播放控制:默认设备:高级: 输入播放列表性能选项: 热键跳跃大小: 关于 VLC VLC media player VLC 是一款自由、开…...
java微服务项目整合skywalking链路追踪框架
skywalking官网网址：Apache SkyWalking 目录 1、安装skywalking 2、微服务接入skywalking 3、skywalking数据持久化 1、安装skywalking 下载skywalking，本篇文章使用的skywalking版本是8.5.0 Index of /dist/skywalkinghttps://archive.apache.org/…...
pandas 笔记： interpolate
一个用于填充 NaN 值的工具 1 基本用法 DataFrame.interpolate(methodlinear, *, axis0, limitNone, inplaceFalse, limit_directionNone, limit_areaNone, downcast_NoDefault.no_default, **kwargs) 2 主要参数 method 多种插值技术 linear: 默认值，使用线性插…...
应用程序接口（API）安全的入门指南
本文简单回顾了 API 的发展历史，其基本概念、功能、相关协议、以及使用场景，重点讨论了与之相关的不同安全要素、威胁、认证方法、以及十二项优秀实践。 根据有记录的历史，随着 Salesforce 的销售自动化解决方案的推出，首个 Web…...
XCTF-web-easyupload
试了试php，php7，pht，phtml等，都没有用 尝试.user.ini 抓包修改将.user.ini修改为jpg图片 在上传一个123.jpg 用蚁剑连接，得到flag...
微软PowerBI考试 PL300-选择 Power BI 模型框架【附练习数据】
微软PowerBI考试 PL300-选择 Power BI 模型框架 20 多年来，Microsoft 持续对企业商业智能 (BI) 进行大量投资。 Azure Analysis Services (AAS) 和 SQL Server Analysis Services (SSAS) 基于无数企业使用的成熟的 BI 数据建模技术。 同样的技术也是 Power BI 数据…...
三维GIS开发cesium智慧地铁教程（5）Cesium相机控制
一、环境搭建 <script src"../cesium1.99/Build/Cesium/Cesium.js"></script> <link rel"stylesheet" href"../cesium1.99/Build/Cesium/Widgets/widgets.css"> 关键配置点： 路径验证：确保相对路径.…...
阿里云ACP云计算备考笔记 (5)——弹性伸缩
目录 第一章 概述 第二章 弹性伸缩简介 1、弹性伸缩 2、垂直伸缩 3、优势 4、应用场景 ① 无规律的业务量波动 ② 有规律的业务量波动 ③ 无明显业务量波动 ④ 混合型业务 ⑤ 消息通知 ⑥ 生命周期挂钩 ⑦ 自定义方式 ⑧ 滚的升级 5、使用限制 第三章 主要定义 …...
在HarmonyOS ArkTS ArkUI-X 5.0及以上版本中，手势开发全攻略：
在 HarmonyOS 应用开发中，手势交互是连接用户与设备的核心纽带。ArkTS 框架提供了丰富的手势处理能力，既支持点击、长按、拖拽等基础单一手势的精细控制，也能通过多种绑定策略解决父子组件的手势竞争问题。本文将结合官方开发文档，…...
2.Vue编写一个app
1.src中重要的组成 1.1main.ts // 引入createApp用于创建应用 import { createApp } from "vue"; // 引用App根组件 import App from ./App.vue;createApp(App).mount(#app)1.2 App.vue 其中要写三种标签 <template> <!--html--> </template>…...
SAP学习笔记 - 开发26 - 前端Fiori开发 OData V2 和 V4 的差异 (Deepseek整理）
上一章用到了V2 的概念，其实 Fiori当中还有 V4，咱们这一章来总结一下 V2 和 V4。 SAP学习笔记 - 开发25 - 前端Fiori开发 Remote OData Service(使用远端Odata服务)，代理中间件（ui5-middleware-simpleproxy）-CSDN博客…...
JVM虚拟机：内存结构、垃圾回收、性能优化
1、JVM虚拟机的简介 Java 虚拟机（Java Virtual Machine 简称：JVM）是运行所有 Java 程序的抽象计算机，是 Java 语言的运行环境，实现了 Java 程序的跨平台特性。JVM 屏蔽了与具体操作系统平台相关的信息，使得 Java 程序只需生成在 JVM 上运行的目标代码（字节码），就可以…...
C++：多态机制详解
目录 一. 多态的概念 1.静态多态（编译时多态） 二.动态多态的定义及实现 1.多态的构成条件 2.虚函数 3.虚函数的重写/覆盖 4.虚函数重写的一些其他问题 1）.协变 2）.析构函数的重写 5.override 和 final关键字 1&#…...
MySQL JOIN 表过多的优化思路
当 MySQL 查询涉及大量表 JOIN 时，性能会显著下降。以下是优化思路和简易实现方法： 一、核心优化思路 减少 JOIN 数量 数据冗余：添加必要的冗余字段（如订单表直接存储用户名）合并表：将频繁关联的小表合并成…...