--------------------------------------------------------------------------------
標題: 關于平衡二叉樹(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 時中止向上減去平
衡值, 否則必須向上減去平衡值.
posted on 2011-05-22 10:44
Kyee Ye 閱讀(626)
評論(0) 編輯 收藏 引用 所屬分類:
算法