平衡二叉树

平衡二叉树(AVL)

定义

  为避免树的高度增长过快，降低二叉树的性能，我们规定在插入和删除结点时，要保证任意结点的左右子树高度差的绝对值不超过1，将这样的二叉树称为平衡二叉树（AVL）。定义结点左子树与右子树的高度差为该结点的平衡因子，则平衡二叉树结点的平衡因子的值只可能是 -1， 0或 1。

  平衡二叉树：一棵空树，或是具有以下性质的二叉树：它的左子树和右子树都是平衡二叉树，且左子树和右子树的高度差的绝对值不超过1。

平衡二叉树的插入

  基本思路：每当在二叉排序树中插入（删除）一个结点时，首先检查其插入路径上的结点是否因为此次操作二导致了不平衡。若导致了不平衡，则先找到插入路径上离插入结点最近的平衡因子的绝对值是否大于1的结点A，再对以A为根的子树，在保持二叉排序树的特性的前提下，调整各个结点的位置关系，使之重新达到平衡。

  平衡二叉树的插入过程的前半部分与二叉排序树相同，但在新结点插入后，若造成查找路径上的某个结点不再平衡，则需要作出相应的调整。一般可将失去平衡后进行调整的规律归纳为下列四种情况：

  1）LL平衡旋转（右单旋转）。

    由于在根结点的左孩子的左子树（L）上插入一个新结点，根结点的平衡因子由 1 增至 2 ，导致以A为根的子树失去平衡，需要一次向右的旋转操作。将根结点的左孩子向右上旋转代替称为根结点，将根结点向右下旋转成为左孩子的右子树的根结点，而原先左孩子的右子树变为现在根结点的右孩子的左子树。

  2）RR平衡旋转（左单旋转）。

    由于在根结点的右孩子的右子树（R）上插入一个新结点，根结点的平衡因子由 1 增至 2 ，导致以A为根的子树失去平衡，需要一次向左的旋转操作。将根结点的右孩子向左上旋转代替称为根结点，将根结点向左下旋转成为右孩子的左子树的根结点，而原先右孩子的左子树变为现在根结点的左孩子的右子树。

  3）LR平衡旋转（先左后右双旋转）。

    由于在根结点的左孩子的右子树上面插入新结点，导致根结点的两个子树失去平衡，需要进行两次旋转操作，先左旋转后右旋转。先将根结点的左孩子的右子树的根结点向左上旋转提升到根结点的左孩子结点的位置，然后再把该结点向右上旋转提升到根结点的位置。

  4）RL平衡旋转（先右后左双旋转）。

    由于在根结点的右孩子的左子树上面插入新结点，导致根结点的两个子树失去平衡，需要进行两次旋转操作，先右旋转后左旋转。先将根结点的右孩子的左子树的根结点向右上旋转提升到根结点的右孩子结点的位置，然后再把该结点向左上旋转提升到根结点的位置。

平衡二叉树的查找

  在平衡二叉树上进行查找时的过程与二叉排序树的相同。含有n个结点的平衡二叉树的最大深度为O（log2n）,因此平衡二叉树的平均查找长度为O（log2n）。