AVL树：高效平衡的二叉搜索树

🌟 快来参与讨论💬，点赞👍、收藏⭐、分享📤，共创活力社区。🌟

在这里插入图片描述

引言🤔

在数据结构的奇妙世界里，二叉搜索树（BST）原本是查找数据的好帮手。想象一下，它就像一本有序的字典，能快速帮我们找到想要的信息。可要是数据排得太整齐，像排队一样有序，二叉搜索树就会“变形”成单支树，这时候查找数据就像在长长的队伍里一个个找，效率低得让人抓狂😫。别担心，1962年，两位聪明的俄罗斯数学家G.M.Adelson - Velskii和E.M.Landis发明了AVL树，给这个问题找到了完美的解决方案👏。

AVL树的概念🧐

1.1 平衡的定义

AVL树就像是一个超级严格的“平衡大师”😏，它不仅是二叉搜索树，还得满足每个节点的左右子树高度差（也就是平衡因子）的绝对值不能超过1。这就好比走钢丝的杂技演员，两边的平衡杆长度差得控制在一定范围内，才能稳稳地走在钢丝上。
在这里插入图片描述

1.2 高度与复杂度

因为AVL树这么会“平衡”，所以哪怕它有好多好多节点（(n)个节点），它的高度也能保持在(O(log_2 n))这个不错的水平。这就意味着，我们查找数据的时候，时间复杂度也是(O(log_2 n))，快得飞起🛫！

AVL树节点的定义📋

要实现AVL树，先得把它的“小砖头”——节点定义好。每个节点都像一个小盒子，装着数据，还有指向左右“小伙伴”（子节点）和“家长”（父节点）的指针，另外还有个记录平衡因子的小标签。下面是用C++ 写的节点定义模板哦👇：

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树插入新数据就像往一个有序的书架上放新书，分两步走：

3.1 二叉搜索树插入

先按照二叉搜索树的规矩，从根节点开始，把新书（新数据）和每个节点的数据比较。要是新书比当前节点的数据小，就往左走；要是大，就往右走，直到找到合适的空位，把新书放进去📚。

3.2 平衡因子调整

新书放进去后，可能会把书架弄“歪”，也就是破坏了AVL树的平衡。这时候就得从新书的“家长”开始，沿着书架往上检查，调整每个节点的平衡因子。在调整过程中，“家长”节点的平衡因子会根据新书插在左边还是右边做相应变化（左边就减1，右边就加1）。这时候“家长”的平衡因子可能出现三种情况：

  • 平衡因子为0：这说明放新书之前，“家长”的平衡因子是正负1，放进去后刚刚好变成0，书架又稳了，插入成功🎉。
  • 平衡因子为正负1：意味着放新书前“家长”的平衡因子是0，放进去后变成正负1，以“家长”为根的这部分书架变高了，还得继续往上检查调整🧐。
  • 平衡因子为正负2：糟糕，这说明“家长”的平衡因子违反规定啦，得赶紧用旋转操作来把书架扶正😰。

AVL树的旋转🔄

当AVL树因为插入新书变得不平衡时，根据新书插的位置不同，有四种旋转“魔法”来恢复平衡：

4.1 左左（LL）：右单旋

要是新书插在较高左子树的左侧，就来个右单旋。想象一下，失衡的节点（叫它(pParent)）像个小塔，它的左子节点（(pSubL)）来帮忙把塔扶正。具体做法就是：

  • 把(pSubL)的右子节点（(pSubLR)）放到(pParent)的左边当左子节点。
  • 如果(pSubLR)存在，记得告诉它新“家长”是(pParent)。
  • 再把(pParent)放到(pSubL)的右边当右子节点。
  • 接着更新(pParent)和(pSubL)的“家长”指针，要是原来的塔尖（根节点）变了，也要更新根节点指针。
  • 最后，把(pParent)和(pSubL)的平衡因子都设为0，塔就稳稳当当啦🧱。
    在这里插入图片描述

4.2 右右（RR）：左单旋

和左左情况相反，新书插在较高右子树的右侧时，就来个左单旋，跟右单旋类似，只是方向反过来。
在这里插入图片描述

4.3 左右（LR）：先左单旋再右单旋

新书插在较高左子树的右侧时，先对失衡节点的左子节点来个左单旋，再对失衡节点来个右单旋。这个过程中，要小心保存和更新每个节点的平衡因子，保证书架重新平衡。
在这里插入图片描述

