文章目录平衡二叉搜索树平衡因子更新旋转平衡二叉搜索树AVL树名字来源于发明者的名字左右子树都是AVL树左右子树的高度差不超过1节点分布类似于完全二叉树总高度为log2N所以增删查改效率为O(log2N)性能比二叉搜索树稳定提升引入了平衡因子的概念每个节点都有平衡因子等于右子树高度减去左子树高度, 因为左右子树高度差最大为1所以平衡因子范围为1,0-1平衡因子更新每当增删一个节点时都会从增删处逐级向上影响其祖先的平衡因子如果某个祖先的平衡因子从0变成了±1说明该节点子树高度发生了变化需要再影响其上级节点 如果某个祖先的平衡因子从±1变成了0说明该节点的高度没有变化不再向上影响 如果某个祖先的平衡因子为±2或者变成了±2则需要旋转改节点的子树旋转在按二叉搜索树规则插入节点后树变得不平衡就需要对最小的不平衡子树进行旋转即最深的平衡因子为±2的节点旋转的目的是让树从不平衡变为平衡并降低树的高度不会改变树的顺序和中序遍历分为左单旋右单旋左右双旋右左双旋左单旋应对RR失衡平衡因子为2时右子树比左子树深2层且右子树的右子树更深需要将该节点A的右节点B替换A而A则成为B的左节点如果B已经有左节点C将C放在A的右节点上 右单旋LL失衡同理平衡因子为-2时将A-B-C变成B-A-C若B没有右节点C只需要A-B变成B-A 旋转前 │ 旋转后 A │ B \ │ / \ B │ A 右子树 / \ │ \ C 右子树 │ C 旋转前 │ 旋转后 A │ B / │ / \ B │ 左树 A / \ │ / 左树 C │ C 左右双旋LR失衡平衡因子为-2左子树更深但左子树的右子树更深。先对A的左节点B左单旋再对节点A右单旋完成平衡调整。 旋转前 │ 旋转后 A │ C / │ / \ B │ B A \ │ C │ 右左双旋RL失衡平衡因子为2右子树更深但右子树的左子树更深。先对A的右节点B右单旋再对节点A左单旋完成平衡调整。 旋转前 │ 旋转后 A │ C \ │ / \ B │ A B / │ C │