数据结构复习 (二叉查找树,高度平衡树AVL)
1.二叉查找树:
为了更好的实现动态的查找(可以插入/删除),并且不超过logn的时间下达成目的
定义: 二叉查找树（亦称二叉搜索树、二叉排序树）是一棵二叉树，其各结点关键词互异，且中根序列按其关键词递增排列。
等价描述: 二叉查找树中任一结点P，其左子树中结点的关键词都小于P的关键词，右子树中结点的关键词都大于P的关键词，且结点P的左右子树也都是二叉查找树。
节点:
BTSTreenode,有左右子树,有键值
有的操作是:
查找,插入和删除,
其他的创建和排序都可以通过上述完成
1,查找:
通过和当前的节点比较大小,来确定之后是:F.返回答案S.去更小的左边,T.去更大的右边
BSTnode* Search(BSTnode* root, int K){
if (root == NULL || root->key == K) return root;
if (K < root->key) return Search(root->left, K);
else return Search(root->right, K);
}
2,插入
根据和左右比较的方法来选择左边还是右边插入,但是不会插入相同的节点
可以引用实现,也可以是返回值实现
引用:
void insert(node*& root,int k){
If(root==NULL||root->val==k){
root=new node(k);
Return;
}
If(k>root->k)insert(root->left,k);
Else insert(root->right,k);
}
返回:
node* insert(node* root,int k){
If(root==NULL)return new node(k);
If(root->val==k)return root;
If(root->val>k)root->right=insert(root->right,k);
Else root->left=insert(root->left,k);
Return root;
}
3,删除,就是通过查找,然后判断:
,没有子树,直接删除
,有一个子树,直接上提
,两个子树,让右边最小的节点s上提到当前位置,之后删除S
void remove(BSTnode* &root, int K) {
if(root==NULL) return;
if(K<root->key) remove(root->left, K); //在左子树删K
else if(K>root->key) remove(root->right, K); //在右子树删K
else if(root->left!=NULL && root->right!=NULL){ //非根节点删除
BSTnode *s=root->right;
while(s->left!=NULL) s=s->left;
root->key=s->key; //s为t右子树中根序列第一个结点
remove(root->right, s->key);
}
else{ //根节点删除
BSTnode* oldroot=root;
root=(root->left!=NULL)? root->left:root->right;
delete oldroot;
}
}
numofBST
F[i]=f[i-1]*(4*i-2)/(i+1)
二叉查找树总结
➢则由n个互异关键词随机生成的二叉查找树，平均高度为O(logn)
➢查找、插入、删除平均时间复杂度O(logn)，但最坏情况时间复杂度为O(n)
2,高度平衡树:(AVL)
为了防止出现二叉查找树发生左/右偏的情况出现的,让一个树的左右高度相差不大于1
平衡系数:左子树高度-右子树高度
高度为h的AVL至少有
所以n>=2^(h/2),同理,h<=2logn
一颗AVL平均比完全二叉树高44%
节点AVLnode 记录的信息是键值,高度,左右子树
初始的时候每个节点的高度是0,空节点的高度为-1
具体操作:
1,计算高度
Int update_H(node* t){
If(t==NULL)return -1;
Int l=update_H(t->left);
Int r=update_H(t->right);
- >height=max(l,r)+1;
Return t->height;
}
Int Height(node* a){
Return a==NULL?-1”a->height;
}
2,旋转操作:
当前子树为root
左边的子树的高度为l1,右边为r1
2.1左边更高
2.1.1 左边的左边发生了插入,让左边提升
我们需要把B提升,A下降然后b右子树变成a的左子树
插入前后我们发现,高度没变
Void LL(node* & A){
Node* B=a->left;
- >left=B->right;
- >right=A;
Update_H(A);
Update_H(B);
A=B;
}
2.1.2左边的右边发生了插入,让左边的右边提升
将C的更低的子树交给B,然后让C提升,然后让C再次提升,将高的子树交给A
void LR(node* &A) {
RR(A->left);
LL(A);
}
2.2.1右边的右边发生了插入
void RR(AVLnode* &A) {
AVLnode *B = A->right;
A->right = B->left;
B->left = A;
UpdateHeight(A);
UpdateHeight(B);
A = B;
}
2.2.2右边的左边发生了插入
先让A的右子树的左子树上提,然后再让右子树上移动
void RL(AVLnode* &A){
LL(A->right);
RR(A);
}
注意;我们在插入节点时我们需要从下面向上去调整
比如:依次插入关键字5, 4, 2, 8, 6, 9
插入2时:
--->
插入6时:
--->
再插入一个9:
使平衡:
void ReBalance(AVLnode* &t) {
if(t==NULL) return;
if(Height(t->left) - Height(t->right)==2){ //左边更深
if(Height(t->left->left) >= Height(t->left->right)) //左边的左边更深
LL(t);
else //右边更深
LR(t);
}else if(Height(t->right) - Height(t->left)==2){
if(Height(t->right->right) >= Height(t->right->left))
RR(t);
else
RL(t);
}
Update_H(t); //更新高度
}
插入:
void Insert(AVLnode* &root, int K) {
if(root==NULL) root=new AVLnode(K);
else if(K < root->key) //在左子树插入
Insert(root->left, K);
else if(K > root->key) //在右子树插入
Insert(root->right, K);
ReBalance(root);
}
删除
和二叉树的删除差不多,需要注意的是删除之后的平衡的保持
所以代码是一样的,只是最后需要加一个使平衡
void remove(AVLnode* &root, int K) {
if(root==NULL) return;
if(K<root->key) remove(root->left, K);
//在左子树删K
else if(K>root->key) remove(root->right, K); //在右子树删K
else if(root->left!=NULL && root->right!=NULL){
AVLnode *s=root->right;
while(s->left!=NULL) s=s->left;
root->key=s->key; //s为t右子树中根序列第一个结点
remove(root->right, s->key);
}else{
AVLnode* oldroot=root;
root=(root->left!=NULL)? root->left:root->right;
delete oldroot;
}
ReBalance(root);
}
高度平衡树总结
➢AVL树的高度为O(logn)，因此使插入、删除、查找的最坏时间复杂度均为O(logn)。
➢删除操作最坏情况下需要做O(logn)次旋转。
➢对任意连续多次删除操作，每次删除所需的均摊旋转次数为O(1)[1]。对于任意多次插入和删除的混合序列，存在精心构造出的特定操作序列，使每次删除所需的均摊旋转次数为O(logn)
相关文章：
)
数据结构复习 (二叉查找树,高度平衡树AVL)
1.二叉查找树: 为了更好的实现动态的查找(可以插入/删除),并且不超过logn的时间下达成目的 定义: 二叉查找树（亦称二叉搜索树、二叉排序树）是一棵二叉树，其各结点关键词互异，且中根序列按其关键词递增排列。 等价描述: 二叉查找…...
深入浅出梯度下降与反向传播
文章目录 1. 前言2. 基本概念2.1 一元函数的导数2.2 偏导数2.3 方向导数2.4 梯度2.5 均方误差 3. 梯度下降3.1 梯度下降的公式3.2 梯度下降的类型（优化器） 4. 反向传播4.1 反向传播的基本步骤4.2 反向传播的数学推导 5. 实战5.1 手动求导5.2 自动求导5.3…...
)
PLC(01)
一.职业规划 电路----------------->电工------------------>电气-------------------plc---------------------DCS--------------------> 机器人 二.交流电直流电的概念 1.交流电AC alternating current 大小方向随时间发生周期性变化 2.直流电 Direct current…...
)
如何通过本地部署的DIFY辅助学习算法(PS可以辅助帮你学习任何想学习的资料)
如何通过本地部署的DIFY辅助学习算法(PS可以辅助帮你学习任何想学习的资料 一 提升知识库的大小容量1.1 调大知识库的基础配置修改.env文件1.2 通过docker compose 重启加载最新配置1.3 重新上传知识库 二 搭建算法知识库的学习助手2.1 text embedding 模型对比2.1.1 如何选择合…...
深入探讨服务器虚拟化：架构、技术与应用
1. 引言 在现代IT基础设施中，服务器虚拟化已成为一种不可或缺的技术。它不仅提高了资源利用率，还增强了系统的灵活性和可管理性。随着企业对高效、灵活和可扩展IT环境的需求不断增加，服务器虚拟化技术的应用愈发广泛。本文将深入探讨服务器虚…...
C++笔记之尾后迭代器
C笔记之尾后迭代器 code review! 参考笔记 1.C笔记之尾后迭代器 2.C笔记之迭代器失效问题处理 在C中，尾后迭代器（通常称为 past-the-end iterator）是指指向容器中最后一个元素之后的位置的迭代器。它并不指向任何有效的元素，而是…...
2024年总结【第五年了】
2024年总结 北国绕院扫雪，南方围炉烹茶，且饮一杯无? 执笔温暖不曾起舞日子里的点点滴滴，誊写一段回忆，还以光阴一段副本。 那么你要听一支新故事吗？第五年总结的片碎。 衣单天寒，走趟流星孤骑…...
EasyExcel（环境搭建以及常用写入操作）
文章目录 EasyExcel环境搭建1.创建模块 easyexcel-demo2.引入依赖3.启动类创建 EasyExcel写1.最简单的写入1.模板2.方法3.结果 Write01.xlsx 2.指定字段不写入Excel1.模板2.方法3.结果 Write02.xlsx 3.指定字段写入excel1.模板2.方法3.结果 Write03.xlsx 4.按照index顺序写入ex…...
JVM类加载器
什么是类加载器 类加载器（ClassLoader）是Java虚拟机提供给应用程序去实现获取类和接口字节码数据的技术。 类加载器只参与加载过程中的字节码获取并加载到内存这一部分 类加载器的分类 类加载器分为两类，一类是Java代码中实现的࿰…...
druid连接池参数配置
最近发现生产环境经常有数据库连接超时的问题，排查发现是druid连接池参数设置不合理导致 总结问题如下： 为了防止僵尸连接，k8s ipvs做了连接超时限制，如果TCP连接闲置超过900s(15分钟)，客户端再尝试通过这个连接去发起…...
【机器学习】Kaggle实战信用卡反欺诈预测（场景解析、数据预处理、特征工程、模型训练、模型评估与优化）
构建信用卡反欺诈预测模型 建模思路 本项目需解决的问题 本项目通过利用信用卡的历史交易数据，进行机器学习，构建信用卡反欺诈预测模型，提前发现客户信用卡被盗刷的事件。 项目背景 数据集包含由欧洲持卡人于2013年9月使用信用卡进行交的…...
Linux（Ubuntu）下ESP-IDF下载与安装完整流程（2）
接前一篇文章：Linux（Ubuntu）下ESP-IDF下载与安装完整流程（1） 本文主要看参考官网说明，如下： 快速入门 - ESP32-S3 - — ESP-IDF 编程指南 latest 文档 Linux 和 macOS 平台工具链的标准设置 - ESP32-S3 - — ESP-IDF 编程指南 latest 文档 一、安装准备 1. Linux用...
SpringBoot3 快速启动框架
文章目录 1 SpringBoot3 介绍 1.1 SpringBoot3 简介1.2 快速入门1.3 入门总结 2 SpringBoot3 配置文件 2.1 统一配置管理概述2.2 属性配置文件使用2.3 YAML配置文件使用2.4 批量配置文件注入2.5 多环境配置和使用 3 SpringBoot 整合 springMVC 3.1 实现过程3.2 web相关配置3.3…...
Enum枚举类，静态常量类，静态类的区别
Enum枚举类，静态常量类，静态类的区别 Enum枚举类静态常量类静态类Enum枚举类，静态常量类，静态类的区别 Enum枚举类 Enum枚举类的结构组成和用法使用可以查阅 Enum枚举类与静态变量和静态数组的区别 静态常量类 public class St…...
解锁专利世界的钥匙 ——famiwei 网
在知识经济的时代,专利作为创新成果的重要体现,无论是对于企业、科研人员乃至整个社会的发展都具有举足轻重的意义。而在众多的专利网站中,famiwei 网为用户提供了一个全面、精准且高效的专利信息交流与服务的舞台。 一、卓越功能,开启专利探索之门 famiwei 网拥有一套强大的专…...
金融租赁系统的创新与发展推动行业效率提升
金融租赁系统的技术升级与创新 在当今快速发展的金融市场中，金融租赁系统的技术升级与创新充满了无限可能。想象一下，传统的租赁方式就像一位沉闷的老师，而新兴技术就如同一位活泼的学生，不断追求新鲜事物。通过自动化、人工智能…...
SQL-Server链接服务器访问Oracle数据
SQL Server 链接服务器访问 Oracle 离线安装 .NET Framework 3.5 方法一：使用 NetFx3.cab 文件 下载 NetFx3.cab 文件，并将其放置在 Windows 10 系统盘的 C:Windows 文件夹中。 以管理员身份运行命令提示符，输入以下命令并回车： …...
Sonic：开源Go语言开发的高性能博客平台
Sonic：一个用Go语言开发的高性能博客平台 简介 Sonic，一个以其速度如声速般快速而命名的博客平台，是一个用Go语言开发的高性能博客系统。正如其名字所暗示的，Sonic旨在提供一个简单而强大的博客解决方案。这个项目受到了Halo项目…...
【react】常见的性能优化 1
目录 常见的 React 性能优化手段 1. 使用 useMemo 和 useCallback 缓存数据和函数 2. 使用 React.memo 缓存组件 3. 组件懒加载 4. 合理使用 key 5. 在组件销毁时清除定时器/事件 6. 使用 Suspense 和 Lazy 拆分组件 7. 使用 Fragment 避免额外标记 8. 避免使用内联函…...
SpringCloud源码-openFeign
LoadBalancer默认只有nacos服务发现器 openFeign与springcloud loadbalancer的结合点...
QLabel添加点击处理
在QLabel中添加点击事件有三种方式，分别是 使用LinkActivated信号连接槽函数（有缺限）注册事件分发器eventFilter创建类重写鼠标事件 1. 使用LinkActivated信号 QLabel类中有LinkActivated信号，是当标签中的链接被点击的时候触发…...
Markdown表格的使用
Markdown表格的使用 前言语法详解定义表格设定表格列内容的对齐方式 使用场景及实例小结其他文章快来试试吧 Markdown表格的使用👈点击这里也可查看 前言 表格通常作为一种布局的形式，用于结构化的数据展示。 Markdown表格包含三个部分：表头…...
时间序列预测算法介绍
时间序列预测是根据时间序列数据的历史变化规律，对未来数据进行预测的方法。在给定的代码中，使用的是自回归（AR）模型中的AR(4)模型来预测光伏功率。以下将详细解释这种算法： 1. 自回归模型（AR模型…...
加密流量TLS1.2 和TLS1.3的握手区别
加密流量TLS1.2 和TLS1.3的握手区别 TLS1.2 握手均是明文 1）Client Hello 2）Server Hello 3）Certificate TLS1.3 握手中Client Hello是明文，而Server Hello中Extensions以及后面的握手信息不可见 1）Client Hello…...
MySQL数据库——主从复制
本文详细介绍 MySQL的主从复制，从原理到配置再到同步过程。 文章目录 简介核心组件主从复制的原理作用主从复制的线程模型主从复制的模式形式复制的方式设计复制机制主从复制的配置步骤优化和改进总结 简介 MySQL 主从复制（Replication）是一…...
详细说明嵌入式linux中bootcmd与bootargs差异
bootcmd 和 bootargs 是在嵌入式系统开发，特别是基于U-Boot（一个广泛应用的开源引导加载程序）环境中常见的两个重要参数，它们的区别如下： 功能用途 bootcmd： 定义：bootcmd 是U-Boot中的一个环…...
【UE5】UnrealEngine源码构建2：windows构建unreal engine 5.3.2
参考大神知乎的文章：UE5 小白也能看懂的源码编译指南 据说会耗费400G的空间。 代码本身并不大，可能是依赖特别多，毕竟看起来UE啥都能干，核心还是c++的， 【UE5】UnrealEngine源码构建1：tag为5.3.2源码clone 本着好奇+ 学习的态度，想着也许有机会能更为深入的熟悉UE的机制…...
【YOLO算法改进】ALSS-YOLO：无人机热红外图像｜野生动物小目标检测
目录 论文信息 论文创新点 1.自适应轻量通道分割和洗牌（ALSS）模块 2.轻量坐标注意力（LCA）模块 3.单通道聚焦模块 4.FineSIOU损失函数 摘要 架构设计 轻量高效网络架构 - ALSS模块 LCA模块 单通道聚焦模块 损失函数优…...
时间序列预测算法---LSTM
文章目录 一、前言1.1、深度学习时间序列一般是几维数据？每个维度的名字是什么？通常代表什么含义？1.2、为什么机器学习/深度学习算法无法处理时间序列数据?1.3、RNN(循环神经网络)处理时间序列数据的思路？1.4、RNN存在哪些问题?…...
【QT】：QT图形化界面概述
Qt背景介绍 1.1 什么是Qt Qt 是⼀个跨平台的C图形⽤⼾界⾯应⽤程序框架。它为应⽤程序开发者提供了建⽴艺术级图形 界⾯所需的所有功能。它是完全⾯向对象的，很容易扩展。Qt为开发者提供了⼀种基于组件的开发模 式，开发者可以通过简单的拖拽和组合来实现…...
[论文笔记]Representation Learning with Contrastive Predictive Coding
引言 今天带来论文 Representation Learning with Contrastive Predictive Coding的笔记。 提出了一种通用的无监督学习方法从高维数据中提取有用表示，称为对比预测编码(Contrastive Predictive Coding,CPC)。使用了一种概率对比损失， 通过使用负采样使…...
Redis相关
Redis相关 什么是redis?redis可以干什么? Redis是一个c语言编写的nosql数据库(不仅仅是sql,泛指非关系型数据库,一般把非关系型数据库称为nosql数据库),数据在内存中以键值对的形式存储,读写速度快,提供数据持久化方式. 常常被广泛应用到做缓存 Redis使用场景 1.缓存 2…...
【优选算法】Binary-Blade：二分查找的算法刃（上）
文章目录 1.概念解析2.二分查找的简单模版3.二分查找的进阶模版4.x的平方根5.搜索插入位置希望读者们多多三连支持小编会继续更新你们的鼓励就是我前进的动力！ 本篇是优选算法之二分查找算法，该算法是一种高效的在有序数组中查找特定元素的搜索算法 1.概…...
Docker--Docker Network（网络）
Docker Network（网络）是Docker容器之间和容器与外部网络之间的通信和连接的一种机制。以下是对Docker Network的详细解释： 一、Docker网络的重要性 Docker容器网络是为应用程序所创造的虚拟环境的一部分，它能让应用从宿主机操作…...
转化率是衡量网页设计的一个重要指标，请问如何做？
AARRR是互联网产品运营中一个非常重要的模型，这些模型的每一个步骤都涉及到转化率问题，那么AARRR是是什么呢？转化漏斗是什么吗？转化率为什么重要？设计师在做网页设计的时候，如何提升转化率呢？本…...
运维工具之syncthing工具的安装和使用
一、syncthing工具简介 Syncthing是一款开源的文件同步工具，采用Go语言编写。它支持在多个操作系统上运行，包括Windows、macOS和Linux，以及BSD、Solaris和Android等。以下是对这款软件的详细介绍，主要功能： 实时文件同…...
国产数据库-崖山使用介绍
本文档基于崖山数据库23.3 个人版本，单机（主备）部署模式的情况下的使用介绍。 数据库实例状态： NOMOUNT：仅读取参数文件，不加载数据库 MOUNT：读取控制文件，加载数据库ÿ…...
primevue的＜Menu＞组件
1.使用场景 2.代码 1.给你的menu组件起个引用名 2.<Menu>组件需要一个MenuItem[] 3.你要知道MenuItem[ ]的特殊的数据格式，就像TreeNode[ ]一样，数据格式不对是不渲染的。。。。 常用的属性就这几种，js语言和java不一样，J…...
【玩转23种Java设计模式】行为型模式篇：备忘录模式
软件设计模式（Design pattern），又称设计模式，是一套被反复使用、多数人知晓的、经过分类编目的、代码设计经验的总结。使用设计模式是为了可重用代码、让代码更容易被他人理解、保证代码可靠性、程序的重用性。 汇总目录链接&…...
便捷饭店点餐小程序的设计与实现ssm+论文源码调试讲解
第4章 系统设计 一个成功设计的系统在内容上必定是丰富的，在系统外观或系统功能上必定是对用户友好的。所以为了提升系统的价值，吸引更多的访问者访问系统，以及让来访用户可以花费更多时间停留在系统上，则表明该系统设计得比较专…...
微信小程序Uniapp
使用命令行创建项目（vuets） npx degit dcloudio/uni-preset-vue#vite-ts my-vue3-project然后用HBX打开项目 再安装依赖 npm i 再运行开发版本，生成dist目录 pnpm dev:mp-weixin 注意要设置APPid 再用微信小程序打开...
Android GameActivity（NativeActivity）读写文件
最近研究native android相关内容，其中最棘手的就是文件读写问题，最主要的是相关的文档很少。这里写下我所知道的方法。 由于本人使用的是Android14[arm64-v8a]版本的设备,能访问的路径相当有限，如果想要访问更多的路径，就不得不申…...
《计算机网络A》单选题-复习题库解析-2
目录 51、下列关于以太网网卡地址特点的说法中，不正确的是（ ）。 52、当一个Web Browser向一个使用标准服务器端口的Web Server提出请求时，那么在服务返回的响应包中，所使用的源端口是（ ࿰…...
GPU 进阶笔记（二）：华为昇腾 910B GPU
大家读完觉得有意义记得关注和点赞！！！ 1 术语 1.1 与 NVIDIA 术语对应关系1.2 缩写2 产品与机器 2.1 GPU 产品2.2 训练机器 底座 CPU功耗操作系统2.3 性能3 实探：鲲鹏底座 8*910B GPU 主机 3.1 CPU3.2 网卡和网络3.3 GPU 信息 3.3…...
如何利用 ClickHouse 实现高级分析：MySQL 到 ClickHouse 实时数据同步指南
在数据驱动的时代，企业必须依靠先进的数据分析能力来提升竞争力。随着数据量的激增和业务需求的复杂化，传统的关系型数据库已经无法满足高效处理和实时分析的需求。ClickHouse 作为一款高性能的列式数据库，凭借其卓越的查询性能和可扩展性&am…...
Python读取TIF文件
在Python中，逐帧读取TIFF文件（尤其是多页TIFF文件）可以使用tifffile库或Pillow库。以下是两种方法的示例： 方法 1：使用 tifffile 逐帧读取 tifffile 是一个专门用于处理TIFF文件的库，支持多页TIFF文件的逐…...
vue3+ts+element-plus 表单el-form取消回车默认提交
问题描述：在表单el-form中的el-input中按回车后，页面会刷新，url也会改变， 回车前： 回车后： 相关代码： 解决方法1：在 el-form 上阻止默认的 submit 事件，增加 submit.pre…...
面试经典150题——滑动窗口
文章目录 1、长度最小的子数组1.1 题目链接1.2 题目描述1.3 解题代码1.4 解题思路 2、无重复字符的最长子串2.1 题目链接2.2 题目描述2.3 解题代码2.4 解题思路 3、串联所有单词的子串3.1 题目链接3.2 题目描述3.3 解题代码3.4 解题思路 4、最小覆盖子串4.1 题目链接4.2 题目描…...
目标检测之DINO详解
相关链接 论文：[2203.03605] DINO: DETR with Improved DeNoising Anchor Boxes for End-to-End Object Detectionhttps://arxiv.org/abs/2203.03605 代码：...
Linux指令
1. 将一个文件夹中的前5000张图片移动到另一个文件夹 可以使用 find 和 mv 命令来实现将一个文件夹 folder1 中的前 5000 张 jpg 图片移动到另一个文件夹 folder2。下面是具体的步骤： 首先，确保 folder2 存在。如果不存在，可以使用 mkdir 命…...