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

【数据结构&C++】二叉平衡搜索树-AVL树(25)

前言

大家好吖,欢迎来到 YY 滴C++系列 ,热烈欢迎! 本章主要内容面向接触过C++的老铁
主要内容含:
在这里插入图片描述

欢迎订阅 YY滴C++专栏!更多干货持续更新!以下是传送门!

目录

  • 一.AVL树的概念
  • 二.AVL树节点的定义(代码演示)
  • 三.Avl树的基本操作:插入
  • 四.AVL树的核心操作:旋转
    • 【1】新节点插入较高右子树的右侧---右右:左单旋
    • 【2】新节点插入较高左子树的左侧—左左:右单旋
    • 【3】新节点插入较高左子树的右侧---左右:先左单旋再右单旋
    • 【4】新节点插入较高右子树的左侧---右左:先右单旋再左单旋
  • 五.AVL树的验证
      • 1. 验证其为二叉搜索树
      • 2. 验证其为平衡树
  • 六.AVL树的性能&引入红黑树
  • 七.AVL树的完整代码

一.AVL树的概念

  • 二叉搜索树虽可以缩短查找的效率,但如果数据有序或接近有序二叉搜索树将退化为单支树,查找元素相当于在顺序表中搜索元素,效率低下。因此,两位俄罗斯的数学家G.M.Adelson-Velskii和E.M.Landis在1962年发明了一种解决上述问题的方法:当向二叉搜索树中插入新结点后,如果能保证 每个结点的左右子树高度之差的绝对值不超过1 (需要对树中的结点进行调整),即可降低树的高度,从而减少平均搜索长度。
  • 平衡因子是-1,左比右高1;平衡因子是1,右比左高1;平衡因子是0,左右一样高
  • 一棵AVL树或者是空树,或者是具有以下性质的二叉搜索树:
    1. 它的左右子树都是AVL树
    2. 左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)
  • 如果一棵二叉搜索树是高度平衡的,它就是AVL树。如果它有n个结点,其高度可保持在
    O ( l o g 2 n ) O(log_2 n) O(log2n),搜索时间复杂度O( l o g 2 n log_2 n log2n)。

二.AVL树节点的定义(代码演示)

  • 除了基本的左右孩子节点与数据外,还需要引入平衡因子
  • 由于平衡因子取决于左右子树相对高度,所以节点本身 要能够返回父亲节点 ——> 要设置指向父亲节点的指针
  • 注意AVL树节点是三叉链
template<class T>
struct AVLTreeNode
{AVLTreeNode(const T& data): _pLeft(nullptr), _pRight(nullptr), _pParent(nullptr), _data(data), _bf(0){}AVLTreeNode<T>* _pLeft;   // 该节点的左孩子AVLTreeNode<T>* _pRight;  // 该节点的右孩子AVLTreeNode<T>* _pParent; // 该节点的父亲节点T _data;int _bf;                  // 该节点的平衡因子
};

三.Avl树的基本操作:插入

  • AVL树就是在二叉搜索树的基础上引入了平衡因子,因此AVL树也可以看成是二叉搜索树。那么 AVL树的插入过程可以分为两步:
    1. 按照二叉搜索树的方式插入新节点
    2. 调整节点的平衡因子
  • AVL树的插入过程:
  • 与二叉搜索树同理,二叉搜索树博客传送门:https://blog.csdn.net/YYDsis/article/details/134374001?spm=1001.2014.3001.5501
  • 平衡因子的变化步骤:
  1. 新增在左,parent平衡因子减减
  2. 新增在右,parent平衡因子加加
  3. 平衡因子==0,高度不变,直接break
  4. 平衡因子==1/-1,高度改变-> 会影响祖先 -> 需要继续沿着到根节点root的路径向上更新
  5. 平衡因子==2/-2,高度改变& 树不再平衡 ->会影响祖先->需要对parent所在子树进行 旋转 操作,让其平衡 (旋转部分放在part4中详解)
  6. 向上更新,直到根节点(根节点parent==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;}//1. 按照二叉搜索树的方式插入新节点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;//2. 调整节点的平衡因子while (parent)//向上更新,直到根节点(根节点parent==0){if (cur == parent->_left)// 1.新增在左,parent平衡因子减减{parent->_bf--;}else // if (cur == parent->_right){parent->_bf++;//2.新增在右,parent平衡因子加加}if (parent->_bf == 0)//3.平衡因子==0,高度不变,直接break{// 更新结束break;}//4.平衡因子==1/-1,高度改变-> 会影响祖先 -> 需要继续沿着到根节点root的路径向上更新else if (parent->_bf == 1 || parent->_bf == -1){// 继续往上更新cur = parent;parent = parent->_parent;}//平衡因子==2/-2,高度改变& 树不再平衡 ->会影响祖先->//需要对parent所在子树进行 旋转 操作,让其平衡else if (parent->_bf == 2 || parent->_bf == -2){// 子树不平衡了,需要旋转     (旋转部分为何这么设计放在part4中详解)if (parent->_bf == 2 && cur->_bf == 1){RotateL(parent);}else if (parent->_bf == -2 && cur->_bf == -1){RotateR(parent);}else if (parent->_bf == 2 && cur->_bf == -1){RotateRL(parent);}else if (parent->_bf == -2 && cur->_bf == 1){RotateLR(parent);}break;}else{assert(false);}}return true;}

