Avl

AVL 树是最早出现的自平衡二叉搜索树，由 G.M. Adelson-Velsky 和 E.M. Landis 于 1962 年在论文《An algorithm for the organization of information》中提出，因此得名 AVL（发明者姓氏首字母），也叫高度平衡树。 平衡二叉树的通用定义（平衡因子、失衡、单旋恢复平衡的例子）见 二叉树与二叉搜索树 §平衡二叉树 Balanced Binary Tree，本文只讲 AVL 特有的部分：严格平衡条件、四种失衡情况的旋转、插入删除的复杂度，以及和其他平衡树、常见平衡树家族的关系。 严格平衡条件 一棵 AVL 树满足以下条件（递归定义）： 左子树和右子树都是 AVL 树。 左子树和右子树的高度差不超过 1。 相比红黑树用颜色规则换取的"相对平衡"，AVL 树是严格平衡：任意结点的平衡因子（左子树高度 − 右子树高度）只能取 -1、0、1。这带来的好处是查找效率稳定，代价是插入、删除时更容易触发再平衡。 树高的维护 判断是否失衡需要知道每个结点的子树高度，通常在结点里额外记一个 height 字段： 空结点（NIL）的高度记为 -1 叶子结点的高度为 0 非叶子结点的高度 = max(左子树高度, 右子树高度) + 1 插入或删除一个结点后，从该结点沿父指针回溯到根，逐层重新计算高度；一旦某个祖先的平衡因子超出 [-1, 1]，该结点就是失衡点，需要旋转恢复平衡。 失衡的四种情况与旋转 失衡点的位置只有 4 种可能，分别对应不同的旋转方式： 情况 触发位置 旋转方式 LL（左左） 左子树的左子树过高 对失衡点做一次右旋 RR（右右） 右子树的右子树过高 对失衡点做一次左旋 LR（左右） 左子树的右子树过高 先对左子树左旋，再对失衡点右旋（双旋） RL（右左） 右子树的左子树过高 先对右子树右旋，再对失衡点左旋（双旋） RR 单旋的完整示例见 二叉树与二叉搜索树 §插入示例，LL 是它的镜像。下面补充一个 LR 双旋的例子。 ...