平衡二叉树AVL

AVL

之前写过的二叉排序树（BST）在插入、删除和查找等基本操作的平均时间为 O(logN)， 但在最坏的情况下 ，这些基本运算的时间均会增至 O(n)（因为退化成了链表）。为了避免这些情况发生，人们研究了许多种动态平衡的方法，使得在树中插入或删除元素时，通过调整树的形态来保持树的“平衡”，使之既保持 BST 的性质不变又保证树的高度在任何情况下均为 O(logN)，从而确保树上的基本运算在最坏情况下的时间也均为 O(logN)。下面的 AVL 就是这样的平衡树。

AVL 树是一种平衡二叉树，得名于其发明者的名字（Adelson-Velskii 以及 Landis）。平衡二叉树递归定义如下：

1. 左右子树的高度差小于等于 1。
2. 其每一个子树均为平衡二叉树。

基于两点，我们就可以进行判断其一棵树是否为平衡二叉树了。

实现原理

算法通过平衡因子（balaced factor，用 bf 表示）来具体实现上述平衡二叉树的定义。平衡因子的定义：平衡二叉树中每个节点有一个平衡因子，每个节点的平衡因子是该节点的左子树高度减去右子树的高度。从平衡因子的角度说，若一棵二叉树中所有节点的平衡因子的绝对值都小于等于 1，即平衡因子取值为 0、1 或 -1，则该二叉树为平衡二叉树。
用 C 语言定义该节点为：

typedef struct node
{
    KeyType key;
    int bf;   // 平衡因子
    InfoType data;
    struct node *lchild, *rchild;    
} BSTNode;