四.AVL树的核心操作:旋转

  • 根据part3中avl树的基本操作"插入",以下情况会出现旋转
  • 平衡因子==2/-2,高度改变& 树不再平衡 ->会影响祖先->需要对parent所在子树进行 旋转 操作,让其平衡 (旋转部分放在part4中详解)
  • 所以一共有四种情况分别如下图所示:
  • 旋转要注意以下两点:
    1. 保持这颗树还是搜索树
    2. 变成平衡树&降低其高度

【1】新节点插入较高右子树的右侧—右右:左单旋

  • 分析:
  • 如下图所示,新节点插入较高右子树的右侧时候,整体会发生“向左的单旋”

在这里插入图片描述

  • 核心操作:
    cur->_right = parent;
    parent->_parent = cur;
  • 代码展示:
void RotateL(Node* parent){Node* cur = parent->_right;Node* curleft = cur->_left;parent->_right = curleft;if (curleft){curleft->_parent = parent;}cur->_left = parent;Node* ppnode = parent->_parent;parent->_parent = cur;if (parent == _root){_root = cur;cur->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = cur;}else{ppnode->_right = cur;}cur->_parent = ppnode;}parent->_bf = cur->_bf = 0;}

【2】新节点插入较高左子树的左侧—左左:右单旋

【3】新节点插入较高左子树的右侧—左右:先左单旋再右单旋

【4】新节点插入较高右子树的左侧—右左:先右单旋再左单旋

五.AVL树的验证

1. 验证其为二叉搜索树

  • 如果其通过 中序遍历 可得到一个有序的序列,就说明为二叉搜索树

2. 验证其为平衡树

  • 每个节点子树高度差的绝对值不超过1(注意节点中如果没有平衡因子)
  • 节点的平衡因子是否计算正确

六.AVL树的性能&引入红黑树

  • AVL树是一棵绝对平衡的二叉搜索树,其要求每个节点的左右子树高度差的绝对值都不超过1,这
    样可以保证查询时高效的时间复杂度,即 l o g 2 ( N ) log_2 (N) log2(N)。但是如果要对AVL树做一些结构修改的操
    作,性能非常低下,比如:插入时要维护其绝对平衡,旋转的次数比较多,更差的是在删除时,
    有可能一直要让旋转持续到根的位置。
    因此:如果需要一种查询高效且有序的数据结构,而且数
    据的个数为静态的(即不会改变),可以考虑AVL树,但一个结构经常修改,就不太适合。 因此需要
    引入红黑树,传送门如下所示:

  • 红黑树博客传送门:

七.AVL树的完整代码

