基本算法|图解各种树（三）

AVL树

二叉树，可以退化到单链，也可以满二叉树，用到二叉树时编码的方便，常常虚拟出一种真二叉树，还说到了一种特列（二叉树）来描述多叉树的方法。

二叉树是二维的链表，当二叉树实现了sorted vector的接口后，它变为了有序二叉树，或二叉搜索树，BST，它的任一节点不小于/不大于其左/右后代。

BST也会退化为单链，也就是会失去平衡性，为了解决这个问题，提出了一种保证平衡的策略：

某个节点的左右子树的高度差不大于1，这是一种适度平衡的策略，AVL就是这样一种适度平衡的实现方法，如下所示是一个AVL树：

树的平衡调整，假定已经了解zig(node)和zag(node)操作。

AVL失衡

1 插入节点M

如上所示，M节点插入后，其祖父节点N失衡，曾祖父节点R也会失衡，插入一个节点后可能会引起其祖父，曾祖父等多个节点失衡。

2 删除节点Y

如上所示，删除节点Y后，其祖父R失衡，并且只会引起一个节点的失衡，而插入一个节点会引起多个节点的失衡，称为失衡传播。

3 据上，是否可以说插入操作比删除操作更复杂？

恰恰相反，插入操作是更简单的，因为一旦局部调整一处，整体就好；删除操作可就不是这样了，需要一而再，再而三的调整。

AVL失而复衡

1 插入操作

1）单旋

只需围绕g进行一次zag旋转

2）双旋

需要先围绕p做zig旋转，然后围绕g做zag旋转。

上面说过，插入操作是一个局部调整后便能整体平衡的操作，因此时间复杂度为O(1)，这是理想的。

2 删除操作

1）单旋

删除T3子树下的某个节点后，导致g节点的平衡因子变为+2，失衡，需要绕g节点做一次zig调整。

调整后变为如下：

p节点局部平衡了，是不是代表整体一定平衡了呢？未必！如果T2下圈起的节点存在，则整体就平衡了。

p的某个祖先平衡因子本为-1，如果，T2下的节点不存在，那么调整后这个祖先的平衡因子变为-2，因此，需要进一步检查p的祖先的平衡因子。这是删除操作所特有的失衡传播。

2）双旋

和单旋一样，也会发生失衡向上传播，需要最多log(n)次的向上调整，经过zag(p)和zig(g)操作。