二叉平衡树

平衡二叉树（Balanced Binary Tree）又被称为AVL（Adelson-Velskii and Landis）树，是带有平衡条件（balance condition）的二叉查找树。

性质

它或者是空树，或者具有下列性质：

• 它的左右两个子树的高度差的绝对值不超过1
• 它的左右两个子树都是平衡二叉树
• 具有二叉排序树的性质

术语

• 平衡因子：某结点的左子树与右子树的高度(深度)差即为该结点的平衡因子（BF,Balance Factor）。
  平衡二叉树上所有结点的平衡因子只可能是 -1，0 或 1。
• 结点高度定义：空结点的高度为0；非空结点的高度为以该结点为根结点的树的高度。
• 最小不平衡子树： 以离插入结点最近，且平衡因子绝对值大于1的结点作为根结点的树。
• 旋转：对最小不平衡树进行调整的操作

规则

• 采用二叉链表的结构进行存储
• 结构体中增加结点的高度，用以计算结点的平衡因子
• 插入节点的高度为0，并可能导致树失衡需要调整平衡
• 删除节点，调整成叶子节点后删除（左子树最大或者右子树最小），删除后可能导致树失衡需要调整平衡

旋转

• 右旋

       4                                2
      /           节点4右旋转           / \
     2          ------------->         1  4
    / \                                   /
   1  3                                  3

• 左旋
  5 7
  \ 结点5左旋转 /
  7 --------------> 5 8
  / \
  6 8 6

失衡判断

4种旋转方式：LL型，LR型，RL型，RR型

• LL型(右旋)
  当根结点左子树的左子树中的节点导致根结点的平衡因子为2时，采用LL型旋转进行调整。

• RR型(左旋)
  当根结点右子树的右子树中的节点导致根结点的平衡因子为-2时，采用RR型旋转进行调整。

• LR型(先左旋，再右旋)
  当根结点左子树的右子树中的节点导致根结点的平衡因子为2时，采用LR型旋转进行调整。

• RL型(先右旋，再左旋)
  当根结点右子树的左子树中的节点导致根结点的平衡因子为-2时，采用RL型旋转进行调整。

实现

• 数据结构

typedef int DataType;
typedef struct Node
{
    DataType data;
    struct Node * left;
    struct Node * right;
    int height;
} AVLNode, * AVLTree;

• 函数

int GetHeight(AVLTree T)
int LLRotate(AVLTree  T)
int RRRotate(AVLTree  T)
int LRRotate(AVLTree  T)
int RLRotate(AVLTree  T)
int AVLInsert(AVLTree  T, DataType key)
int AVLDelete(AVLTree T, DataType key)

链接:

• 《数据结构与算法分析:C语言描述(原书第3版)》
• http://www.cnblogs.com/Camilo/p/3917041.html