#pragma once#include<iostream>
#include<assert.h>
using namespace std;template<class K, class V>
struct AVLTreeNode
{pair<K, V> _kv;AVLTreeNode<K, V>* _left;AVLTreeNode<K, V>* _right;AVLTreeNode<K, V>* _parent;int _bf;  // balance factorAVLTreeNode(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 // if (cur == parent->_right){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){// 子树不平衡了,需要旋转if (parent->_bf == 2 && cur->_bf == 1){RotateL(parent);}else if (parent->_bf == -2 && cur->_bf == -1){RotateR(parent);}else if (parent->_bf == 2 && cur->_bf == -1){RotateRL(parent);}else if (parent->_bf == -2 && cur->_bf == 1){RotateLR(parent);}break;}else{assert(false);}}return true;}void RotateL(Node* parent){++_rotateCount;Node* cur = parent->_right;Node* curleft = cur->_left;parent->_right = curleft;if (curleft){curleft->_parent = parent;}cur->_left = parent;Node* ppnode = parent->_parent;parent->_parent = cur;if (parent == _root){_root = cur;cur->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = cur;}else{ppnode->_right = cur;}cur->_parent = ppnode;}parent->_bf = cur->_bf = 0;}void RotateR(Node* parent){++_rotateCount;Node* cur = parent->_left;Node* curright = cur->_right;parent->_left = curright;if (curright)curright->_parent = parent;Node* ppnode = parent->_parent;cur->_right = parent;parent->_parent = cur;if (ppnode == nullptr){_root = cur;cur->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = cur;}else{ppnode->_right = cur;}cur->_parent = ppnode;}parent->_bf = cur->_bf = 0;}void RotateRL(Node* parent){Node* cur = parent->_right;Node* curleft = cur->_left;int bf = curleft->_bf;RotateR(parent->_right);RotateL(parent);if (bf == 0){cur->_bf = 0;curleft->_bf = 0;parent->_bf = 0;}else if (bf == 1){cur->_bf = 0;curleft->_bf = 0;parent->_bf = -1;}else if (bf == -1){cur->_bf = 1;curleft->_bf = 0;parent->_bf = 0;}else{assert(false);}}void RotateLR(Node* parent){Node* cur = parent->_left;Node* curright = cur->_right;int bf = curright->_bf;RotateL(parent->_left);RotateR(parent);if (bf == 0){parent->_bf = 0;cur->_bf = 0;curright->_bf = 0;}else if (bf == -1){parent->_bf = 1;cur->_bf = 0;curright->_bf = 0;}else if (bf == 1){parent->_bf = 0;cur->_bf = -1;curright->_bf = 0;}}int Height(){return Height(_root);}int Height(Node* root){if (root == nullptr)return 0;int leftHeight = Height(root->_left);int rightHeight = Height(root->_right);return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;}bool IsBalance(){return IsBalance(_root);}bool IsBalance(Node* root){if (root == nullptr)return true;int leftHight = Height(root->_left);int rightHight = Height(root->_right);if (rightHight - leftHight != root->_bf){cout << "平衡因子异常:" <<root->_kv.first<<"->"<< root->_bf << endl;return false;}return abs(rightHight - leftHight) < 2&& IsBalance(root->_left)&& IsBalance(root->_right);}private:Node* _root = nullptr;public:int _rotateCount = 0;
};

相关文章:

【数据结构&C++】二叉平衡搜索树-AVL树(25)

前言 大家好吖&#xff0c;欢迎来到 YY 滴C系列 &#xff0c;热烈欢迎&#xff01; 本章主要内容面向接触过C的老铁 主要内容含&#xff1a; 欢迎订阅 YY滴C专栏&#xff01;更多干货持续更新&#xff01;以下是传送门&#xff01; 目录 一.AVL树的概念二.AVL树节点的定义(代码…...

Python算法——树的最大深度和最小深度

Python中的树的最大深度和最小深度算法详解 树的最大深度和最小深度是树结构中的两个关键指标&#xff0c;它们分别表示树的从根节点到最深叶子节点的最大路径长度和最小路径长度。在本文中&#xff0c;我们将深入讨论如何计算树的最大深度和最小深度&#xff0c;并提供Python…...

46.全排列-py

46.全排列 class Solution(object):def permute(self, nums):""":type nums: List[int]:rtype: List[List[int]]"""# 结果数组0ans[]nlen(nums)# 判断是否使用state_[False]*n# 临时状态数组dp_[]def dfs (index):# 终止条件if indexn:ans.appe…...

系列三、GC垃圾回收算法和垃圾收集器的关系?分别是什么请你谈谈

一、关系 GC算法&#xff08;引用计数法、复制算法、标记清除算法、标记整理算法&#xff09;是方法论&#xff0c;垃圾收集器是算法的落地实现。 二、4种主要垃圾收集器 4.1、串行垃圾收集器&#xff08;Serial&#xff09; 它为单线程环境设计&#xff0c;并且只使用一个线程…...

WPF中的虚拟化是什么

WPF&#xff08;Windows Presentation Foundation&#xff09;中的虚拟化是一种性能优化技术&#xff0c;它主要用于提高大量数据展示的效率。在WPF中&#xff0c;如果你有一个包含大量项的ItemsControl&#xff08;例如ListBox、ListView或DataGrid等&#xff09;&#xff0c;…...

免费稳定几乎无门槛,我的ChartGPT助手免费分享给你

公众号「架构成长指南」&#xff0c;专注于生产实践、云原生、分布式系统、大数据技术分享。 概述 ChatGPT想必大家应该都不陌生了&#xff0c;大部分人或多或少都接触了&#xff0c;好多应该都是通过openAi的官方进行使用的&#xff0c;这个门槛对大部分人有点高&#xff0c;…...

奇瑞金融:汽车金融行业架构设计

拆借联合贷款abs...

milvus数据库分区管理

