自平衡二叉查找树（AVL tree）¶

自平衡二叉查找树（AVL tree）: 首先也是二次查找树，其实任何 2 个子树的高度差不大于 1 在删除，插入的过程中不断调整子树的高度，保证查找操作平均和最坏情况下都是 O(logn)

Adelson-Velskii 和 Landis 1962 年创造, 因此叫做 AVL 树。

1）平衡因子 -1 0 1 节点是正常的。平衡因子 = 左子树高度 - 右字数高度 2）除此之外的节点是不平衡的，需要重新平衡这个树。也就是 AVL 旋转

AVL 实际使用案例

LLVM 的 ImmutableSet，其底层的实现选择为 AVL 树
《一种基于二叉平衡树的 P2P 覆盖网络的研究》论文

插入节点¶

a: 左旋转 (RR 型：节点 x 的右孩子的右孩子上插入新元素）平衡因子由 -1 -》-2 时，需要绕节点 x 左旋转 b：右旋转 (LL 型：节点 X 的左孩子的左孩子上插入新元素）平衡因子有 1-》2，右旋转 c: 先左后右旋转:(LR 型: 树中节点 X 的左孩子的右孩子上插入新元素）平衡因子从 1 变成 2 后，就需要先绕 X 的左子节点 Y 左旋转，接着再绕 X 右旋转 d: 先右后左旋转：(RL 型: 节点 X 的右孩子的左孩子上插入新元素)

    6     6                  6              6           
   /        \               /                \
  5          7             3                  9
/             \             \                 /

3 8 5 7 (LL 型) （RR） (LR) (RL)

删除节点¶

可以看到，为了保证高度平衡，插入和删除操作代价增加

AVL 实现过程中的问题¶

AVL 是严格的平衡二叉树，平衡条件必须满足，即所有节点的左右子树高度差的绝对值不超过 1；

执行插入还是删除操作，只要不满足上面的条件，就要通过旋转来保持平衡，而旋转是非常耗时的，由此我们可以知道 AVL 树适合用于插入与删除次数比较少，但查找多的情况。

由于维护这种高度平衡所付出的代价比从中获得的效率收益还大，故而实际的应用不多，更多的地方是用追求局部平衡而不是非常严格整体平衡的红黑树 ()。