在家做兼职哪个网站靠谱吗/软文案例
1.AVL的概念
1.AVL树属于二叉搜索树的一种,但它不同与普通的二叉搜索树还具有以下的性质:
每一个根的左右子树的高度差的绝对值不超过1。AVL树是通过高度差去控制平衡的,所以又称作为平衡二叉搜索树。
2.AVL树实现我们引入了一个平衡因子的概念,每一个结点都有它的平衡因子,所谓平衡因子即结点的右子树的高度减去左子树的高度,AVL树的平衡因子有0/1/-1三种,如果平衡因子不属于这三种之一便不是AVL树。
3.AVL树整体结点数量和分布和完全二叉树类似,高度可以控制在logN,那么增删查改的效率也可以控制在O(logN)
下图就为典型的AVL树:
2.AVL树的实现
2.1AVL树的结构
template<class K, class V>
struct AVLTreeNode
{
// 需要parent指针,后续更新平衡因子可以看到
pair<K, V> _kv;
AVLTreeNode<K, V>* _left;
AVLTreeNode<K, V>* _right;
AVLTreeNode<K, V>* _parent;
int _bf; // 平衡因子
AVLTreeNode(const pair<K, V>& kv)
:_kv(kv)
, _left(nullptr)
, _right(nullptr)
, _parent(nullptr)
, _bf(0)
{}
};
template<class K, class V>
class AVLTree
{
typedef AVLTreeNode<K, V> Node;
public:
bool Insert(const pair<K, V>& kv)
{
if (_root == nullptr)
{
_root = new Node(kv);
return true;
}
Node* parent = nullptr;
Node* cur = _root;
while (cur)
{
if (cur->_kv.first < kv.first)
{
parent = cur;
cur = cur->_right;
}
else if (cur->_kv.first > kv.first)
{
parent = cur;
cur = cur->_left;
}
else
{
return false;
}
}
cur = new Node(kv);
if (parent->_kv.first < kv.first)
{
parent->_right = cur;
}
else
{
parent->_left = cur;
}
// 链接父亲
cur->_parent = parent;
// 控制平衡
// 更新平衡因子
while (parent)
{
if (cur == parent->_left)
parent->_bf--;
else
parent->_bf++;
if (parent->_bf == 0)
{
break;
}
else if (parent->_bf == 1 || parent->_bf == -1)
{
cur = parent;
parent = parent->_parent;
}
else if (parent->_bf == 2 || parent->_bf == -2)
{
// 旋转
break;
}
else
{
assert(false);
}
}
return true;
}
private:
Node* _root = nullptr;
};
上面为一个完整的AVL的结构,接下来就是对AVL树的深层次了解
2.2 AVL树的插入
2.2.1 AVL树插入一个值的过程
1.插入一个值按二叉搜索树的规则进行插入
2.如果插入后平衡因子都符合AVL树的规则插入就结束
3.如果不符合AVL树的规则,就更新平衡因子,对不平衡子树进行旋转
2.2.2 平衡因子更新
更新的原则:
1. 平衡因子 = 0/1/-1;
2.插入的结点在右子树则parent的平衡因子++,在左子树则parent的平衡因子--
更新停止条件:
1.更新后parent的平衡因子等于0,更新前的平衡因子为1或者-1,说明一边高一边低,而插入的新结点插入在低的一边,插入后parent所在的子树高度不变,不会影响parent的父亲结点的平衡因子,更新结束。
2.更新后parent的平衡因子等于1或者-1,说明在更新前parent的平衡因子等于0,parent的左右子树一样高,但插入新结点后高度增加1了,就会影响parent的父结点,如果此时父结点不符合AVL树的规则就要去继续更新。
3.更新后parent的平衡因子等于2或者-2,说明更新前parent的平衡因子等于1或者-1,而新插入的结点恰好在较高的子树上。破坏了平衡,parent所在的子树不符合平衡要求,则需要旋转处理。
旋转的目标有两个: 1.把parent子树旋转平衡
2.降低parent子树的高度,恢复到插入结点以前的高度,所以旋转后插入 结束。
2.3 旋转
2.3.1 旋转的原则
1.保持搜索树的原则
2.让旋转的树从不满足变平衡,其次降低旋转树的高度
旋转总共分为四种:左单旋/右单旋/左右双旋/右左双旋
2.3.2 右单旋
在上图中就是右单旋的流程图, 有a/b/c抽象为三颗高度为h的子树(h>=0),a/b/c均符合AVL树的要求,10可能是整数的根也可能是一个整颗树局部的子树的根,该图也只是右单旋的形态之一,但易于理解。
如上图所示:在a点插入了一个新结点导致10的平衡因子变为了-2,为让其符合平衡规则,需要让10的过高的的左子树右旋,如第三步所示,从而控制两颗树的平衡。
核心步骤:因为5 < b子树的值 < 10,将b子树作为10结点的左子树,然后将5变成这颗新树的根,符合了搜索树的规则,控制了平衡,同时这颗树恢复到了之前的h+2,符合旋转原则。
以下的情况就不细讲了,根据第一张的思维可以理解下面的情况:
2.3.3 右单旋代码的实现
void RotateR(Node* parent)
{
Node* subL = parent->_left;
Node* subLR = subL->right;
Node*Pparent = parent ->_parent;
parent ->left = subLR;
if(subLR)
subLR->_parent = parent;
parent ->_parent = subL;
if(Pparent ==nullptr)
{
_root = subL;
subL->_parent =nullptr;
}
else
{
if (parent ==Pparent->_left){Pparent->_left = subL;}else{Pparent->_right = subL;}subL->_parent = Pparent;}subL->_parent = subL->_bf = 0;
}
2.3.4 左单旋
左单旋与右单旋类似,只是从原本过高的左子树的右旋变成现在的过高的右子树的左旋。
其他的情况也和右子树的情况类似这里就不一一列举了
2.3.5 左单旋代码的实现
void RotateRL(Node* parent)
{
Node*subR = parent->right;Node*subRL = parent->left;
Node*Pparent = parent->_parent;
parent ->_right = subRL;
if(subRL)
subRL->_parent = parent;
subR->_left = parent;
parent->_parent = subR;
if(Pparent == nullptr)
{
_root = subR;
subR->_parent = nullptr;
}
else if(Pparent->_left = parent)
{
Pparent ->_left = subR;
}
else
{
Pparent ->_right = subR;
}
subR->_parent = Pparent;
parent->_bf = subR->_bf = 0;
}
2.3.6 左右双旋
从上图可以看出右单旋没有解决两颗树的平衡问题,所以在这里就要使用左右双旋才能解决该问题。
在上图中有三个场景:
场景1:h>=1时,新增结点插入在e子树,e子树高度从h-1并为h并不断更新8->5->10平衡因子,引发旋转,其中8的平衡因子为1,旋转后8和5平衡因子为0,10的平衡因子变为1.
场景2:h >= 1时,新增结点插⼊在f⼦树,f⼦树⾼度从h-1变为h并不断更新8->5->10平衡因⼦,引发旋转,其中8的平衡因⼦为1,旋转后8和10平衡因⼦为0,5平衡因⼦为-1。
场景3:h == 0时,a/b/c都是空树,b⾃⼰就是⼀个新增结点,不断更新5->10平衡因⼦,引发旋 转,其中8的平衡因⼦为0,旋转后8和10和5平衡因⼦均为0。
2.3.7 左右双旋代码实现
void RotateLR(Node* parent)
{
Node*subL = parent ->_left;Node*subLR = subL->_right;
int bf = subLR->_bf;
Rotatel(parent->_left);
RotateR(parent);
if (bf == 0){subL->_bf = 0;subLR->_bf = 0;parent->_bf = 0;}else if (bf == -1){subL->_bf = 0;subLR->_bf = 0;parent->_bf = 1;}else if(bf == 1){subL->_bf = -1;subLR->_bf = 0;parent->_bf = 0;}else{assert(false);}}
2.3.8 右左双旋
同样分三个场景:
场景1:h >= 1时,新增结点插⼊在e⼦树,e⼦树⾼度从h-1变为h并不断更新12->15->10平衡因 ⼦,引发旋转,其中12的平衡因⼦为-1,旋转后10和12平衡因⼦为0,15平衡因⼦为1。
场景2:h >= 1时,新增结点插⼊在f⼦树,f⼦树⾼度从h-1变为h并不断更新12->15->10平衡因⼦,引发旋转,其中12的平衡因⼦为1,旋转后15和12平衡因⼦为0,10平衡因⼦为-1。
场景3:h == 0时,a/b/c都是空树,b⾃⼰就是⼀个新增结点,不断更新15->10平衡因⼦,引发旋 转,其中12的平衡因⼦为0,旋转后10和12和15平衡因⼦均为0。
2.3.9 右左双旋代码实现
void RotateRL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;int bf = subRL->_bf;RotateR(parent->_right);RotateL(parent);if (bf == 0){subR->_bf = 0;subRL->_bf = 0;parent->_bf = 0;}else if (bf == 1){subR->_bf = 0;subRL->_bf = 0;parent->_bf = -1;}else if (bf == -1){subR->_bf = 1;subRL->_bf = 0;parent->_bf = 0;}else{assert(false);}}
相关文章:

AVL树实现
1.AVL的概念 1.AVL树属于二叉搜索树的一种,但它不同与普通的二叉搜索树还具有以下的性质: 每一个根的左右子树的高度差的绝对值不超过1。AVL树是通过高度差去控制平衡的,所以又称作为平衡二叉搜索树。 2.AVL树实现我们引入了一个平衡因子的概…...

初始MYSQL数据库(6)—— 事务
找往期文章包括但不限于本期文章中不懂的知识点: 个人主页:我要学编程(ಥ_ಥ)-CSDN博客 所属专栏: MYSQL 目录 事务的概念 事务的ACID特性 使用事务 查看支持事务的存储引擎 事务的语法 保存点 自动/手动提交事务 事务的隔离性和…...

0基础学习PyTorch——GPU上训练和推理
大纲 创建设备训练推理总结 在《Windows Subsystem for Linux——支持cuda能力》一文中,我们让开发环境支持cuda能力。现在我们要基于《0基础学习PyTorch——时尚分类(Fashion MNIST)训练和推理》,将代码修改成支持cuda的训练和推…...

这款免费工具让你的电脑焕然一新,专业人士都在用
HiBit Uninstaller 采用单一可执行文件的形式,无需复杂的安装过程,用户可以即刻开始使用。这种便捷性使其成为临时使用或紧急情况下的理想选择。尽管体积小巧,但其功能却异常强大,几乎不会对系统性能造成任何负面影响。 这款工具的一大亮点是其多样化的功能。它不仅能够常规卸…...

