AVL树学习笔记（一）：原理

AVL树是最早发明的自平衡二叉查找树，其节点的平衡因子是它的左子树的高度减去它的右子树的高度（有时相反）。带有平衡因子1、0或 -1的节点被认为是平衡的。带有平衡因子 -2或2的节点被认为是不平衡的，并需要重新平衡这个树。平衡因子可以直接存储在每个节点中，或从可能存储在节点中的子树高度计算出来。

AVL树的节点需要存储除了一般的二叉查找树之外的高度信息，用于计算平衡因子。

AVL树的平衡性非常好。这保证了其插入，删除，查找和遍历的算法时间复杂度都为O(logN)。 比起普通的二叉查找树，AVL树仅仅在插入和删除上有额外的平衡操作。

在引起不平衡的情况有四种（以下图片引自wikipedia）：

其中后两种情况实际上是将节点旋转为前两种情况再对整个不平衡的节点进行左/右旋转。因此不需要特别说明。

详细说明一下左/右旋转。

左旋转： 将要旋转的节点成为其右节点的左子节点（N 右旋转： 将要旋转的节点成为其左节点的右子节点（N>Nl），左节点的右子节点成为其左节点(N>Nlr)。此操作看起来就像这个节点向右边旋转了一样。这样左边的节点高度就减少了1 。 对于AVL树的插入操作，需要对插入的节点进行平衡处理。分为以下几种情况：

若插入的节点为左节点，且其祖父节点平衡因子为2，其父节点为其祖父节点的左子节点，则对其祖父节点进行右旋转；
若插入的节点为右节点，且其祖父节点平衡因子为-2，其父节点为其祖父节点的右子节点，则对其祖父节点进行左旋转；
若插入的节点为左节点，且其祖父节点平衡因子为2，其父节点为其祖父节点的右子节点，则先对其父节点进行右旋转，使其祖父节点成为情况2的样子，再对其祖父节点进行左旋转。
若插入的节点为右节点，且其祖父节点平衡因子为2，其父节点为其祖父节点的左子节点，则先对其父节点进行左旋转，使其祖父节点成为情况1的样子，再对其祖父节点进行右旋转。

需要特别说明的是，当节点进行旋转了之后，会更改父节点的指针，如对某节点进行左旋转，其右子节点会代替其位置成为新的父节点。 插入过程中，在对插入节点进行平衡操作后，还需要从下往上对父节点进行平衡操作。由于每次插入都会对插入节点进行平衡，这时候出现的不平衡只会有1和2的情况，因此只需要简单左右旋转即可。

对于AVL树的删除节点操作，可以使用一般的算法删除节点后平衡，也可以旋转节点使其成为叶子节点再进行删除和平衡。个人比较喜欢第二种方法，概念非常的清晰，充分利用到了AVL树的平衡性能。下面就以第二种方法进行说明：

待删除的节点没有左子节点的时候，对其进行左旋转使其成为叶子节点；
待删除的节点没有右子节点的时候，对其进行右旋转使其成为叶子节点；
待删除的节点既有左子节点又有有子节点的时候，向高度小的一侧进行旋转，如果高度一致，则任选一边；
待删除的节点为叶子节点时，直接删除该节点即可；

在删除操作完成之后，需要从下往上进行平衡操作。由于在旋转节点的过程中可能打乱了平衡，因此四种情况都可能出现。 AVL树的查找，遍历算法和普通的二叉查找树没有区别，此处不再详细描述。 下一篇将分析实现代码。