news 2026/5/30 14:58:04

AVL树（C++详解版）

作者头像

张小明

前端开发工程师

1.2k 24
文章封面图
AVL树（C++详解版）

1. AVL的概念

  • AVL是一颗空树，或者具备下列性质的二叉搜索树：它的左右子树都是AVL树，且左右子树的高度差的绝对值不超过1。AVL树是一颗高度平衡搜索二叉树，通过控制高度差去控制平衡。
  • AVL树实现这里我们引入一个平衡因子的概念，每个结点都有⼀个平衡因子，任何结点的平衡因子等于右子树的高度减去左子树的高度，也就是说任何结点的平衡因子等于0/1/-1，AVL树并不是必须要平衡因子，但是有了平衡因子可以更方便我们去进性观察和控制树是否平衡。
  • AVL树整体结点数量和分布和完全二叉树类似，高度可以控制在log⁡n\log nlogn，那么增删查改的效率也可以控制在Olog⁡(n)\log (n)log(n)，相比与二叉搜索树有了本质的提升。

2.AVL的实现

2.1 AVL树的结构

template<classK,classV>structAVLNode{pair<K,V>_kv;AVLNode<K,V>*_parent;AVLNode<K,V>*_left;AVLNode<K,V>*_right;int_bf;AVLNode(constpair<K,V>&kv):_kv(kv),_parent(nullptr),_left(nullptr),_right(nullptr),_bf(0){}};template<classK,classV>classAVLTree{usingNode=AVLNode<K,V>;public:private:Node*_root=nullptr;};

2.2 AVL树的插入

    1. 插⼊⼀个值按⼆叉搜索树规则进行。
    1. 新增结点以后，只会影响祖先结点的高度，也就是可能会影响部分祖先结点的平衡因子，所以更新从新增结点->根结点路径上的平衡因子，实际中最坏情况下要更新到根，有些情况更新到中间就可以停止了，具体情况我们下面再详细分析。
    1. 更新平衡因子过程中没有出现问题，则插入结束
    1. 更新平衡因子过程中出现不平衡，对不平衡子树旋转，旋转后本质调平衡的同时，本质降低了子树的高度，不会再影响上一层，所以插入结束。

平衡因子更新
更新原则：

  • 平衡因子 = 右子树高度-左子树高度
  • 只有子树高度变化才会影响当前结点平衡因子。
  • 插入结点，会增加高度，所以新增结点在parent的右子树，parent的平衡因子++，新增结点在parent的左子树，parent平衡因子–
  • parent所在⼦树的⾼度是否变化决定了是否会继续往上更新

更新停止条件：

  • 更新后parent的平衡因子等于0，更新中parent的平衡因子变化为-1->0 或者 1->0，说明更新前parent子树⼀边高⼀边低，新增的结点插⼊在低的那边，插入后parent所在子树高度不变，不会影响parent的父亲结点的平衡因子，更新结束。
  • 更新后parent的平衡因子等于1 或 -1，更新前更新中parent的平衡因子变化为0->1 或者 0->-1，说明更新前parent子树两边⼀样高，新增的插入结点后，parent所在的子树⼀边高⼀边低，parent所在的子树符合平衡要求，但是高度增加了1，会影响parent的父亲结点的平衡因子，所以要继续向上更新。
  • 更新后parent的平衡因子等于2 或 -2，更新前更新中parent的平衡因子变化为1->2 或者 -1->-2，说明更新前parent子树⼀边高⼀边低，新增的插入结点在高的那边，parent所在的子树高的那边更高了，破坏了平衡，parent所在的子树不符合平衡要求，需要旋转处理，旋转的目标有两个：
    1、把parent子树旋转平衡。
    2、降低parent子树的高度，恢复到插⼊结点以前的⾼度。所以旋转后也不需要继续往上更新，插入结束。
  • 不断更新，更新到根，根的平衡因子是1或-1也停止了。

    插入代码实现：
