--------------------------------------------------------------------------------
標(biāo)題: 關(guān)于平衡二叉樹(AVL tree)旋轉(zhuǎn)后平衡標(biāo)志調(diào)整的計(jì)算公式
作者: 葉飛虎
建立: 2009.10.18
變更: 2010.06.22
--------------------------------------------------------------------------------

1. 引言
      平衡二叉樹的平衡標(biāo)志計(jì)算可以說是最簡單的, 也可以說是AVL樹中最難的。平衡標(biāo)
   志計(jì)算方法有兩種：
      a. Balance = Height(Left) - Height(Right);
      b. Balance = Height(Right) - Height(Left);

      其中 Height 為結(jié)點(diǎn)的子樹高度(>= 0), 算法簡單就是說只要左右子樹高度相減即可,
   但運(yùn)行效率不高。當(dāng)結(jié)點(diǎn)數(shù)上千以上時(shí), 頻繁增刪結(jié)點(diǎn)帶來開銷會(huì)相當(dāng)可觀, 正因如此,
   本人通過推理得到的計(jì)算公式就非常重要了。

2. 假設(shè)
   a. 結(jié)點(diǎn)定義
      typedef struct TAVLNode
      {
         void*       Item;          // 存放項(xiàng)
         TAVLNode*   Left;          // 左子結(jié)點(diǎn)
         TAVLNode*   Right;         // 右子結(jié)點(diǎn)
         TAVLNode*   Parent;        // 父結(jié)點(diǎn)
         char        Balance;       // 平衡標(biāo)志: [-1..1]
      } *PAVLNode;

   b. 平衡增量 D 和 D', D 為左子樹增量, D' 為右子樹增量, 且 D = -D', D 可以定義
      為 1 或 -1, 其中:
      1). D = 1  則表示平衡標(biāo)志計(jì)算方法為: Height(Left) - Height(Right)
      2). D = -1 則表示平衡標(biāo)志計(jì)算方法為: Height(Right) - Height(Left)

   c. 結(jié)點(diǎn)高度的函數(shù) H, 則結(jié)點(diǎn) n 有:
      H(n) = M(H(n.Left), H(n.Right)) + D, 同時(shí) H(NULL) = 0
      其中, M(H(n.Left), H(n.Right) 函數(shù)描述如下:
      1). |H(n.Left)| >= |H(n.Right)| 則值為: H(n.Left)
      2). |H(n.Left)| <  |H(n.Right)| 則值為: H(n.Right)

   d. 結(jié)點(diǎn)平衡標(biāo)志的函數(shù) B, 則結(jié)點(diǎn) n 有:
      B(n) = n.Balance = H(n.Left) - H(n.Right)

3. 旋轉(zhuǎn)方式(Left-Left)
   a. 旋轉(zhuǎn)前的樹結(jié)構(gòu)和函數(shù)方程如下:
            (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)                 同時(shí)必定存在: B(t) != D', 可以用反證法證明.

   b. 旋轉(zhuǎn)后的樹結(jié)構(gòu)和函數(shù)方程如下: (注: 結(jié)點(diǎn) p, t, n 旋轉(zhuǎ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)          同時(shí)必定存在: 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) 公式 (即調(diào)整后的高度變化)
      B(T) =  B(t) - D        => B(T) != D
                              => H(T)  = H(P) + D     -+
      H(P) = / H(1) + 2D   當(dāng) B(P) == D                +
             \ H(1) + D    當(dāng) B(P) == 0               -+
                              => H(T) = / H(1) + 3D   當(dāng) B(P) == D   -+
                                        \ H(1) + 2D   當(dāng) B(P) == 0    |
                                                                      + =>
      H(p) = H(t) + D   \                                             |
      H(t) = H(1) + 2D  /     => H(p) = H(1) + 3D                    -+

      H(T) - H(p) = / 0    當(dāng) B(P) == D => B(t) == 0
                    \ -D   當(dāng) B(P) == 0 => B(t) != 0

4. 旋轉(zhuǎn)方式(Left-Right)
   a. 旋轉(zhuǎn)前的樹結(jié)構(gòu)和函數(shù)方程如下:
            (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)             同時(shí)必定存在: B(t) != D, 可以用反證法證明.

   b. 旋轉(zhuǎn)后的樹結(jié)構(gòu)和函數(shù)方程如下: (注: 結(jié)點(diǎn) p, t, n 旋轉(zhuǎ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)          同時(shí)必定存在: B(P) != D, 可以用反證法證明.

   c. B(T) 公式
      H(n) = / H(3) + 2D      當(dāng) B(n) == D'
             \ H(3) + D       當(dāng) 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         當(dāng) B(n) == D'
                                           \ B(t) + D          當(dāng) B(n) != D'

                              =>    B(T) = / t.Balance + 2D    當(dāng) B(n) == D'
                                           \ t.Balance + D     當(dāng) B(n) != D'

   d. B(P) 公式
      H(n) = / H(4) + 2D      當(dāng) B(n) == D
             \ H(4) + D       當(dāng) 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          當(dāng) B(n) == D
                                           \ H(4)              當(dāng) B(n) != D   -+
                                                                               +
                                    B(P) = H(4) - H(1)                        -+

                              =>    B(P) = / D'                當(dāng) B(n) == D
                                           \ 0                 當(dāng) B(n) != D

   e. B(N) 公式
                  +- 2D       當(dāng) B(T) == 2D  -+
      定義 X(T) = +  D        當(dāng) B(T) == D    |
                  +- 0        當(dāng) B(T) == 0    |
                              => X(T) = B(T)  + => H(T) = H(3) + B(T) + D     -+
             +- H(3) + 3D     當(dāng) B(T) == 2D   |                                |
      H(T) = +  H(3) + 2D     當(dāng) B(T) == D    |                                |
             +- H(3) + D      當(dāng) B(T) == 0   -+                                |
                                                   B(N) = H(T) - H(P)          +
      定義 X(P) = / D         當(dāng) B(P) == D'  -+                                |
                  \ 0         當(dāng) B(P) == 0    |                                |
                              => X(P) = -B(P) + => H(P) = H(4) - B(P) + D     -+
      H(P) = / H(4) + 2D      當(dāng) B(P) == D'   |
             \ H(4) + D       當(dāng) 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) 公式 (即調(diào)整后的高度變化)
      由于 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      當(dāng) B(t) == 0                   + =>
             \ H(2) + 3D      當(dāng) B(t) != 0                  -+

      H(N) - H(p) = / 0       當(dāng) B(t) == 0
                    \ -D      當(dāng) B(t) != 0

