--------------------------------------------------------------------------------
标题: 关于平衡二叉树(AVL tree)旋转后平衡标志调整的计算公式
作者: 叶飞虎
建立: 2009.10.18
变更: 2010.06.22
--------------------------------------------------------------------------------

1. 引言
      平衡二叉树的平衡标志计算可以说是最简单的, 也可以说是AVL树中最难的。平衡标
   志计算方法有两种：
      a. Balance = Height(Left) - Height(Right);
      b. Balance = Height(Right) - Height(Left);

      其中 Height 为结点的子树高度(>= 0), 算法简单就是说只要左右子树高度相减即可,
   但运行效率不高。当结点数上千以上时, 频繁增删结点带来开销会相当可观, 正因如此,
   本人通过推理得到的计算公式就非常重要了。

2. 假设
   a. 结点定义
      typedef struct TAVLNode
      {
         void*       Item;          // 存放项
         TAVLNode*   Left;          // 左子结点
         TAVLNode*   Right;         // 右子结点
         TAVLNode*   Parent;        // 父结点
         char        Balance;       // 平衡标志: [-1..1]
      } *PAVLNode;

   b. 平衡增量 D 和 D', D 为左子树增量, D' 为右子树增量, 且 D = -D', D 可以定义
      为 1 或 -1, 其中:
      1). D = 1  则表示平衡标志计算方法为: Height(Left) - Height(Right)
      2). D = -1 则表示平衡标志计算方法为: Height(Right) - Height(Left)

   c. 结点高度的函数 H, 则结点 n 有:
      H(n) = M(H(n.Left), H(n.Right)) + D, 同时 H(NULL) = 0
      其中, M(H(n.Left), H(n.Right) 函数描述如下:
      1). |H(n.Left)| >= |H(n.Right)| 则值为: H(n.Left)
      2). |H(n.Left)| <  |H(n.Right)| 则值为: H(n.Right)

   d. 结点平衡标志的函数 B, 则结点 n 有:
      B(n) = n.Balance = H(n.Left) - H(n.Right)

3. 旋转方式(Left-Left)
   a. 旋转前的树结构和函数方程如下:
            (p)               B(p) = H(t) - H(1) = 2D
            / \
          (t) (1)             B(t) = H(n) - H(2)
          / \
        (n) (2)               B(n) = H(3) - H(4)
        / \
      (3) (4)                 同时必定存在: B(t) != D', 可以用反证法证明.

   b. 旋转后的树结构和函数方程如下: (注: 结点 p, t, n 旋转后分别定义为 P, T, N)
          ( T  )              B(T) = H(N) - H(P)
          /    \              B(N) = H(3) - H(4)
        (N)    (P)            B(P) = H(2) - H(1)
        / \    / \
      (3) (4) (2)(1)          同时必定存在: B(P) != D', 可以用反证法证明.

   c. B(N) 公式
      B(N) = H(3) - H(4)   \
      B(n) = H(3) - H(4)   /  =>    B(N) = B(n) = n.Balance

   d. B(P) 公式
      B(t) = H(n) - H(2)      =>    H(2) = H(n) - B(t)  -+
      B(p) = H(t) - H(1) = 2D =>    H(1) = H(t) - 2D     +
                                    B(P) = H(2) - H(1)  -+

                              =>    B(P) = H(n) - H(t) - B(t) + 2D   \
      由于必定: B(t) != D'    =>    H(t) = H(n) + D                  /
                                 => B(P) = D - B(t) = D - t.Balance

   e. B(T) 公式
      B(t) = H(n) - H(2)      =>    H(n) = B(t) + H(2)  -+
      由于必定: H(N) == H(n)  =>    B(T) = H(n) - H(P)   +
      由于必定: B(P) != D'    =>    H(P) = H(2) + D     -+
                                 => B(T) = B(t) + H(2) - (H(2) + D)
                                 => B(T) = B(t) - D = t.Balance - D

   f. H(T) - H(p) 公式 (即调整后的高度变化)
      B(T) =  B(t) - D        => B(T) != D
                              => H(T)  = H(P) + D     -+
      H(P) = / H(1) + 2D   当 B(P) == D                +
             \ H(1) + D    当 B(P) == 0               -+
                              => H(T) = / H(1) + 3D   当 B(P) == D   -+
                                        \ H(1) + 2D   当 B(P) == 0    |
                                                                      + =>
      H(p) = H(t) + D   \                                             |
      H(t) = H(1) + 2D  /     => H(p) = H(1) + 3D                    -+

      H(T) - H(p) = / 0    当 B(P) == D => B(t) == 0
                    \ -D   当 B(P) == 0 => B(t) != 0

