98年地特四等資料處理概要 - 考試

※ 引述《ARCHERDEVIL (開弓)》之銘言：
: 標題: Re: [考題] 98年地特四等資料處理概要
: 時間: Sat Jun 8 18:28:11 2013
:
: 早上看到這題就覺得你最後答案有點怪
:
: 我自己轉一次之後果然有問題XD
:
: 你最後的答案與AVL樹定義不符歐
:
: AVL樹的定義包括其子樹也要是AVL樹才對
:
: 不然F(n-2)+1就會不正確了XD
:
: 最後答案應該是
:
: 24
: / \
: 20 43
: / / \
: 12 28 55
: 這樣才對吧？
:
: 可以問一下為什麼最後會挑28作為旋轉軸心嗎？
:
: ....有人要畫一下 -1 0 1 之類的圖嗎？其實wiki也有就是了
左邊 基準 右邊

獻醜一下

(1)55
55
0
(2)43
55
1/
43
0
(3)20 1-1=0
55 43
2/ LL / \
43 --------> 20 55
1/ 0 0
20
0
(4)24
43 2-1=1 43 1
/ \ / \
20 55 --------> 20 55
-1 \ 0 -1 \ 0
24 24
0 0
(5)28
43 3-1=2 43 2-1=1 1 43
/ \ / \ / \
20 55 RR 1-1=0 24 55 0 24 55
-2 \ 0 --------> / \ 0 --------> / \ 0
24 20 28 20 28
-1 \ 0 0 0 0
28
0

(6)12
43 3-1=2 24 2-2=0 0 24
/ \ LL / \ / \
2-1=1 24 55 --------> 1 20 43 1-1=0 --------> 1 20 43 0
/ \ 0 / / \ / / \
1 20 28 12 28 55 12 28 55
/ 0 0 0 0 0 0 0
12
0


使用顏色是因為不好解釋

用看得比較快

看不懂的再推文好了

--