Re: [考題] 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
使用顏色是因為不好解釋
用看得比較快
看不懂的再推文好了
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.47.155.87
※ 編輯: pongno2 來自: 114.47.155.87 (06/09 00:05)
推
06/09 00:02, , 1F
06/09 00:02, 1F
推
06/09 00:15, , 2F
06/09 00:15, 2F
推
06/09 00:30, , 3F
06/09 00:30, 3F
討論串 (同標題文章)
完整討論串 (本文為第 3 之 3 篇)：