一、创建分区 在创建集合时&#xff0c;会默认创建分区_default。 自己手动创建如下&#xff1a; from pymilvus import Collection collection Collection("book") # Get an existing collection. collection.create_partition("novel")二、检测分…...

pytorch.nn.Conv1d详解

通读了从论文中找的代码&#xff0c;终于找到这个痛点了&#xff01; 以下详解nn.Conv1d方法 1 参数说明 in_channels(int) – 输入信号的通道。 out_channels(int) – 卷积产生的通道。 kernel_size(int or tuple) - 卷积核的尺寸&#xff0c;经测试后卷积核的大小应为in_cha…...

大数据HCIE成神之路之数学(2)——线性代数

线性代数 1.1 线性代数内容介绍1.1.1 线性代数介绍1.1.2 代码实现介绍 1.2 线性代数实现1.2.1 reshape运算1.2.2 转置实现1.2.3 矩阵乘法实现1.2.4 矩阵对应运算1.2.5 逆矩阵实现1.2.6 特征值与特征向量1.2.7 求行列式1.2.8 奇异值分解实现1.2.9 线性方程组求解 1.1 线性代数内…...

音视频学习(十八)——使用ffmepg实现视音频解码

视频解码 初始化 视频常用的编解码器id定义&#xff08;以h264和h265为例&#xff09; // 定义在ffmpeg\include\libavcodec\avcodec.h AV_CODEC_ID_H264 AV_CODEC_ID_H265查找解码器&#xff1a;根据编解码id查看解码器 AVCodec* pCodecVideo avcodec_find_decoder(codec…...

nginx的GeoIP模块

使用场景 过滤指定地区/国家的IP&#xff0c;一般是国外IP禁止请求。 使用geoip模块实现不同国家的请求被转发到不同国家的nginx服务器&#xff0c;也就是根据国家负载均衡。 前置知识 GeoIP是什么&#xff1f; 官网地址 https://www.maxmind.com/en/home包含IP地址的地理位…...

mac控制台命令小技巧

shigen日更文章的博客写手&#xff0c;擅长Java、python、vue、shell等编程语言和各种应用程序、脚本的开发。记录成长&#xff0c;分享认知&#xff0c;留住感动。 hello伙伴们&#xff0c;作为忠实的mac骨灰级别的粉丝&#xff0c;它真的给我带来了很多效率上的提升。那作为接…...

Postman:API测试之Postman使用完全指南

Postman是一个可扩展的API开发和测试协同平台工具&#xff0c;可以快速集成到CI/CD管道中。旨在简化测试和开发中的API工作流。 Postman工具有Chrome扩展和独立客户端&#xff0c;推荐安装独立客户端。 Postman有个workspace的概念&#xff0c;workspace分personal和team类型…...

Flume学习笔记(3)—— Flume 自定义组件

前置知识&#xff1a; Flume学习笔记&#xff08;1&#xff09;—— Flume入门-CSDN博客 Flume学习笔记&#xff08;2&#xff09;—— Flume进阶-CSDN博客 Flume 自定义组件 自定义 Interceptor 需求分析&#xff1a;使用 Flume 采集服务器本地日志&#xff0c;需要按照日志…...

go的字符切片和字符串互转

Go 1.21 // 返回一个Slice&#xff0c;它的底层数组自ptr开始&#xff0c;长度和容量都是len func Slice(ptr *ArbitraryType, len IntegerType) []ArbitraryType // 返回一个指针&#xff0c;指向底层的数组 func SliceData(slice []ArbitraryType) *ArbitraryType // 生成一…...

所见即所得的动画效果:Animate.css

我们可以在集成Animate.css来改善界面的用户体验&#xff0c;省掉大量手写css动画的时间。 官网&#xff1a;Animate.css 使用 1、安装依赖 npm install animate.css --save2、引入依赖 import animate.css;3、在项目中使用 在class类名上animate__animated是必须的&#x…...

ERR:Navicat连接Sql Server报错

错误信息&#xff1a;报错&#xff1a;未发现数据源名称并且未指定默认驱动程序。 原因&#xff1a;Navicat没有安装Sqlserver驱动。 解决方案&#xff1a;在Navicat安装目录下找到sqlncli_x64.msi安装即可。 一键安装即可。 Navicat链接SQL Server配置 - MarchXD - 博客园 …...

python算法例10 整数转换为罗马数字

1. 问题描述 给定一个整数&#xff0c;将其转换为罗马数字&#xff0c;要求返回结果的取值范围为1~3999。 2. 问题示例 4→Ⅳ&#xff0c;12→Ⅻ&#xff0c;21→XⅪ&#xff0c;99→XCIX。 3. 代码实现 def int_to_roman(num):val [1000, 900, 500, 400,100, 90, 50, 40…...