boolInsert(constpair<K,V>&kv){if(_root==nullptr){_root=newNode(kv);returntrue;}Node*cur=_root;Node*parent=nullptr;while(cur){if(cur->_kv.first>kv.first){parent=cur;cur=cur->_left;}elseif(cur->_kv.first<kv.first){parent=cur;cur=cur->_right;}else{returnfalse;}}cur=newNode(kv);if(parent->_kv.first>kv.first){parent->_left=cur;}else{parent->_right=cur;}cur->_parent=parent;while(parent){if(cur==parent->_left)parent->_bf--;elseparent->_bf++;if(parent->_bf==0){break;}elseif(parent->_bf==-1||parent->_bf==1){cur=parent;parent=cur->_parent;}elseif(parent->_bf==2||parent->_bf==-2){//旋转}else{assert(false);}}}

3.AVL树的旋转

旋转的原则

    1. 保持搜索树的规则
    1. 让旋转的树从不满足变平衡，其次降低旋转树的高度旋转总共分为四种，左单旋/右单旋/左右双旋/右左双旋。

1.右单旋

当左子树纯粹地比右边高时，且高度差为2时，就要开始右单旋，右单旋有一个好记的规则，就是将旋转点的左子树的右子树放到右子树的左子树，可以参考下面的例子。
而且有时候要旋转两次，一次时不够的，图三就是旋转了2次。



代码实现：

voidRotateR(Node*parent){Node*subL=parent->_left;Node*subLR=subL->_right;parent->_left=subLR;if(subLR){subLR->_parent=parent;}Node*Pparent=parent->_parent;parent->_parent=subL;subL->_right=parent;if(Pparent==nullptr){_root=subL;_root->_parent=nullptr;}else{if(Pparent->_left==parent){Pparent->_left=subL;}else{Pparent->_right=subL;}subL->_parent=Pparent;}parent->_bf=0;subL->_bf=0;}

2.左单旋

左单旋和右单旋同理，都是规则是一样的，唯一不同的就是，左单旋是将根的右子树的左子树放到根的左子树的右子树
代码实现：

voidRotateL(Node*parent){Node*subR=parent->_right;Node*subRL=subR->_left;parent->_right=subRL;if(subRL){subRL->_parent=parent;}parent->_parent=subR;subR->_left=parent;Node*Pparent=parent->_parent;if(Pparent==nullptr){_root=subR;_root->_parent=nullptr;}else{if(parent==Pparent->_left){Pparent->_left=subR;}else{Pparent->_right=subR;}subR->_parent=Pparent;}parent->_bf=0;subR->_bf=0;}

3.右左双旋

产生双旋的条件是比较好辩别的，就是当一棵树不是纯粹的一边高时，就会发生双旋，比如图一，根的右子树比左子树高，本来理应左旋，但是左子树的右子树比左子树矮，左旋的代价是把旋上去的那个节点的左子树放到原本的根的右子树上，这样就会陷入循环，导致问题无法解决，所以我们要把右子树变成纯粹的一边高
情景有以下几种：



代码演示：

voidRotateRL(Node*parent){Node*subR=parent->_right;Node*subRL=subR->_left;intbf=subRL->_bf;RotateR(subR);RotateL(parent);if(bf==0){parent->_bf=0;subR->_bf=0;subRL->_bf=0;}elseif(bf==-1){parent->_bf=0;subR->_bf=1;subRL->_bf=0;}elseif(bf==1){parent->_bf=-1;subR->_bf=0;subRL->_bf=0;}else{assert(false);}}

4.左右双旋

原理和右左双旋一样



代码演示：

voidRotateRL(Node*parent){Node*subR=parent->_right;Node*subRL=subR->_left;intbf=subRL->_bf;RotateR(subR);RotateL(parent);if(bf==0){parent->_bf=0;subR->_bf=0;subRL->_bf=0;}elseif(bf==-1){parent->_bf=0;subR->_bf=1;subRL->_bf=0;}elseif(bf==1){parent->_bf=-1;subR->_bf=0;subRL->_bf=0;}else{assert(false);}}

4.AVL树的平衡检测

AVL树的平衡检测需要检查检查平衡因子是否正确，这时候我们需要一个参照物，就要借助树的高度来检查平衡因子是否没有出错。
而树的高度我们需要用到递归的方式来得到：
代码演示：

intHeight(Node*root){if(root==nullptr){return0;}intHeightLeft=Height(root->_left);intHeightRight=Height(root->_right);returnHeightLeft>HeightRight?HeightLeft+1:HeightRight+1;}boolIsBalanceTree(Node*root){if(root==nullptr){returntrue;}intHeightleft=Height(root->_left);intHeightright=Height(root->_right);intbf=Heightleft-Heightright;if(bf==-2||bf==2){returnfalse;}if(bf!=root->_bf){returnfalse;}returnIsBalanceTree(root->_left)&&IsBalanceTree(root->_right);}
版权声明: 本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系邮箱：809451989@qq.com进行投诉反馈，一经查实，立即删除！
网站建设 2026/5/30 14:57:07

人工智能【第35篇】PPO算法详解：近端策略优化实战

作者的话&#xff1a;在上一篇中&#xff0c;我们学习了Actor-Critic架构&#xff0c;但传统的策略梯度方法存在训练不稳定的问题——策略更新幅度过大可能导致性能崩溃。PPO&#xff08;Proximal Policy Optimization&#xff09;通过巧妙地限制策略更新的幅度&#xff0c;在保…

作者头像 李华
网站建设 2026/5/30 14:52:19

Vite 插件开发与 TypeScript 类型提示实践指南

Vite 插件开发与 TypeScript 类型提示实践指南 引言 在前端开发领域&#xff0c;构建工具的演进不断推动着开发效率的提升。Vite 作为新一代前端构建工具&#xff0c;凭借其基于原生 ESM 的开发服务器和快速的打包能力&#xff0c;逐渐成为许多开发者的首选。当开发者基于 Vite…

作者头像 李华
网站建设 2026/5/30 14:48:50

基于Arduino与PIR传感器的互动游戏装置设计与实现

1. 项目概述&#xff1a;一个会“抓人”的互动龙如果你对Arduino、传感器和手工制作都感兴趣&#xff0c;那么把这三者结合起来&#xff0c;做一个能和你玩“红灯停&#xff0c;绿灯行”游戏的自动机&#xff0c;绝对是个让人兴奋的挑战。这个项目源于一个课程作业&#xff0c;…

作者头像 李华
网站建设 2026/5/30 14:48:48

基于ESP32C3与A9G的便携式GPS追踪器全栈开发实战

1. 项目概述与核心价值在户外探险或者看护重要物品时&#xff0c;我们常常面临一个两难困境&#xff1a;智能手机功能强大&#xff0c;但其定位和通信能力严重依赖蜂窝网络信号和电池续航。一旦进入深山、荒漠或地下车库等信号盲区&#xff0c;或者手机电量耗尽&#xff0c;我们…

作者头像 李华
网站建设 2026/5/30 14:47:16

开源KMS模拟器：企业级Windows许可管理的自动化解决方案

开源KMS模拟器&#xff1a;企业级Windows许可管理的自动化解决方案 【免费下载链接】KMS_VL_ALL_AIO Smart Activation Script 项目地址: https://gitcode.com/gh_mirrors/km/KMS_VL_ALL_AIO 在Windows和Office的批量部署环境中&#xff0c;许可管理一直是IT管理员面临的…

作者头像 李华