一．概述
avl 树是每个节点的左子树和右子树的高度最多差 1 的二叉查找树.一棵高度为 h 的 avl
树最少节点数由 S(h) = S(h-1)+S(h-2)+1 得到.
avl 树要保证任一节点的左右子树的高度之差的绝对值不能超过 1(空树的高定义为 1).
在插入和删除的时候就需要根据情况对树的某些节点做调整.
二．插入
设 T 是一棵满足 avl 树.X 是 T 的一个节点.导致 X 不平衡(对于插入来说)有下面四种情
况:
1.对 T 的左子树的左子树做插入操作
2.对 T 的左子树的右子树做插入操作
3.对 T 的右子树的左子树做插入操作
4.对 T 的右子树的右子树做插入操作
其中, 1 和 4、2 和 3 分别是关于 T 的镜像对称。可以只讨论 1、2。
a.对于情形 1,可以通过一个单旋转来使节点回复平衡。如图所示：
k1
21
1
x
k 2
y
z
k1
21
1
k 2
y
z
x
旋转之前
旋转之后