5. 旋轉(zhuǎn)方式(Right-Left)
   a. 旋轉(zhuǎn)前的樹結(jié)構(gòu)和函數(shù)方程如下:
      注: 因旋轉(zhuǎn)方式與 (Left-Right) 左右對(duì)稱, 所以推理方法相同, 故省略推理過程
            (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)             同時(shí)必定存在: B(t) != D', 可以用反證法證明.

   b. 旋轉(zhuǎn)后的樹結(jié)構(gòu)和函數(shù)方程如下: (注: 結(jié)點(diǎn) p, t, n 旋轉(zhuǎ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)          同時(shí)必定存在: B(P) != D', 可以用反證法證明.

   c. B(T) 公式
      B(T) = / t.Balance + 2D'當(dāng) B(n) == D
             \ t.Balance + D' 當(dāng) B(n) != D

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

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

   f. H(N) - H(p) 公式 (即調(diào)整后的高度變化)
      H(N) - H(p) = / 0       當(dāng) B(t) == 0
                    \ -D      當(dāng) B(t) != 0

6. 旋轉(zhuǎn)方式(Right-Right)
   a. 旋轉(zhuǎn)前的樹結(jié)構(gòu)和函數(shù)方程如下:
      注: 因旋轉(zhuǎn)方式與 (Left-Left) 左右對(duì)稱, 所以推理方法相同, 故省略推理過程
            (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)         同時(shí)必定存在: B(t) != D, 可以用反證法證明.

   b. 旋轉(zhuǎn)后的樹結(jié)構(gòu)和函數(shù)方程如下: (注: 結(jié)點(diǎn) p, t, n 旋轉(zhuǎ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)          同時(shí)必定存在: 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) 公式 (即調(diào)整后的高度變化)
      B(T) =  B(t) - D'       => B(T) != D'
                              => H(T)  = H(P) + D     -+
      H(P) = / H(1) + 2D   當(dāng) B(P) == D'               +
             \ H(1) + D    當(dāng) B(P) == 0               -+
                              => H(T) = / H(1) + 3D   當(dāng) B(P) == D'  -+
                                        \ H(1) + 2D   當(dāng) B(P) == 0    |
                                                                      + =>
      H(p) = H(t) + D   \                                             |
      H(t) = H(1) + 2D  /     => H(p) = H(1) + 3D                    -+

      H(T) - H(p) = / 0    當(dāng) B(P) == D'=> B(t) == 0
                    \ -D   當(dāng) B(P) == 0 => B(t) != 0

7. 增/刪結(jié)點(diǎn)的要點(diǎn)分析
   a. 插入結(jié)點(diǎn)
      插入結(jié)點(diǎn)沿著根結(jié)點(diǎn)向上增加平衡值, 若檢測(cè)到 p 為 2D 或 2D' 時(shí), 只要使用 LL,
   LR, RL, 或 RR 中的一種旋轉(zhuǎn)調(diào)整平衡值, 且只要需要一次即可并中止向上增加平衡值.

   b. 刪除結(jié)點(diǎn)
      1). 由于 LR 旋轉(zhuǎn), 若 B(t) == 0 且 B(n) == D' 時(shí), 則存在 B(T) = 2D 即失去平
         衡, 所以在刪除結(jié)點(diǎn)若遇到 B(t) == 0 時(shí)就改為 LL 旋轉(zhuǎn)即可避開 B(T) = 2D;

      2). 由于 RL 旋轉(zhuǎn), 若 B(t) == 0 且 B(n) == D 時(shí), 則存在 B(T) = 2D' 即失去平
         衡, 所以在刪除結(jié)點(diǎn)若遇到 B(t) == 0 時(shí)就改為 RR 旋轉(zhuǎn)即可避開 B(T) = 2D';

      3). 刪除結(jié)點(diǎn)沿著根結(jié)點(diǎn)向上減去平衡值, 若檢測(cè)到 p 為 2D 或 2D' 時(shí), 只要使用
         LL, LR, RL, 或 RR 中的一種旋轉(zhuǎn)調(diào)整平衡值, 當(dāng) B(t) == 0 時(shí)中止向上減去平
         衡值, 否則必須向上減去平衡值.