4. 旋转方式(Left-Right)
   a. 旋转前的树结构和函数方程如下:
            (p)               B(p) = H(t) - H(1) = 2D
            / \
          (t) (1)             B(t) = H(2) - H(n)
          / \
        (2) (n)               B(n) = H(3) - H(4)
            / \
          (3) (4)             同时必定存在: B(t) != D, 可以用反证法证明.

   b. 旋转后的树结构和函数方程如下: (注: 结点 p, t, n 旋转后分别定义为 P, T, N)
          ( N  )              B(N) = H(T) - H(P)
          /    \              B(T) = H(2) - H(3)
        (T)    (P)            B(P) = H(4) - H(1)
        / \    / \
      (2) (3) (4)(1)          同时必定存在: B(P) != D, 可以用反证法证明.

   c. B(T) 公式
      H(n) = / H(3) + 2D      当 B(n) == D'
             \ H(3) + D       当 B(n) != D'                    -+
                                                                |
      B(t) = H(2) - H(n)      =>    H(2) = H(n) + B(t)   \      +
                                    B(T) = H(2) - H(3)   /      |
                                 => B(T) = H(n) - H(3) + B(t)  -+

                              =>    B(T) = / B(t) + 2D         当 B(n) == D'
                                           \ B(t) + D          当 B(n) != D'

                              =>    B(T) = / t.Balance + 2D    当 B(n) == D'
                                           \ t.Balance + D     当 B(n) != D'

   d. B(P) 公式
      H(n) = / H(4) + 2D      当 B(n) == D
             \ H(4) + D       当 B(n) != D                     -+
                                                                |
      由于必定: B(t) != D     =>    H(t) = H(n) + D      \      +
      B(p) = H(t) - H(1) = 2D =>    H(1) = H(t) - 2D     /      |
                                 => H(1) = H(n) - D            -+

                              =>    H(1) = / H(4) + D          当 B(n) == D
                                           \ H(4)              当 B(n) != D   -+
                                                                               +
                                    B(P) = H(4) - H(1)                        -+

                              =>    B(P) = / D'                当 B(n) == D
                                           \ 0                 当 B(n) != D

   e. B(N) 公式
                  +- 2D       当 B(T) == 2D  -+
      定义 X(T) = +  D        当 B(T) == D    |
                  +- 0        当 B(T) == 0    |
                              => X(T) = B(T)  + => H(T) = H(3) + B(T) + D     -+
             +- H(3) + 3D     当 B(T) == 2D   |                                |
      H(T) = +  H(3) + 2D     当 B(T) == D    |                                |
             +- H(3) + D      当 B(T) == 0   -+                                |
                                                   B(N) = H(T) - H(P)          +
      定义 X(P) = / D         当 B(P) == D'  -+                                |
                  \ 0         当 B(P) == 0    |                                |
                              => X(P) = -B(P) + => H(P) = H(4) - B(P) + D     -+
      H(P) = / H(4) + 2D      当 B(P) == D'   |
             \ H(4) + D       当 B(P) == 0   -+

                              =>    B(N) = H(3) - H(4) + (B(T) + B(P))  \
                                    B(n) = H(3) - H(4)                  /
                                 => B(N) = B(n) + B(T) + B(P)
                                         = n.Balance + B(T) + B(P)

   f. H(N) - H(p) 公式 (即调整后的高度变化)
      由于 B(T) in {0, D, 2D} => H(T) = H(2) + D
      若 B(n) != D'           => B(N) = B(T) => H(N) = H(T) + D = H(2) + 2D   -+
      若 B(n) == D'           => B(P) = 0                   -+                 |
                                 B(T) = B(t) + 2D            +                 |
                                 B(N) = B(n) + B(T) + B(P)  -+                 +
                                                                               |
                                 => B(N) = B(t) + D => H(N) = H(T) + D         |
                                                            = H(2) + 2D       -+

                                    => H(N) = H(2) + 2D     -+
      H(p) = / H(2) + 2D      当 B(t) == 0                   + =>
             \ H(2) + 3D      当 B(t) != 0                  -+

      H(N) - H(p) = / 0       当 B(t) == 0
                    \ -D      当 B(t) != 0

