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

彻底搞懂AVL树从原理到旋转再到C完整实现超详细本文干货密度拉满适合数据结构学习、面试手撕、期末复习看完就能彻底吃透AVL树。文章目录彻底搞懂AVL树从原理到旋转再到C完整实现超详细一、什么是AVL树核心性质二、AVL树节点结构设计三、插入操作最核心逻辑1. 搜索插入2. 向上更新平衡因子更新停止规则四、旋转操作4种全解旋转判断口诀背会就够用1. 右单旋左左失衡2. 左单旋右右失衡3. 左右双旋左右失衡4. 右左双旋右左失衡五、旋转调用插入中补全六、查找操作和BST一样七、AVL树平衡验证最稳的检查方式八、AVL树总结极简版九、高频面试题一、什么是AVL树AVL树是最早发明的自平衡二叉搜索树由两位科学家在1962年提出它在二叉搜索树的基础上加入了严格平衡限制避免树退化成链表。核心性质左右子树都是AVL树左右子树高度差的绝对值 ≤ 1引入平衡因子Balance Factor简称BFBF 右子树高度 − 左子树高度合法值-1、0、1树高度严格控制在O(logN)查找/插入效率稳定O(logN)为什么不要求高度差一定为0因为节点数量为2、4等情况时根本无法做到高度完全一致只能控制差值≤1。二、AVL树节点结构设计为了支持向上更新平衡因子节点必须带parent指针。templateclassK,classVstructAVLTreeNode{// 存储键值对pairK,V_kv;// 三叉链结构AVLTreeNodeK,V*_left;AVLTreeNodeK,V*_right;AVLTreeNodeK,V*_parent;// 平衡因子int_bf;AVLTreeNode(constpairK,Vkv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr),_bf(0){}};templateclassK,classVclassAVLTree{typedefAVLTreeNodeK,VNode;private:Node*_rootnullptr;};三、插入操作最核心逻辑插入分为3 步按二叉搜索树规则插入节点向上更新平衡因子出现失衡则旋转调整1. 搜索插入boolInsert(constpairK,Vkv){// 1. 空树直接创建根节点if(_rootnullptr){_rootnewNode(kv);returntrue;}// 2. 按BST规则查找插入位置Node*parentnullptr;Node*cur_root;while(cur){if(cur-_kv.firstkv.first){parentcur;curcur-_right;}elseif(cur-_kv.firstkv.first){parentcur;curcur-_left;}else{// 键值重复插入失败returnfalse;}}// 3. 链接新节点curnewNode(kv);if(parent-_kv.firstkv.first)parent-_rightcur;elseparent-_leftcur;cur-_parentparent;}2. 向上更新平衡因子这是AVL树最精髓的部分插入左子树 → parent-_bf–插入右子树 → parent-_bf更新停止规则parent-_bf 0子树高度不变停止更新parent-_bf ±1子树高度变了继续向上更新parent-_bf ±2已失衡需要旋转// 继续Insert函数while(parent){// 更新平衡因子if(curparent-_left)parent-_bf--;elseparent-_bf;// 判断是否继续更新if(parent-_bf0){// 高度不变更新结束break;}elseif(parent-_bf1||parent-_bf-1){// 高度变了继续往上更新curparent;parentparent-_parent;}elseif(parent-_bf2||parent-_bf-2){// 失衡旋转处理break;}else{// 非法情况断言报错assert(false);}}returntrue;四、旋转操作4种全解旋转的两个目标保持二叉搜索树有序恢复平衡并让子树高度回到插入前旋转判断口诀背会就够用-2、-1 → 右单旋左左2、1 → 左单旋右右-2、1 → 左右双旋2、-1 → 右左双旋1. 右单旋左左失衡场景左边太高新节点插入在左孩子的左子树voidRotateR(Node*parent){Node*subLparent-_left;Node*subLRsubL-_right;// 1. 旋转移动parent-_leftsubLR;if(subLR)subLR-_parentparent;Node*parentParentparent-_parent;subL-_rightparent;parent-_parentsubL;// 2. 链接上层if(parentParentnullptr){_rootsubL;subL-_parentnullptr;}else{if(parentparentParent-_left)parentParent-_leftsubL;elseparentParent-_rightsubL;subL-_parentparentParent;}// 3. 重置平衡因子parent-_bfsubL-_bf0;}2. 左单旋右右失衡场景右边太高新节点插入在右孩子的右子树voidRotateL(Node*parent){Node*subRparent-_right;Node*subRLsubR-_left;parent-_rightsubRL;if(subRL)subRL-_parentparent;Node*parentParentparent-_parent;subR-_leftparent;parent-_parentsubR;if(parentParentnullptr){_rootsubR;subR-_parentnullptr;}else{if(parentparentParent-_left)parentParent-_leftsubR;elseparentParent-_rightsubR;subR-_parentparentParent;}parent-_bfsubR-_bf0;}3. 左右双旋左右失衡场景左子树高但新节点插入在左孩子的右子树先对左孩子左旋再对parent右旋根据subLR的bf修正平衡因子voidRotateLR(Node*parent){Node*subLparent-_left;Node*subLRsubL-_right;intbfsubLR-_bf;RotateL(parent-_left);RotateR(parent);if(bf0){subL-_bf0;subLR-_bf0;parent-_bf0;}elseif(bf-1){subL-_bf0;subLR-_bf0;parent-_bf1;}elseif(bf1){subL-_bf-1;subLR-_bf0;parent-_bf0;}else{assert(false);}}4. 右左双旋右左失衡场景右子树高但新节点插入在右孩子的左子树先对右孩子右旋再对parent左旋根据subRL的bf修正平衡因子voidRotateRL(Node*parent){Node*subRparent-_right;Node*subRLsubR-_left;intbfsubRL-_bf;RotateR(parent-_right);RotateL(parent);if(bf0){subR-_bf0;subRL-_bf0;parent-_bf0;}elseif(bf1){subR-_bf0;subRL-_bf0;parent-_bf-1;}elseif(bf-1){subR-_bf1;subRL-_bf0;parent-_bf0;}else{assert(false);}}五、旋转调用插入中补全elseif(parent-_bf2||parent-_bf-2){// 失衡判断旋转类型if(parent-_bf-2parent-_left-_bf-1){RotateR(parent);}elseif(parent-_bf2parent-_right-_bf1){RotateL(parent);}elseif(parent-_bf-2parent-_left-_bf1){RotateLR(parent);}elseif(parent-_bf2parent-_right-_bf-1){RotateRL(parent);}else{assert(false);}break;}六、查找操作和BST一样Node*Find(constKkey){Node*cur_root;while(cur){if(cur-_kv.firstkey){curcur-_right;}elseif(cur-_kv.firstkey){curcur-_left;}else{returncur;}}returnnullptr;}七、AVL树平衡验证最稳的检查方式验证两点每个节点左右高度差≤1存储的_bf必须等于真实计算的平衡因子int_Height(Node*root){if(rootnullptr)return0;intleftH_Height(root-_left);intrightH_Height(root-_right);returnmax(leftH,rightH)1;}bool_IsBalanceTree(Node*root){if(rootnullptr)returntrue;intleftH_Height(root-_left);intrightH_Height(root-_right);intdiffrightH-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树总结极简版AVL 严格平衡BST高度差 ≤1BF 右高 − 左高必须是 -1/0/1插入后向上更新BF出现±2则旋转4种旋转左左→右旋、右右→左旋、左右→左右旋、右左→右左旋效率稳定O(logN)优点查找极快缺点旋转频繁、实现略复杂九、高频面试题AVL树的平衡条件是什么平衡因子的定义插入后为什么要向上更新4种旋转分别在什么场景使用为什么AVL树必须带parent指针如何验证一棵树是AVL树