算法与数据结构(4): AVL树

根据维基百科，AVL是最早被发明的自平衡二叉查找树。在AVL树中，任一节点对应的两棵子树的最大高度差为1，因此它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下的时间复杂度都是，表示树的容量。

AVL树本质上还是二叉搜索树，即需要满足左子树的键小于根，右子树的键值大于等于根。

在AVL树中插入或删除结点时，可能会导致树失去平衡，为此需要通过旋转操作来恢复树的平衡。旋转操作又分为左旋和右旋，其示意图如下：

T1,T2和T3都是子树
      
     y                                x
    / \          右旋                /  \
   x   T3   - - - - - - - >        T1   y 
  / \       < - - - - - - -            / \
 T1  T2          左旋                 T2  T3

对于AVL树，其结点对象中相对于一般的二叉搜索树而言还需要多一个数据成员bf，其表示以该结点为根的子树的平衡因子。