最近面试被问到平衡二叉树如何保证平衡即失衡后是如何调整的, 之前也只是在leetcode上做过判断是否为平衡二叉树和树的深度搜索之类的题目,对AVL保证平衡的旋转方法及实现并不不了解,所以答不上来.回去后仔细了解了下,记录一下.

AvlTree的定义

AVL (Adelson Velskii和 Landis)树是带有平衡条件的二叉查找树。这个平衡条件必须容易保持，而且它必须保证树的深度是O(log N). 最简单的想法是要求左右子树具有相同的高度.

一般限制为：一棵AVL树是其每个节点的左子树和右子树的高度最多差1的二叉查找树(空树的高度定义为-1，树中叶子的高度为0，往根上递增).

插入操作的问题

在对AVL树进行插入操作的时候,隐含的困难在于,插入一个节点可能破坏AVL树的平衡特性.

所以一般发生这种情况，我们需要把AVL树的平衡性质恢复之后才能算是插入这一步骤完成。事实上，我们只需要根据树的实际结构进行几种简单的旋转（rotation）操作就可以让树恢复AVL树的平衡性质。

四种旋转的情况

若平衡二叉树种某个结点的左子树和右子树的高度相差大于1，该树就是失衡了，该结点称为失衡点，就要通过旋转来保持二叉树的平衡

一共分四种情况导致结点失衡：

  • 在结点的左孩子的左子树中插入数据（LL）
  • 在结点的左孩子的右子树中插入数据（LR）
  • 在结点的右孩子的左子树中插入数据（RL）
  • 在结点的右孩子的右子树中插入数据（RR)

第1和4种情况是对称的，可用单旋来解决，而第2和3种情况也是对称的，要用双旋来解决

LL型（左孩子的左子树）通过右旋解决

对于LL型的情况，要使用右旋来解决，将失衡点右旋到其左孩子的右孩子的位置，失衡点的左子树更新为其原来左孩子的右子树


RR型（右孩子的右子树）通过左旋解决

对于RR型的情况，要使用左旋来解决，将失衡点左旋到其右孩子的左孩子的位置，失衡点的右子树更新为其原来右孩子的左子树


LR型（左孩子的右子树）通过先左旋再右旋解决

对于LR型的情况，要使用先对失衡点的左孩子进行左旋，然后再对失衡点进行右旋来解决


RL型（右孩子的左子树）通过先右旋再左旋解决

对于RL型的情况，要使用先对失衡点的右孩子进行右旋，然后再对失衡点进行左旋来解决


以上图片来自 AVL平衡二叉树详解与实现