springboot引入第三方jar包放到项目目录中,添加web.xml

参考博客&#xff1a;https://www.cnblogs.com/mask-xiexie/p/16086612.html https://zhuanlan.zhihu.com/p/587605618 1、在resources目录下新建lib文件夹&#xff0c;将jar包放到lib文件夹中 2、修改pom.xml文件 <dependency><groupId>com.lanren312</grou…...

Spring Boot 实现流式响应(兼容 2.7.x)

在实际开发中&#xff0c;我们可能会遇到一些流式数据处理的场景&#xff0c;比如接收来自上游接口的 Server-Sent Events&#xff08;SSE&#xff09; 或 流式 JSON 内容&#xff0c;并将其原样中转给前端页面或客户端。这种情况下&#xff0c;传统的 RestTemplate 缓存机制会…...

ETLCloud可能遇到的问题有哪些?常见坑位解析

数据集成平台ETLCloud&#xff0c;主要用于支持数据的抽取&#xff08;Extract&#xff09;、转换&#xff08;Transform&#xff09;和加载&#xff08;Load&#xff09;过程。提供了一个简洁直观的界面&#xff0c;以便用户可以在不同的数据源之间轻松地进行数据迁移和转换。…...

DeepSeek 技术赋能无人农场协同作业:用 AI 重构农田管理 “神经网”

目录 一、引言二、DeepSeek 技术大揭秘2.1 核心架构解析2.2 关键技术剖析 三、智能农业无人农场协同作业现状3.1 发展现状概述3.2 协同作业模式介绍 四、DeepSeek 的 “农场奇妙游”4.1 数据处理与分析4.2 作物生长监测与预测4.3 病虫害防治4.4 农机协同作业调度 五、实际案例大…...

jmeter聚合报告中参数详解

sample、average、min、max、90%line、95%line,99%line、Error错误率、吞吐量Thoughput、KB/sec每秒传输的数据量 sample&#xff08;样本数&#xff09; 表示测试中发送的请求数量&#xff0c;即测试执行了多少次请求。 单位&#xff0c;以个或者次数表示。 示例&#xff1a;…...

Golang——7、包与接口详解

包与接口详解 1、Golang包详解1.1、Golang中包的定义和介绍1.2、Golang包管理工具go mod1.3、Golang中自定义包1.4、Golang中使用第三包1.5、init函数 2、接口详解2.1、接口的定义2.2、空接口2.3、类型断言2.4、结构体值接收者和指针接收者实现接口的区别2.5、一个结构体实现多…...

在树莓派上添加音频输入设备的几种方法

在树莓派上添加音频输入设备可以通过以下步骤完成&#xff0c;具体方法取决于设备类型&#xff08;如USB麦克风、3.5mm接口麦克风或HDMI音频输入&#xff09;。以下是详细指南&#xff1a; 1. 连接音频输入设备 USB麦克风/声卡&#xff1a;直接插入树莓派的USB接口。3.5mm麦克…...

【UE5 C++】通过文件对话框获取选择文件的路径

目录 效果 步骤 源码 效果 步骤 1. 在“xxx.Build.cs”中添加需要使用的模块 &#xff0c;这里主要使用“DesktopPlatform”模块 2. 添加后闭UE编辑器&#xff0c;右键点击 .uproject 文件&#xff0c;选择 "Generate Visual Studio project files"&#xff0c;重…...

热门Chrome扩展程序存在明文传输风险,用户隐私安全受威胁

赛门铁克威胁猎手团队最新报告披露&#xff0c;数款拥有数百万活跃用户的Chrome扩展程序正在通过未加密的HTTP连接静默泄露用户敏感数据&#xff0c;严重威胁用户隐私安全。 知名扩展程序存在明文传输风险 尽管宣称提供安全浏览、数据分析或便捷界面等功能&#xff0c;但SEMR…...

Vue3中的computer和watch

computed的写法 在页面中 <div>{{ calcNumber }}</div>script中 写法1 常用 import { computed, ref } from vue; let price ref(100);const priceAdd () > { //函数方法 price 1price.value ; }//计算属性 let calcNumber computed(() > {return ${p…...

Spring AOP代理对象生成原理

代理对象生成的关键类是【AnnotationAwareAspectJAutoProxyCreator】&#xff0c;这个类继承了【BeanPostProcessor】是一个后置处理器 在bean对象生命周期中初始化时执行【org.springframework.beans.factory.config.BeanPostProcessor#postProcessAfterInitialization】方法时…...