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菜鸟使用教程(实现一个本地英文翻译软件)

1 安装Qt Designer 安装这个包的时候会自带安装 Qt Designer, 安装目录为python的安装根目录的 Lib/site-packages/qt5_applications/Qt/bin 目录下。 pip install pyqt5-tools2 新建窗体 2.1 新建主窗体 创建之后如下图&#xff1a; 设置主窗口大小&#xff1a; 设置窗…

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

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

C++ 网络编程

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

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

微软在今年4月份的时候提出了GraphRAG的概念&#xff0c;然后在上周开源了GraphRAG,Github链接见https://github.com/microsoft/graphrag,截止当前&#xff0c;已有6900Star。 安装教程 官方推荐使用Python3.10-3.12版本&#xff0c;我使用Python3.10版本安装时&#xff0c;在…

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

🚀返回专栏总目录 文章目录 一、RPS 的介绍1. RPS 的工作原理2. RPS 配置3. 启用和调优 RPS4. RPS 优势二、下行测试iperf测试沉淀、分享、成长,让自己和他人都能有所收获!😄 RPS(Receive Packet Steering) 是一种用于提高网络接收性能的技术,通常用于多核处理器系统中…

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 演进:高弹性低成本、更稳定更安全、智能化免运维

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

【蓝桥杯嵌入式】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)的语法着色文件

1 DeepSeek处理自有业务的案例&#xff1a;让AI给你写一份小众编辑器(EverEdit)的语法着色文件 1.1 背景 AI能力再强&#xff0c;如果不能在企业的自有业务上产生助益&#xff0c;那基本也是一无是处。将企业的自有业务上传到线上训练&#xff0c;那是脑子进水的做法&#xff…

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

设计模式的分类 创建型模式&#xff1a;通过隐藏对象创建的细节&#xff0c;避免直接使用 new 关键字实例化对象&#xff0c;从而使程序在判断和创建对象时更具灵活性。常见的模式包括&#xff1a; 工厂模式抽象工厂模式单例模式建造者模式原型模式 结构型模式&#xff1a;通…

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

什么是uni-app云开发 uni-app云开发是uni-app提供的一套后端服务,它可以帮助开发者快速搭建起一个完整的后端服务,包括数据库、云函数、存储等。开发者只需要关注前端页面的开发,后端服务由uni-app云开发提供。 uni-app云开发的优势: 快速搭建后端服务:uni-app云开发提供了…

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

课程里的版本好像是1.9&#xff0c;目前使用版本为3.8.3 开始~ 目录 状态同步帧同步帧同步客户端帧同步服务端ECS框架概念ECS的解释ECS的特点EntityComponentSystemWorld ECS实现逻辑帧&渲染帧 ECS框架使用帧同步&ECS 状态同步 一般游戏的同步策略有两种&#xff1a;…

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

背景 WpsDocFrame控件‌是由金山公司开发的ActiveX控件&#xff0c;主要用于OA系统中&#xff0c;支持在浏览器中嵌入WPS文档的查看和编辑功能。 allWebPlugin中间件是一款为用户提供安全、可靠、便捷的浏览器插件服务的中间件产品&#xff0c;致力于将浏览器插件重新应用到所有…

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

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

算法 ST表

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

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

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

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网关的石化厂区巡检机器人应用

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