彻底搞懂AVL树：从原理到旋转，再到C++完整实现（超详细）

彻底搞懂AVL树：从原理到旋转，再到C++完整实现（超详细）

本文干货密度拉满，适合数据结构学习、面试手撕、期末复习，看完就能彻底吃透AVL树。

一、什么是AVL树？

AVL树是最早发明的自平衡二叉搜索树，由两位科学家在1962年提出，它在二叉搜索树的基础上加入了严格平衡限制，避免树退化成链表。

核心性质

1. 左右子树都是AVL树
2. 左右子树高度差的绝对值 ≤ 1
3. 引入平衡因子（Balance Factor，简称BF）
   • BF = 右子树高度 − 左子树高度
   • 合法值：-1、0、1
4. 树高度严格控制在O(logN)，查找/插入效率稳定O(logN)

为什么不要求高度差一定为0？因为节点数量为2、4等情况时，根本无法做到高度完全一致，只能控制差值≤1。

二、AVL树节点结构设计

为了支持向上更新平衡因子，节点必须带parent指针。

template<classK,classV>structAVLTreeNode{// 存储键值对pair<K,V>_kv;// 三叉链结构AVLTreeNode<K,V>*_left;AVLTreeNode<K,V>*_right;AVLTreeNode<K,V>*_parent;// 平衡因子int_bf;AVLTreeNode(constpair<K,V>&kv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr),_bf(0){}};

template<classK,classV>classAVLTree{typedefAVLTreeNode<K,V>Node;private:Node*_root=nullptr;};

三、插入操作（最核心逻辑）

插入分为3 步：

1. 按二叉搜索树规则插入节点
2. 向上更新平衡因子
3. 出现失衡则旋转调整

1. 搜索插入

boolInsert(constpair<K,V>&kv){// 1. 空树直接创建根节点if(_root==nullptr){_root=newNode(kv);returntrue;}// 2. 按BST规则查找插入位置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;}}// 3. 链接新节点cur=newNode(kv);if(parent->_kv.first<kv.first)parent->_right=cur;elseparent->_left=cur;cur->_parent=parent;}

2. 向上更新平衡因子

这是AVL树最精髓的部分：

• 插入左子树 → parent->_bf–
• 插入右子树 → parent->_bf++

更新停止规则

• parent->_bf == 0：子树高度不变，停止更新
• parent->_bf == ±1：子树高度变了，继续向上更新
• parent->_bf == ±2：已失衡，需要旋转

// 继续Insert函数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=parent->_parent;}elseif(parent->_bf==2||parent->_bf==-2){// 失衡，旋转处理break;}else{// 非法情况，断言报错assert(false);}}returntrue;

四、旋转操作（4种全解）

旋转的两个目标：

1. 保持二叉搜索树有序
2. 恢复平衡，并让子树高度回到插入前

旋转判断口诀（背会就够用）

• -2、-1 → 右单旋（左左）
• +2、+1 → 左单旋（右右）
• -2、+1 → 左右双旋
• +2、-1 → 右左双旋

1. 右单旋（左左失衡）

场景：左边太高，新节点插入在左孩子的左子树

voidRotateR(Node*parent){Node*subL=parent->_left;Node*subLR=subL->_right;// 1. 旋转移动parent->_left=subLR;if(subLR)subLR->_parent=parent;Node*parentParent=parent->_parent;subL->_right=parent;parent->_parent=subL;// 2. 链接上层if(parentParent==nullptr){_root=subL;subL->_parent=nullptr;}else{if(parent==parentParent->_left)parentParent->_left=subL;elseparentParent->_right=subL;subL->_parent=parentParent;}// 3. 重置平衡因子parent->_bf=subL->_bf=0;}

2. 左单旋（右右失衡）

场景：右边太高，新节点插入在右孩子的右子树

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

3. 左右双旋（左右失衡）

场景：左子树高，但新节点插入在左孩子的右子树

1. 先对左孩子左旋
2. 再对parent右旋
3. 根据subLR的bf修正平衡因子

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

4. 右左双旋（右左失衡）

场景：右子树高，但新节点插入在右孩子的左子树

1. 先对右孩子右旋
2. 再对parent左旋
3. 根据subRL的bf修正平衡因子

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

五、旋转调用（插入中补全）

elseif(parent->_bf==2||parent->_bf==-2){// 失衡，判断旋转类型if(parent->_bf==-2&&parent->_left->_bf==-1){RotateR(parent);}elseif(parent->_bf==2&&parent->_right->_bf==1){RotateL(parent);}elseif(parent->_bf==-2&&parent->_left->_bf==1){RotateLR(parent);}elseif(parent->_bf==2&&parent->_right->_bf==-1){RotateRL(parent);}else{assert(false);}break;}

六、查找操作（和BST一样）

Node*Find(constK&key){Node*cur=_root;while(cur){if(cur->_kv.first<key){cur=cur->_right;}elseif(cur->_kv.first>key){cur=cur->_left;}else{returncur;}}returnnullptr;}

七、AVL树平衡验证（最稳的检查方式）

验证两点：

1. 每个节点左右高度差≤1
2. 存储的_bf必须等于真实计算的平衡因子

int_Height(Node*root){if(root==nullptr)return0;intleftH=_Height(root->_left);intrightH=_Height(root->_right);returnmax(leftH,rightH)+1;}bool_IsBalanceTree(Node*root){if(root==nullptr)returntrue;intleftH=_Height(root->_left);intrightH=_Height(root->_right);intdiff=rightH-leftH;// 高度差超过1if(abs(diff)>=2){cout<<"节点"<<root->_kv.first<<"高度失衡"<<endl;returnfalse;}// 平衡因子不一致if(root->_bf!=diff){cout<<"节点"<<root->_kv.first<<"平衡因子异常"<<endl;returnfalse;}return_IsBalanceTree(root->_left)&&_IsBalanceTree(root->_right);}// 对外接口boolIsBalanceTree(){return_IsBalanceTree(_root);}

八、AVL树总结（极简版）

1. AVL = 严格平衡BST，高度差 ≤1
2. BF = 右高 − 左高，必须是 -1/0/1
3. 插入后向上更新BF，出现±2则旋转
4. 4种旋转：左左→右旋、右右→左旋、左右→左右旋、右左→右左旋
5. 效率稳定O(logN)
6. 优点：查找极快；缺点：旋转频繁、实现略复杂

九、高频面试题

1. AVL树的平衡条件是什么？
2. 平衡因子的定义？
3. 插入后为什么要向上更新？
4. 4种旋转分别在什么场景使用？
5. 为什么AVL树必须带parent指针？
6. 如何验证一棵树是AVL树？