5. 旋转方式(Right-Left)
   a. 旋转前的树结构和函数方程如下:
      注: 因旋转方式与 (Left-Right) 左右对称, 所以推理方法相同, 故省略推理过程
            (p)               B(p) = H(1) - H(t) = 2D'
            / \
          (1) (t)             B(t) = H(n) - H(2)
              / \
            (n) (2)           B(n) = H(3) - H(4)
            / \
          (3) (4)             同时必定存在: B(t) != D', 可以用反证法证明.

   b. 旋转后的树结构和函数方程如下: (注: 结点 p, t, n 旋转后分别定义为 P, T, N)
          ( N  )              B(N) = H(T) - H(P)
          /    \              B(P) = H(1) - H(3)
        (P)    (T)            B(T) = H(4) - H(2)
        / \    / \
      (1) (3) (4)(2)          同时必定存在: B(P) != D', 可以用反证法证明.

   c. B(T) 公式
      B(T) = / t.Balance + 2D'当 B(n) == D
             \ t.Balance + D' 当 B(n) != D

   d. B(P) 公式
      B(P) = / D              当 B(n) == D'
             \ 0              当 B(n) != D'

   e. B(N) 公式
      B(N) = n.Balance + B(P) + B(T)

   f. H(N) - H(p) 公式 (即调整后的高度变化)
      H(N) - H(p) = / 0       当 B(t) == 0
                    \ -D      当 B(t) != 0

6. 旋转方式(Right-Right)
   a. 旋转前的树结构和函数方程如下:
      注: 因旋转方式与 (Left-Left) 左右对称, 所以推理方法相同, 故省略推理过程
            (p)               B(p) = H(1) - H(t) = 2D'
            / \
          (1) (t)             B(t) = H(2) - H(n)
              / \
            (2) (n)           B(n) = H(3) - H(4)
                / \
              (3) (4)         同时必定存在: B(t) != D, 可以用反证法证明.

   b. 旋转后的树结构和函数方程如下: (注: 结点 p, t, n 旋转后分别定义为 P, T, N)
          ( T  )              B(T) = H(P) - H(N)
          /    \              B(P) = H(1) - H(2)
        (P)    (N)            B(N) = H(3) - H(4)
        / \    / \
      (1) (2) (3)(4)          同时必定存在: B(P) != D, 可以用反证法证明.

   c. B(N) 公式
      B(N) = B(n) = n.Balance

   d. B(P) 公式
      B(P) = D' - B(t) = D' - t.Balance

   e. B(T) 公式
      B(T) = B(t) - D' = t.Balance - D'

   f. H(T) - H(p) 公式 (即调整后的高度变化)
      B(T) =  B(t) - D'       => B(T) != D'
                              => H(T)  = H(P) + D     -+
      H(P) = / H(1) + 2D   当 B(P) == D'               +
             \ H(1) + D    当 B(P) == 0               -+
                              => H(T) = / H(1) + 3D   当 B(P) == D'  -+
                                        \ H(1) + 2D   当 B(P) == 0    |
                                                                      + =>
      H(p) = H(t) + D   \                                             |
      H(t) = H(1) + 2D  /     => H(p) = H(1) + 3D                    -+

      H(T) - H(p) = / 0    当 B(P) == D'=> B(t) == 0
                    \ -D   当 B(P) == 0 => B(t) != 0

7. 增/删结点的要点分析
   a. 插入结点
      插入结点沿着根结点向上增加平衡值, 若检测到 p 为 2D 或 2D' 时, 只要使用 LL,
   LR, RL, 或 RR 中的一种旋转调整平衡值, 且只要需要一次即可并中止向上增加平衡值.

   b. 删除结点
      1). 由于 LR 旋转, 若 B(t) == 0 且 B(n) == D' 时, 则存在 B(T) = 2D 即失去平
         衡, 所以在删除结点若遇到 B(t) == 0 时就改为 LL 旋转即可避开 B(T) = 2D;

      2). 由于 RL 旋转, 若 B(t) == 0 且 B(n) == D 时, 则存在 B(T) = 2D' 即失去平
         衡, 所以在删除结点若遇到 B(t) == 0 时就改为 RR 旋转即可避开 B(T) = 2D';

      3). 删除结点沿着根结点向上减去平衡值, 若检测到 p 为 2D 或 2D' 时, 只要使用
         LL, LR, RL, 或 RR 中的一种旋转调整平衡值, 当 B(t) == 0 时中止向上减去平
         衡值, 否则必须向上减去平衡值.