Java高级Day52-BasicDAO
138.BasicDao 基本说明: DAO:data access object 数据访问对象 这样的通用类,称为 BasicDao,是专门和数据库交互的,即完成对数据库(表)的crud操作 在BasicDao 基础上,实现一张表对应一个Dao,…...

【OceanBase 诊断调优】—— SQL 诊断宝典
视频 OceanBase 数据库 SQL 诊断和优化:https://www.oceanbase.com/video/5900015OB Cloud 云数据库 SQL 诊断与调优的应用实践:https://www.oceanbase.com/video/9000971SQL 优化:https://www.oceanbase.com/video/9000889阅读和管理SQL执行…...

微服务Redis解析部署使用全流程
目录 1、什么是Redis 2、Redis的作用 3、Redis常用的五种基本类型(重要知识点) 4、安装redis 4.1、查询镜像文件【省略】 4.2、拉取镜像文件 4.3、启动redis并设置密码 4.3.1、修改redis密码【可以不修改】 4.3.2、删除密码【坚决不推荐】 5、S…...

C++之STL—常用排序算法
sort (iterator beg, iterator end, _Pred) // 按值查找元素,找到返回指定位置迭代器,找不到返回结束迭代器位置 // beg 开始迭代器 // end 结束迭代器 // _Pred 谓词 random_shuffle(iterator beg, iterator end); // 指定范围内的元素随机调…...

