看板Examination
早上看到這題就覺得你最後答案有點怪
我自己轉一次之後果然有問題XD
你最後的答案與AVL樹定義不符歐
AVL樹的定義包括其子樹也要是AVL樹才對
不然F(n-2)+1就會不正確了XD
最後答案應該是
24
/ \
20 43
/ / \
12 28 55
這樣才對吧？
可以問一下為什麼最後會挑28作為旋轉軸心嗎？
: [考題] 國考歷屆考題與考題觀念討論(書裡看到的選這個)請附上想法、出處
: 輸入資料為:55、43、20、24、28、12
: (二)建立AVL樹
: 轉換過程:http://ppt.cc/pCaf
: 想法:
: 我在step5的時候，關鍵因子是20和43
: 補習班是用43，然後用LR轉換
: 我是選20，然後用RR方式轉
: 在step6時再轉一遍
: 請問我的作法有問題嗎??
: 請高手替我解答，謝謝
--
◆ From: 175.111.51.2
補習班老師那個答案....XD
我先講，他的答案每個步驟都有符合AVL樹的定義
但是第五步轉成那種畸形樣子我完全沒有概念來想像他怎麼轉的
尤其是28原本在24右子樹位置，然後轉完之後跑到左子樹位置去，整個奇蹟XD
但依然符合定義。
如果完全按照LL、RR、LR、RL方式去轉，原PO到第五步跟我都一樣
然後第六步轉到最後的時候我覺得他選錯軸來轉...就這樣而已
下面補一下解法好了
PTT手動排圖好囧阿orz
題目是55, 43, 20 ,24, 28, 12
55
55
/
43
55
/
43
/
20 不符定義，選43開始轉
43
/ \
20 55
43
/ \
20 55
\
24
43
/ \
20 55
\
24
\
28 出現定義不符，選24轉
43
/ \
24 55
/ \
20 28
43
/ \
24 55
/ \
20 28
/
12 又出現定義不符
這時候如果把28往上？
當然不可能...
因為如果把28往上...就會變成這樣...
28
/ \
24 43
/ \
20 55
/
12 還是不符定義
假設你要看01之類的因子...
(1)43
/ \
(0)24 55
/ \
(1) 20 28(1)
/
12 會有點類似這樣（其實我根本不知道因子怎麼表示
但是whatever.....
這時候選24就對了...。
因為當24上去的時候，24以下的左右子樹不會亂跑
然後答案就會回歸到我最後答案的狀態....
....有人要畫一下-1 0 1 之類的圖嗎？其實wiki也有就是了
但我基本上是覺得那個「非常容易混淆」
所以根本不管因子...
實際上也不用管就是了
只要把定義倍好就一定轉得出來
好吧，被你提醒一下我想起來一件事情
我是這樣判斷的...。
首先我們有一株樹長這樣...
43
/ \
24 55
/ \
20 28
/
12
把這棵樹改一下會變成
12 — 20 — 24 — 43 — 55
｜
28
這樣就懂了吧XD
(2) (1) (0) (1) (2)
12 — 20 — 24 — 43 — 55
｜
28(1)
所以選24當作總根.....
讓我解釋的話就會是這樣...
※ 批踢踢實業坊(ptt.cc)※ 文章網址: https://www.ptt.cc/bbs/Examination/M.1370687294.A.1CA.html
推 GLTY:可是我覺得補習班老師最後答案是對的,原PO最後少做一個RR 06/08 18:39
→ GLTY:選28去轉是因為其他的用LL轉不了@[email protected]" 06/08 18:40
→ GLTY:前面說錯...原PO少做一個LL(左右不分...) 06/08 18:41
→ grandoph:因為我在step6時,關鍵因子是43，所以LR把28往上轉 06/08 18:49
推 asdd:我作起來跟A大的答案一樣!! 06/08 18:49
→ ARCHERDEVIL:還有不用一定要用LL阿 你可以用LR(43,24,28挑24往上轉 06/08 18:50
→ ARCHERDEVIL:grandoph你關鍵因子挑錯了 06/08 18:50
→ grandoph:我的確是在最後一步少轉LL 不過我的根節點是28 06/08 18:51
推 asdd:根節點不應該是28 你最後一步應該是往最深的地方作LL 06/08 18:55
推 GLTY:看完講義再做一次結果跟此篇答案一樣了@@" 06/08 19:11
→ ARCHERDEVIL:我本來想解釋一下怎麼選因子，但後來我發現太抽象了 06/08 19:15
→ ARCHERDEVIL:抱歉orz 06/08 19:15
推 GLTY:因子=左子樹高度-右子樹高度~ 06/08 19:16
→ ARCHERDEVIL:原po你把43當關鍵轉的時後... 應該是43 24 28 要轉吧 06/08 20:02
→ ARCHERDEVIL:我剛剛看了一下.... 你該不會是逆時針轉... 06/08 20:02
→ ARCHERDEVIL:所以28 上去，然後24跟42分別成為28的左右子節點...？ 06/08 20:03
→ ARCHERDEVIL:如果是這樣的話你挑關鍵搞不好沒問題，只是轉錯方向.. 06/08 20:04
推 asdd:推A大真熱心！ 06/08 20:18
→ eevvaag:這種題目可能有多種旋轉方式嗎？若最後都符合定義？ 06/08 20:35
→ ARCHERDEVIL:實做跟畫圖不一樣。實做上 可能。因為最後定義對就對 06/08 20:41
→ ARCHERDEVIL:至於畫圖... 你知道學理派的老頭通常都很頑固的XD 06/08 20:41
→ ARCHERDEVIL:asdd 我就當順便複習了XD 06/08 20:42
推 GLTY:這題有解到我的盲點!! 推~ 06/08 20:58