4.4 右左（RL）：先右单旋再左单旋

新书插在较高右子树的左侧时，先对失衡节点的右子节点来个右单旋，再对失衡节点来个左单旋。同样，别忘了平衡因子的更新。
在这里插入图片描述

AVL树的验证✅

要看看AVL树是不是真的“合格”，可以从两方面检查：

5.1 验证为二叉搜索树

像给书架上的书排序一样，对AVL树进行中序遍历。要是遍历出来的顺序是有序的，那就说明它是个合格的二叉搜索树📖。

5.2 验证为平衡树

一个个检查每个节点的平衡因子，看看它们左右子树高度差的绝对值是不是都没超过1。同时，还要检查平衡因子算得对不对🧮。
在这里插入图片描述

AVL树的删除🗑️

AVL树删除节点就像从书架上拿走一本书，和二叉搜索树的删除方法差不多。但拿走书后，书架可能又歪了，得重新调整平衡。有时候运气不好，可能得一直调整到最上面的根节点。具体怎么做，可以参考《算法导论》或者《数据结构 - 用面向对象方法与C++描述》殷人昆版📚。

AVL树的性能📈

AVL树在查找数据方面就像个超级跑车，时间复杂度是(O(log_2 n))，快得没话说。可要是经常对它进行插入和删除这些“大动作”，就像经常给跑车改装，为了保持平衡，得频繁调整，性能就会受影响，特别是删除的时候，可能要一直调整到根节点，很费时间。所以呢，要是数据基本不怎么变，查询又多，AVL树就是个好选择；要是数据经常变来变去，它可能就不太合适啦😕。

AVL树实现代码示例📄

