AVL Tree

简介

在AVL树中，任一结点对应的两颗子树的最大高度差为1，因此它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下的时间复杂度都是O(log n)。增加和删除元素的操作则可能需要借由一次或多次树旋转，以实现树的重新平衡。

在开始之前请明确树的高度的概念。

以下面这颗树为例，标明各个结点的高度

          30(2)
          / \
         /   \
       17(1)  40(0)
       /\
      /  \
   14(0) 20(0)

为了方便起见，空结点的高度设定为-1，例如上图右下的40结点，左右孩子都为空，高度看作-1，这样计算像40这样的结点高度时不用指定特殊情况：左右孩子高度最大值加一(-1+1=0)

属性

AVL树每个结点左右子树的高度差不超过1，如上图根结点30，左子树高度为1，右子树高度为0，相差1。

基本操作

旋转(Rotation)

如下图所示，从左到右为对X结点左旋(X结点移动到左侧)，从右到左为对Y结点右旋(Y结点移动到右侧)

           X                                 Y
          / \         left_rotate(X)        / \
         /   \        ---------------->    /   \
       A子树  Y    <----------------      X   C子树
              /\      right_rotate(Y)    /\
             /  \                       /  \
          B子树 C子树               A子树 B子树

此操作花费恒定的O(1)时间，而且变换后满足二叉搜索树的属性，你可以看到操作前后它的中序遍历都是A,X,B,Y,C

插入

1. 插入到二叉搜索树
2. 修复AVL属性

第一步就是很普通的把结点插入到二叉搜索树，重点在第二步如何保持AVL树的属性，请看下面的两种情况(括号内为结点高度)：

如果X的右子树(Y树)右侧偏重(C子树高度大于B子树高度)，进行左旋X操作

           X(k)                            Y(k-1)
          / \         left_rotate(X)        / \
         /   \        ---------------->    /   \
   A子树(k-3) Y(k-1)                   X(k-2)  C子树(k-2)
              /\                         /\
             /  \                       /  \
     B子树(k-3) C子树(k-2)      A子树(k-3) B子树(k-3)
     
否则，对Z进行右旋操作，再对X进行左旋操作

           X          right_totate(Z)        Y
          / \          left_rotate(X)       / \
         /   \        ---------------->    /   \
      A子树   Z                           X     Z
              /\                         /\     /\
             /  \                       /  \   /  \
            Y   D子树                  A   B   C   D
           /\                         子  子   子  子
          /  \                        树  树   树  树
      B子树  C子树

你可以使用它进行排序，逐个插入结点时间复杂度为O(nlogn)，之后进行中序遍历时间复杂度为O(n)，就可以得到递增的序列。

tags: #数据结构 #排序 #二叉搜索树 #AVL树