吃透 AVL 树！从概念到手撕实现，一篇搞定二叉平衡搜索树核心----《Hello C++ Wrold!》(21)--(C/C++)
文章目录
前言
你是否曾在写算法时，用二叉搜索树（BST）存数据却遭遇 “超时” 暴击？明明理论复杂度是 O (logn)，偏偏插入一串有序数据后，树直接退化成链表，查询效率暴跌到 O (n)？这背后的 “元凶”，正是 BST 无法自我平衡的结构性缺陷 —— 而 AVL 树，就是为破解这个痛点而生的 “平衡大师”。
但 AVL 树的价值，从不止于 “让树变矮” 这么简单。它是首个严格平衡的二叉搜索树，每一个设计细节都藏着精妙的逻辑：为什么平衡因子要选 “高度差≤1” 而非 “高度相等”？旋转操作看似复杂，实则是 “局部修复全局平衡” 的贪心策略；甚至它在工程中不如红黑树常用，也不是因为 “不够好”，而是 “严格平衡” 与 “写入效率” 的取舍艺术。
这篇前言之后，我们不会只停留在 “背旋转步骤”“记平衡因子更新规则” 的表层，而是要挖透 AVL 树的底层逻辑：从它诞生的根源，到旋转与平衡因子的本质，再到它在工程场景中的取舍，最终让你明白 ——AVL 树不仅是一种数据结构，更是一套 “用最小代价解决失衡问题” 的方法论。
AVL树的概念
AVL树是二叉平衡搜索树中的一种,还有比如像红黑树也算二叉平衡搜索树的一种
跟二叉搜索树的区别:二叉搜索树极端场景下会退化成类似链表的结构,AVL树则不会
概念:
一棵AVL树或者是空树，或者是具有以下性质的二叉搜索树：
1.它的左右子树都是AVL树
2.左右子树高度之差(简称平衡因子)的绝对值不超过1(-1/0/1)
–每个节点都有它的平衡因子哈
AVL树增删查改的时间复杂度都是O(logn)–n是元素个数
AVL树的模拟实现
AVL树和红黑树考手撕考的不多–但是会让你说整体模拟实现的思想或者考eg:旋转的手撕
template<classK,classV>structAVLTreeNode{ 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<classK,classV>classAVLTree{typedef AVLTreeNode<K, V> Node;public:boolInsert(const pair<K, V>& kv){if(_root ==nullptr){ _root =newNode(kv);returntrue;} Node* parent =nullptr; Node* cur = _root;while(cur){if(cur->_kv.first < kv.first){ parent = cur; cur = cur->_right;}elseif(cur->_kv.first > kv.first){ parent = cur; cur = cur->_left;}else{returnfalse;}} cur =newNode(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;}elseif(parent->_bf ==1|| parent->_bf ==-1){// 继续往上更新 cur = parent; parent = parent->_parent;}elseif(parent->_bf ==2|| parent->_bf ==-2){// 子树不平衡了，需要旋转if(parent->_bf ==2|| cur->bf ==1){RotateL(parent);}elseif(parent->_bf ==-2&& cur->_bf ==-1){RotateR(parent);}elseif(parent->_bf ==2&& cur->_bf ==-1){RotateRL(parent);}elseif(parent->_bf ==-2&& cur->_bf ==1){RotateLR(parent);}break;}else{assert(false);//这个的话是防止自己写代码时写出BUG了--也是一个小技巧的学习}}returntrue;}//左旋voidRotateL(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;//这个容易考虑不到//这下面是cur代替parent的步骤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;//注意理解为什么都改成0}//右旋voidRotateR(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;}//双旋中的先右旋再左旋voidRotateRL(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;}elseif(bf ==1){ cur->_bf =0; curleft->_bf =0; parent->_bf =-1;}elseif(bf ==-1){ cur->_bf =1; curleft->_bf =0; parent->_bf =0;}else{assert(false);}}//双旋中的先左旋再右旋voidRotateLR(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;}//这里其实没啥用，就是用来防止RotateL和RotateR有毛病--当RotateL啥的是别人写的时候...elseif(bf ==-1){ parent->_bf =1; cur->_bf =0; curright->_bf =0;}elseif(bf ==1){ parent->_bf =0; cur->_bf =-1; curright->_bf =0;}}private: Node* _root =nullptr;};这里AVL旋转的时间复杂度是O(logN)模拟实现的时候一定要画图!不然是不好理解的–尤其是像AVL这些复杂的东西
AVL树的模拟实现不一定要用到平衡因子，也可以用高度去搞
关于这里平衡因子的更新
1.新增的在左，parent平衡因子减减
2.新增的在右，parent平衡因子加加
3.更新后parent平衡因子等于0，祖先的平衡因子不用动了–更新结束
4.更新后parent平衡因子等于1或-1，祖先平衡因子要动–依旧用前两点
5.更新后parent平衡因子等于2或-2，要对parent所在子树进行旋转–之后就更新结束了
6.更新到根节点了–更新结束
关于旋转
旋转时要确保1.一直是搜索树
AVL树的旋转分为四种:
(这个x,y,z这个没啥用) abcd各个位置是啥肯定是已知的
新节点插入较高左子树的左侧—左左：右旋
a是z b.c是x,y,z中的任意一种右旋步骤:60是parent30是cur
把cur的右节点接到parent的左边，然后把parent接到cur的右边
新节点插入较高右子树的右侧—左旋
c是z a.b是x,y,z中的任意一种左旋步骤:30是parent60是cur
把cur的左节点接到parent的右边，然后把parent接到cur的左边
新节点插入较高左子树的右侧—先左旋再右旋
插入c的话也是可以的
a和d是x,y,z中的任意一种 b,c被插入的那个树是x,y中的一种
还有种情况就是60是新增的节点步骤:30是cur90是parent60是cur->right是左旋中的
curparentcur->right是左旋里面的cur是右旋中的
parentparentcur->left是右旋里面的cur
新节点插入较高右子树的左侧—先右旋再左旋
–较高右子树指的是右子树当前比左子树高
插入b的话也是可以的
a和d是x,y,z中的任意一种 b,c被插入的那个树是x,y中的一种
还有种情况就是60是新增的节点步骤:90是cur30是parent60是cur->left是右旋中的
curparentcur->left是右旋里面的cur是左旋中的
parentparentcur->left是左旋里面的cur
用是直线还是折线及其方向判断需要哪种旋转:
1.沿着cur点向右偏的直线–右旋
2.沿着cur点向左偏的直线–左旋
3.cur在最左边的折线–先左旋再右旋
4.cur在最右边的折线–先右旋再左旋
关于双旋平衡因子的更改方法
单旋的那两种的话是直接把平衡因子改为0就行了
但是双旋不一样:
要分三种情况:1.新插入节点正好是上图的60
AVL树的删除
这个的步骤:
1.按搜索树的规则查找节点删除
2.更新平衡因子
3.出现异常，然后旋转
要注意的是，这里的规则跟插入的时候可不一样，删除这里的话要节点的平衡因子更新为+-1就停止，为0的话向上走
异常之后旋转的话还是平衡因子为+-2时搞
AVL树的验证
intHeight(Node* root){if(root ==nullptr)return0;int leftHeight =Height(root->_left);int rightHeight =Height(root->_right);return leftHeight > rightHeight ? leftHeight +1: rightHeight +1;}boolIsBalance(Node* root){if(root ==nullptr)returntrue;int leftHight =Height(root->_left);int rightHight =Height(root->_right);if(rightHight - leftHight != root->_bf){ cout <<"平衡因子异常:"<<root->_kv.first<<"->"<< root->_bf << endl;returnfalse;}//这个就是检查平衡因子有没有问题returnabs(rightHight - leftHight)<2&&IsBalance(root->_left)&&IsBalance(root->_right);}也就是使用看左右子树高度差是不是对的
1.不能用平衡因子去检查AVL树写的对不对–因为可能更新平衡因子就是出了问题的
2.也不能用中序遍历出来是有序来说明它是AVL树，只能说明他是二叉搜索树
作业部分
现有一棵无重复关键字的平衡二叉树（AVL树），对其进行中序遍历可得到一个降序序列。下列关于该平衡二叉树的叙述中，正确的是(D)
A.根结点的度一定为2
B.树中最小元素一定是叶结点
C.最后插入的元素一定是叶结点//可能会旋转，所以错
D.树中最大元素一定是无左子树