【驱动】地平线X3派:备份与恢复SD卡镜像
1、备份镜像 1.1 安装gparted GParted是硬盘分区软件GNU Parted的GTK+图形界面前端,是GNOME桌面环境的默认分区软件。 GParted可以用于创建、删除、移动分区,调整分区大小,检查、复制分区等操作。可以用于调整分区以安装新操作系统、备份特定分区到另一块硬盘等。 在Ubun…...

【C++报错已解决】std::ios_base::failure
🎬 鸽芷咕:个人主页 🔥 个人专栏: 《C干货基地》《粉丝福利》 ⛺️生活的理想,就是为了理想的生活! 专栏介绍 在软件开发和日常使用中,BUG是不可避免的。本专栏致力于为广大开发者和技术爱好者提供一个关于BUG解决的经…...

matlab入门学习(四)多项式、符号函数、数据统计
一、多项式 %多项式(polynomial)%创建 p[1,2,3,4] %系数向量,按x降幂排列,最右边是常数(x的0次幂) f1poly2str(p,x) %系数向量->好看的字符串 f x^3 2 x^2 3 x 4(不能运算的式子…...

leetcode621. 任务调度器
给你一个用字符数组 tasks 表示的 CPU 需要执行的任务列表,用字母 A 到 Z 表示,以及一个冷却时间 n。每个周期或时间间隔允许完成一项任务。任务可以按任何顺序完成,但有一个限制:两个 相同种类 的任务之间必须有长度为 n 的冷却时…...

Spark 的 Skew Join 详解
Skew Join 是 Spark 中为了解决数据倾斜问题而设计的一种优化机制。数据倾斜是指在分布式计算中,由于某些 key 具有大量数据,而其他 key 数据较少,导致某些分区的数据量特别大,造成计算负载不均衡。数据倾斜会导致个别节点出现性能…...

讯飞星火编排创建智能体学习(一)最简单的智能体构建
目录 开篇 智能体的概念 编排创建智能体 创建第一个智能体 编辑 大模型节点 测试与调试 开篇 前段时间在华为全联接大会上看到讯飞星火企业级智能体平台的演示,对于拖放的可视化设计非常喜欢,刚开始以为是企业用户才有的,回来之后查…...

mac-m1安装nvm,docker,miniconda
1.安装minicondaMAC OS(M1)安装配置miniconda_mac-mini m1 conda-CSDN博客 2.安装nvm(用第二个方法)Mac电脑安装nvm(node包版本管理工具)-CSDN博客 3.安装docker dmg下载链接docker-toolbox-mac-docker-for-mac安装包下载_开源镜像站-阿里云 教程MacOS系…...

STM32F407之Flash
寄存器分类 一般寄存器分为只读存储器 (ROM) 随机存储器(RAM) 只读存储器 只读存储器也被称为ROM 在正常工作时只能读不能写。 只读存储器经历的阶段 ROM->PROM->EPROM->EEPROM ->Flash 优点:掉电不丢失,解构简单 缺点:只适…...

优化 Go 语言数据打包:性能基准测试与分析
场景:在局域网内,需要将多个机器网卡上抓到的数据包同步到一个机器上。 原有方案:tcpdump -w 写入文件,然后定时调用 rsync 进行同步。 改造方案:使用 Go 重写这个抓包逻辑及同步逻辑,直接将抓到的包通过网…...

【SQL】未订购的客户
目录 语法 需求 示例 分析 代码 语法 SELECT columns FROM table1 LEFT JOIN table2 ON table1.common_field table2.common_field; LEFT JOIN(或称为左外连接)是SQL中的一种连接类型,它用于从两个或多个表中基于连接条件返回左表…...

Qt(9.28)
widget.cpp #include "widget.h"Widget::Widget(QWidget *parent): QWidget(parent) {QPushButton *btn1 new QPushButton("登录",this);this->setFixedSize(640,480);btn1->resize(80,40);btn1->move(200,300);btn1->setIcon(QIcon("C:…...

javascript-冒泡排序
前言:好久没学习算法了,今天看了一个视频课,之前掌握很好的冒泡排序居然没写出来? <!DOCTYPE html> <html lang"en"><head><meta charset"UTF-8"><meta name"viewport"…...

第九届蓝桥杯嵌入式省赛程序设计题解析(基于HAL库)
一.题目分析 (1).题目 (2).题目分析 按键功能分析----存储位置的切换键 a. B1按下切换存储位置,切换后定时时间设定为当前位置存储的时间 b. B2短按切换时分秒高亮,设置完成后,长按把设置的时…...

MATLAB云计算集成:在云端扩展计算能力
摘要 MATLAB云计算集成是指将MATLAB的计算能力与云平台的弹性资源相结合,以实现高性能计算、数据处理和算法开发。本文详细介绍了MATLAB云计算的基本概念、优势、配置要点以及编程实践。 1. 云计算概述 云计算是一种通过互联网提供计算资源(如服务器、…...

基于BeagleBone Black的网页LED控制功能(flask+gpiod)
目录 项目介绍硬件介绍项目设计开发环境功能实现控制LED外设构建Webserver 功能展示项目总结 👉 【Funpack3-5】基于BeagleBone Black的网页LED控制功能 👉 Github: EmbeddedCamerata/BBB_led_flask_web_control 项目介绍 基于 BeagleBoard Black 开发板…...

【C语言】单片机map表详细解析
1、RO Size、RW Size、ROM Size分别是什么 首先将map文件翻到最下面,可以看到 1.1 RO Size:只读段 Code:程序的代码部分(也就是 .text 段),它存放了程序的指令和可执行代码。 RO Data:只读…...

Java中的继承和实现
Java中的继承和实现在面向对象编程中扮演着不同的角色,它们之间的主要区别可以从以下几个方面进行阐述: 1. 定义和用途 继承(Inheritance):继承是面向对象编程中的一个基本概念,它允许我们定义一个类&…...

uniapp云打包
ios打包 没有mac电脑,使用香蕉云编 先登录香蕉云编这个工具,新建csr文件——把csr文件下载到你电脑本地: 然后,登录苹果开发者中心 生成p12证书 1、点击+号创建证书 创建证书的时候一定要选择ios distribution app store and ad hoc类型的证书 2、上传刚才从本站生成的…...

端口安全技术原理与应用
目录 概述 端口安全原理 端口安全术语 二层安全地址配置 端口模式下配置 全局模式下配置 动态学习 二层数据包处理流程 三层安全地址配置 三层数据包处理流程 端口安全违例动作和安全地址老化时间 查看命令 端口安全的注意事项 小结 概述 园区网的接入安全关系着…...

数据集-目标检测系列-鲨鱼检测数据集 shark >> DataBall
数据集-目标检测系列-鲨鱼检测数据集 shark >> DataBall 数据集-目标检测系列-鲨鱼检测数据集 shark 数据量:6k 数据样例项目地址: gitcode: https://gitcode.com/DataBall/DataBall-detections-100s/overview github: https://github.com/Te…...

数字乡村解决方案-3
1. 国家大数据战略与数字乡村 中国第十三个五年规划纲要强调实施国家大数据战略,加快建设数字中国,推进数据资源整合和开放共享,保障数据安全,以大数据助力产业转型升级和提高社会治理的精准性与有效性。 2. 大数据与数字经济 …...

WPF文本框无法输入小数点
问题描述 在WPF项目中,文本框BInding双向绑定了数据Text“{UpdateSourceTriggerPropertyChanged}”,但手套数据是double类型,手动输入数据时,小数点输入不进去 解决办法: 在App.xaml.cs文件中添加语句: …...