AVL 树

第一篇AVL树从入门到原理——平衡因子、插入逻辑与单旋实现大家好本篇我们从零开始吃透AVL树从概念、平衡因子、插入流程到最核心的左/右单旋一步步把原理讲透。一、什么是AVL树AVL树是人类最早发明的自平衡二叉搜索树1962年由前苏联科学家 G.M. Adelson-Velsky 和 E.M. Landis 提出因此得名AVL。它本质是一棵二叉搜索树额外满足一条铁律任意节点的左右子树高度差的绝对值 ≤ 1满足这条规则树就不会退化成链表增删查改稳定 O(logN)。为什么高度差是 1不是 0很多人会问完全相等不是更平衡吗节点数量为偶数时根本做不到完全等高2 个节点、4 个节点……必然一边高 1所以用±1做平衡阈值是工程上最合理的选择。二、平衡因子BF——AVL的“平衡仪表盘”为了快速判断是否失衡我们引入平衡因子平衡因子 BF 右子树高度 − 左子树高度合法值-1、0、1失衡值±2必须旋转修复平衡因子不是AVL必需但有了它更新和判断会极其方便。三、AVL树节点结构设计C要实现AVL节点必须带键值对左、右孩子父指针向上更新平衡因子必备平衡因子 bftemplateclassK,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;public:boolInsert(constpairK,Vkv);// 其他接口下篇实现};四、AVL插入4步标准流程插入是AVL最核心的操作逻辑非常固定按BST规则找到位置并插入从新节点向上更新平衡因子正常则结束失衡则旋转旋转后高度恢复直接结束平衡因子怎么更新新节点插在左子树→ 父bf-1新节点插在右子树→ 父bf1什么时候停止更新bf 0子树高度没变停止更新bf ±1子树变高继续向上bf ±2失衡旋转修复然后停止五、AVL旋转总原则所有旋转都必须遵守两条铁律保持二叉搜索树有序恢复平衡并降低子树高度AVL一共四种旋转右单旋LL左单旋RR左右双旋LR右左双旋RL本篇先讲最基础的两种单旋。六、右单旋LL 型失衡场景失衡节点 bf -2左孩子 bf -1→ 左边的左边太高整体向左倾斜核心步骤左孩子的右子树 挂到 失衡节点的左边失衡节点 挂到 左孩子的右边左孩子成为新根重置平衡因子为 0右单旋代码voidRotateR(Node*parent){Node*subLparent-_left;Node*subLRsubL-_right;// 1. subLR 挂载到 parent 左边parent-_leftsubLR;if(subLR)subLR-_parentparent;// 2. parent 挂载到 subL 右边Node*ppparent-_parent;subL-_rightparent;parent-_parentsubL;// 3. 链接上层if(ppnullptr)_rootsubL;elseif(pp-_leftparent)pp-_leftsubL;elsepp-_rightsubL;subL-_parentpp;// 4. 重置平衡因子parent-_bfsubL-_bf0;}七、左单旋RR 型失衡场景失衡节点 bf 2右孩子 bf 1→ 右边的右边太高整体向右倾斜核心步骤和右单旋完全对称右孩子的左子树 挂到 失衡节点的右边失衡节点 挂到 右孩子的左边右孩子成为新根重置平衡因子为 0左单旋代码voidRotateL(Node*parent){Node*subRparent-_right;Node*subRLsubR-_left;// 1. subRL 挂到 parent 右边parent-_rightsubRL;if(subRL)subRL-_parentparent;// 2. parent 挂到 subR 左边Node*ppparent-_parent;subR-_leftparent;parent-_parentsubR;// 3. 链接上层if(ppnullptr)_rootsubR;elseif(pp-_leftparent)pp-_leftsubR;elsepp-_rightsubR;subR-_parentpp;// 4. 重置平衡因子parent-_bfsubR-_bf0;}第一篇总结AVL 自平衡二叉搜索树高度差 ≤ 1平衡因子 BF 右高 − 左高-1/0/1 合法插入 BST插入 向上更新bf 失衡旋转LL 失衡 → 右单旋RR 失衡 → 左单旋