AVL 树 LR 型旋转

一、前置基础插入后初始树结构与核心规则在节点3的左孩子2的右子树位置插入节点2.5后AVL树的初始结构如下节点后括号内为树高未标注则默认后续计算5 / \ 3 6 / \ 2 4 \ 2.5核心前提的两个关键规则二叉搜索树BST规则任意节点的左子树所有节点值均小于该节点值右子树所有节点值均大于该节点值即“左小右大”AVL树平衡规则任意节点的平衡因子BF左子树高度-右子树高度需满足|BF|≤1若不满足则判定为失衡需通过旋转矫正。二、失衡判定找到失衡节点与旋转类型插入节点2.5后需从插入节点向上回溯计算每个节点的树高和平衡因子找到首个失衡节点并判定旋转类型。一各节点树高与平衡因子计算节点2.5无左右子树树高为1BF0左高0-右高0无失衡节点2左子树高0右子树高1节点2.5的高度树高为2BF0-1-1|BF|≤1无失衡节点4无左右子树树高为1BF0无失衡节点3左子树高2节点2的高度右子树高1节点4的高度树高为3BF2-11|BF|≤1无失衡节点6无左右子树树高为1BF0无失衡节点5左子树高3节点3的高度右子树高1节点6的高度树高为4BF3-12|BF|1判定为失衡且是回溯过程中首个失衡节点。二旋转类型判定LR型旋转类型由失衡节点及其左、右孩子的平衡因子共同决定具体判定逻辑如下失衡节点5的BF2说明左子树过高失衡方向为“左偏重”失衡节点5的左孩子为节点3节点3的BF1说明节点3的左子树偏高但结合初始树结构可见节点3的右子树节点4与插入节点2.5形成“左-右”折线结构3→左2→右2.53→右4本质是左子树的右分支偏高综上判定为LR型失衡左子树的右分支失衡对应的矫正规则为先左旋失衡节点的左子树节点节点3将折线结构转为直线结构再右旋失衡节点节点5最终恢复树的平衡。三、旋转操作步骤分步执行兼顾平衡与BST规则LR型旋转需分两步执行先左旋节点3再右旋节点5每一步操作都需严格遵循旋转规则确保不破坏BST的“左小右大”特性同时逐步矫正平衡因子。第一步左旋节点3将LR型转为LL型左旋操作的核心目的是将节点3的“左-右”折线结构转为“左-左”直线结构为后续右旋操作铺垫具体旋转规则及步骤如下确定旋转核心节点以节点3为左旋节点其右孩子节点4为旋转后的替代节点节点转移将节点4的左子树此处为空挂载到节点3的右孩子位置替代原节点4的位置父子关系调整将节点3作为节点4的左孩子完成节点3与节点4的父子关系互换树高更新调整节点3和节点4的树高节点3的树高变为2左子树节点2的高度11节点4的树高变为3左子树节点3的高度21位置衔接将旋转后的节点4替代原节点3的位置作为节点5的左孩子。左旋节点3后的中间态已转为LL型结构5 / \ 4 6 / 3 / 2 \ 2.5此时节点5的左子树为节点4形成“左-左”直线结构LR型失衡已转为LL型失衡满足后续右旋操作的条件。第二步右旋失衡节点5恢复树的平衡右旋操作的核心目的是矫正节点5的左子树过高问题将节点4晋升为新的子树根节点使树恢复平衡具体旋转规则及步骤如下确定旋转核心节点以节点5为右旋节点其左孩子节点4为旋转后的新根节点节点转移将节点4的右子树此处为空挂载到节点5的左孩子位置替代原节点4的位置父子关系调整将节点5作为节点4的右孩子完成节点5与节点4的父子关系互换树高更新调整节点5和节点4的树高节点5的树高变为2右子树节点6的高度11节点4的树高变为3左子树节点3的高度2、右子树节点5的高度2取最大值1最终衔接节点4成为该子树的新根节点保持原有其他节点的父子关系不变节点3仍为节点4的左孩子节点6仍为节点5的右孩子。四、旋转最终结果与校验一最终平衡AVL树结构经过“左旋节点3→右旋节点5”两步操作后最终得到的平衡AVL树结构如下4 / \ 3 5 / \ 2 6 \ 2.5二双重校验确保合规与平衡BST规则校验左小右大节点2的右孩子2.522.5符合规则节点3的左孩子223符合规则节点4的左子树3、2、2.5均小于4右子树5、6均大于4符合规则节点5的右孩子656符合规则所有节点均满足“左小右大”BST规则完全合规。AVL平衡规则校验|BF|≤1节点2.5BF0节点2BF-1节点3BF1节点6BF0节点5BF-1节点4BF0所有节点的平衡因子绝对值均不超过1树的平衡状态完全恢复。五、总结本次AVL树旋转操作核心是处理插入节点2.5后出现的LR型失衡通过“先左旋左子节点、再右旋失衡节点”的两步操作成功将失衡树矫正为平衡树。整个过程始终遵循BST“左小右大”和AVL“平衡因子≤1”的核心规则先将折线结构转为直线结构再通过旋转调整节点位置最终实现树的平衡。LR型旋转是AVL树中较复杂的旋转类型关键在于准确判定失衡类型分步执行旋转操作每一步都兼顾节点位置调整和树高更新确保旋转后既符合BST规则又能恢复AVL树的平衡特性本次操作最终得到的树结构即为合规、平衡的最终结果无需进一步旋转。