#pragma once
#include <iostream>
#include <utility>
#include <cassert>template<class K, class V>
class AVLTreeNode
{
public:AVLTreeNode(const std::pair<K, V>& kv) : _kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr), _bf(0) {}AVLTreeNode<K, V>* _left;AVLTreeNode<K, V>* _right;AVLTreeNode<K, V>* _parent;int _bf; // 平衡因子std::pair<K, V> _kv;
};template<class K, class V>
class AVLTree
{
public:typedef AVLTreeNode<K, V> Node;~AVLTree(){destroy(_root);}void destroy(Node* node){if (node){destroy(node->_left);destroy(node->_right);delete node;}}bool insert(const std::pair<K, V>& key){try{if (_root == nullptr){_root = new Node(key);return true;}Node* cur = _root;Node* parent = nullptr;while (cur){parent = cur;if ((cur->_kv).first < key.first){cur = cur->_right;}else if ((cur->_kv).first > key.first){cur = cur->_left;}else{return false;}}cur = new Node(key);cur->_parent = parent;if ((parent->_kv).first < (cur->_kv).first){parent->_right = cur;}else{parent->_left = cur;}// 考虑平衡因子while (cur){if (parent == nullptr){break; // 如果 parent 为 nullptr，说明已经到根节点，跳出循环}if (cur == parent->_right){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){// 旋转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;}catch (const std::bad_alloc&){return false;}}void RotateL(Node* parent) // 左单旋{Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL){subRL->_parent = parent;}subR->_left = parent;Node* parentParent = parent->_parent;parent->_parent = subR;if (parentParent == nullptr){_root = subR;subR->_parent = nullptr;}else{if (parentParent->_left == parent){parentParent->_left = subR;}else{parentParent->_right = subR;}subR->_parent = parentParent;}// 修改_bfparent->_bf = subR->_bf = 0;}void RotateR(Node* parent) // 右单旋{Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subL->_right;if (subLR){subLR->_parent = parent;}subL->_right = parent;Node* parentParent = parent->_parent;parent->_parent = subL;if (parentParent == nullptr){_root = subL;subL->_parent = nullptr;}else{if (parentParent->_left == parent){parentParent->_left = subL;}else{parentParent->_right = subL;}subL->_parent = parentParent;}// 修改_bfparent->_bf = subL->_bf = 0;}void RotateRL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;int bf = subRL->_bf;RotateR(parent->_right);RotateL(parent);if (bf == 0){// 新增的就是subRLparent->_bf = subR->_bf = subRL->_bf = 0;}else if (bf == 1){// subRL的右结点就是新增的parent->_bf = -1;subR->_bf = 0;subRL->_bf = 0;}else if (bf == -1){parent->_bf = 0;subR->_bf = 1;subRL->_bf = 0;}else{assert(false);}}void RotateLR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;int bf = subLR->_bf;RotateL(parent->_left);RotateR(parent);if (bf == 1){subL->_bf = -1;parent->_bf = 0;subLR->_bf = 0;}else if (bf == -1){subL->_bf = 0;parent->_bf = 1;subLR->_bf = 0;}else{subL->_bf = 0;parent->_bf = 0;subLR->_bf = 0;}}// 中序打印方法void inorderPrint() const{inorderPrintHelper(_root);std::cout << std::endl;}// 判断是否为平衡二叉树bool isBalanced() const{int height = 0;return isBalancedHelper(_root, height);}private:Node* _root = nullptr;// 中序遍历辅助函数void inorderPrintHelper(Node* node) const{if (node){inorderPrintHelper(node->_left);std::cout << "Key: " << node->_kv.first << ", Value: " << node->_kv.second << std::endl;inorderPrintHelper(node->_right);}}// 判断是否为平衡二叉树的辅助函数bool isBalancedHelper(Node* node, int& height) const{if (node == nullptr){height = 0;return true;}int leftHeight = 0;int rightHeight = 0;// 递归判断左子树是否平衡if (!isBalancedHelper(node->_left, leftHeight)){return false;}// 递归判断右子树是否平衡if (!isBalancedHelper(node->_right, rightHeight)){return false;}// 计算当前节点的高度height = std::max(leftHeight, rightHeight) + 1;// 检查当前节点的左右子树高度差是否不超过 1if (std::abs(leftHeight - rightHeight) > 1){return false;}return true;}
};

总结🎉

AVL树就像一个聪明又有点小脾气的数据结构小伙伴😜。它用巧妙的平衡方法，解决了二叉搜索树可能失衡的问题，让查找数据又快又稳。它的插入、旋转和验证等操作一环扣一环，保证了自己时刻保持高效。虽然在结构经常变化的时候有点“小傲娇”，性能不太好，但在适合的场景下，绝对是个得力助手💪。通过深入了解AVL树，希望大家在编程时能更明智地选择数据结构，让程序跑得又快又好🚀。
在这里插入图片描述

投票环节🎊

你觉得AVL树在以下哪种场景最有用呢🧐？

  1. 数据基本不变，查询频繁：就像图书馆的藏书目录，很少新增或删除书籍，但经常有人查询。📚
  2. 数据频繁插入和删除：比如一个实时更新的新闻网站，不断有新新闻发布，旧新闻过期删除。📰
  3. 其他场景（请留言说明）：说不定你有独特的想法哦，快来分享！💡

快来投出你宝贵的一票吧👇，让我们看看大家对AVL树的看法！🎯

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/17368.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

Qt Designer菜鸟使用教程（实现一个本地英文翻译软件）

Qt Designer菜鸟使用教程（实现一个本地英文翻译软件）

1 安装Qt Designer 安装这个包的时候会自带安装 Qt Designer, 安装目录为python的安装根目录的 Lib/site-packages/qt5_applications/Qt/bin 目录下。 pip install pyqt5-tools2 新建窗体 2.1 新建主窗体 创建之后如下图&#xff1a; 设置主窗口大小&#xff1a; 设置窗…
阅读更多...
机械学习基础-5.分类-数据建模与机械智能课程自留

机械学习基础-5.分类-数据建模与机械智能课程自留

data modeling and machine intelligence - CLASSIFICATION 为什么我们不将回归技术用于分类&#xff1f;贝叶斯分类器&#xff08;The Bayes Classifier&#xff09;逻辑回归&#xff08;Logistic Regression&#xff09;对逻辑回归的更多直观理解逻辑 /sigmoid 函数的导数我们…
阅读更多...
C++ 网络编程

C++ 网络编程

1. socket Socket 是一种用于网络通信的编程接口&#xff0c;它提供了一种类似于文件描述符的接口&#xff0c;允许不同计算机之间的进程进行通信。Socket 可以工作在多种协议上&#xff0c;最常用的是 TCP/IP 和 UDP/IP 协议 1.1 UDP 1.1.1 概念 UDP&#xff08;用户数据报协…
阅读更多...
C/C++内存管理

C/C++内存管理

目录 前言 1、C/C内存划分 2、C语言中的动态内存管理方式 3、C内存管理方式 3.1操作内置类型 3.2操作自定义类型 3.3为什么对应的new和delete必须搭配使用&#xff08;了解&#xff09; 4、operator new与operator delete函数 5、new和delete的实现原理 5.1内置类型 5…
阅读更多...
微软开源GraphRAG的使用教程-使用自定义数据测试GraphRAG

微软开源GraphRAG的使用教程-使用自定义数据测试GraphRAG

微软在今年4月份的时候提出了GraphRAG的概念&#xff0c;然后在上周开源了GraphRAG,Github链接见https://github.com/microsoft/graphrag,截止当前&#xff0c;已有6900Star。 安装教程 官方推荐使用Python3.10-3.12版本&#xff0c;我使用Python3.10版本安装时&#xff0c;在…
阅读更多...
RK3568平台开发系列讲解（调试篇）网卡队列均衡负载

RK3568平台开发系列讲解（调试篇）网卡队列均衡负载

🚀返回专栏总目录 文章目录 一、RPS 的介绍1. RPS 的工作原理2. RPS 配置3. 启用和调优 RPS4. RPS 优势二、下行测试iperf测试沉淀、分享、成长，让自己和他人都能有所收获！😄 RPS（Receive Packet Steering） 是一种用于提高网络接收性能的技术，通常用于多核处理器系统中…
阅读更多...
RagFlow + Docker Desktop + Ollama + DeepSeek-R1本地部署自己的本地AI大模型工具

RagFlow + Docker Desktop + Ollama + DeepSeek-R1本地部署自己的本地AI大模型工具

前期准备 首先&#xff0c;我们需要下载 Ollama 以及配置相关环境。 Ollama 的 GitHub仓库 &#xff08;https://github.com/ollama/ollama&#xff09;中提供了详细的说明&#xff0c;简单总结如下: Step1&#xff1a;下载 Ollama 下载&#xff08;https://ollama.com/dow…
阅读更多...
变分边界详解

变分边界详解

起因 当时看VAE论文时有这么一段&#xff0c;但是看完直接一头雾水&#xff0c;这都那跟哪&#xff0c;第一个公式咋做的变换就变出那么一堆。网上搜了很多博客都语焉不详&#xff0c;只好自己来写一篇&#xff0c;希望能解答后来人的疑惑。 公式1 参考文章&#xff1a;证据…
阅读更多...
云消息队列 ApsaraMQ Serverless 演进：高弹性低成本、更稳定更安全、智能化免运维

云消息队列 ApsaraMQ Serverless 演进：高弹性低成本、更稳定更安全、智能化免运维

如今&#xff0c;消息队列已成为分布式架构中不可或缺的关键服务&#xff0c;为电商、物联网、游戏和教育等行业&#xff0c;提供了异步解耦、集成、高性能和高可靠的核心价值。 过去一年&#xff0c;我们发布了云消息队列 ApsaraMQ 全系列产品 Serverless 化&#xff0c;面向…
阅读更多...
【蓝桥杯嵌入式】8_IIC通信-eeprom读写

【蓝桥杯嵌入式】8_IIC通信-eeprom读写

全部代码网盘自取 链接&#xff1a;https://pan.baidu.com/s/1PX2NCQxnADxYBQx5CsOgPA?pwd3ii2 提取码&#xff1a;3ii2 1、电路图 这个电路允许通过I2C总线与EEPROM(M24C02-WMN6TP)和数字电位器(MCP4017T-104ELT)进行通信。EEPROM用于存储数据&#xff0c;而数字电位器可以用…
阅读更多...
DeepSeek处理自有业务的案例：让AI给你写一份小众编辑器(EverEdit)的语法着色文件

DeepSeek处理自有业务的案例：让AI给你写一份小众编辑器(EverEdit)的语法着色文件

1 DeepSeek处理自有业务的案例&#xff1a;让AI给你写一份小众编辑器(EverEdit)的语法着色文件 1.1 背景 AI能力再强&#xff0c;如果不能在企业的自有业务上产生助益&#xff0c;那基本也是一无是处。将企业的自有业务上传到线上训练&#xff0c;那是脑子进水的做法&#xff…
阅读更多...
Java常用设计模式面试题总结(内容详细，简单易懂)

Java常用设计模式面试题总结(内容详细，简单易懂)

设计模式的分类 创建型模式&#xff1a;通过隐藏对象创建的细节&#xff0c;避免直接使用 new 关键字实例化对象&#xff0c;从而使程序在判断和创建对象时更具灵活性。常见的模式包括&#xff1a; 工厂模式抽象工厂模式单例模式建造者模式原型模式 结构型模式&#xff1a;通…
阅读更多...
使用HX搭建UNI-APP云开发项目（适合新手小白与想学云开发的宝子）

使用HX搭建UNI-APP云开发项目（适合新手小白与想学云开发的宝子）

什么是uni-app云开发 uni-app云开发是uni-app提供的一套后端服务，它可以帮助开发者快速搭建起一个完整的后端服务，包括数据库、云函数、存储等。开发者只需要关注前端页面的开发，后端服务由uni-app云开发提供。 uni-app云开发的优势： 快速搭建后端服务：uni-app云开发提供了…
阅读更多...
零基础学CocosCreator·第九季-网络游戏同步策略与ESC架构

零基础学CocosCreator·第九季-网络游戏同步策略与ESC架构

课程里的版本好像是1.9&#xff0c;目前使用版本为3.8.3 开始~ 目录 状态同步帧同步帧同步客户端帧同步服务端ECS框架概念ECS的解释ECS的特点EntityComponentSystemWorld ECS实现逻辑帧&渲染帧 ECS框架使用帧同步&ECS 状态同步 一般游戏的同步策略有两种&#xff1a;…
阅读更多...
最新版Edge浏览器集成ActiveX控件之金山WpsDocFrame控件

最新版Edge浏览器集成ActiveX控件之金山WpsDocFrame控件

背景 WpsDocFrame控件‌是由金山公司开发的ActiveX控件&#xff0c;主要用于OA系统中&#xff0c;支持在浏览器中嵌入WPS文档的查看和编辑功能。 allWebPlugin中间件是一款为用户提供安全、可靠、便捷的浏览器插件服务的中间件产品&#xff0c;致力于将浏览器插件重新应用到所有…
阅读更多...
Win10系统IP地址修改_出现了一个意外的情况不能完成所有你在设置中所要求的更改---Windows工作笔记001

Win10系统IP地址修改_出现了一个意外的情况不能完成所有你在设置中所要求的更改---Windows工作笔记001

今天在修改win10系统中的ip地址的时候报错了 来看看如何解决吧,挺简单,简单记录一下 这个时候就需要使用cmd命令来修改 一定要使用,管理员权限,运行cmd才可以 然后首先: 输入 netsh 然后输入 ip 然后输入: set address "以太网" 172.19.126.199 255.255.255.0…
阅读更多...
算法 ST表

算法 ST表

目录 前言 一&#xff0c;暴力法 二&#xff0c;打表法 三&#xff0c;ST表 四&#xff0c;ST表的代码实现 总结 前言 ST表的主要作用是在一个区间里面寻找最大值&#xff0c;具有快速查找的功能&#xff0c;此表有些难&#xff0c;读者可以借助我的文章和网上的课程结…
阅读更多...
node.js+兰空图床实现随机图

node.js+兰空图床实现随机图

之前博客一直用的公共的随机图API&#xff0c;虽然图片的质量都挺不错的&#xff0c;但是稳定性都比较一般&#xff0c;遂打算使用之前部署的兰空图床&#xff0c;自己弄一个随机图 本文章服务器操作基于雨云——新一代云服务提供商的云服务器进行操作&#xff0c;有兴趣的话可…
阅读更多...
CNN|ResNet-50

CNN|ResNet-50

导入数据 import matplotlib.pyplot as plt # 支持中文 plt.rcParams[font.sans-serif] [SimHei] # 用来正常显示中文标签 plt.rcParams[axes.unicode_minus] False # 用来正常显示负号import os,PIL,pathlib import numpy as npfrom tensorflow import keras from tensor…
阅读更多...
基于微型5G网关的石化厂区巡检机器人应用

基于微型5G网关的石化厂区巡检机器人应用

石化工业属于高风险产业&#xff0c;由于涉及易燃易爆、有毒有害工业原料&#xff0c;为了保障企业的安全生产与持续运营&#xff0c;因此相比其它行业需要进行更高频次、更全面细致的安全巡检和监测。由于传统的人工巡检监测存在诸多不便&#xff0c;例如工作强度大、现场环境…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023