[理工] 資結 AVL Tree

[jerry900287 ()]

題目 :

Construct an AVL tree by inserting 8,9,10,2,1,5,3,6,4,7,11,and 12
successively. You should note the balance factor of each node and show
all necessary rotation.                             【95 中央資管(丙)】

我寫這題寫到平衡時有多個孤立點存在

如圖

https://i.imgur.com/9YQEBMi.png


我聽 洪毅上課 他只說一個孤立點的情形 就是照BST插入

那多個孤立點的時候

是要照 "小到大" 依序 BST 插入 還是照 "題目順序" BST插入?

謝謝~~

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.243.93.245
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1510106727.A.A6C.html
※ 編輯: jerry900287 (111.243.93.245), 11/08/2017 10:06:07
推 TMDTMD2487: 插入孤點 4 跟 (6-7) ， 7不是孤點7的阿拔是6
推 TMDTMD2487: https://i.imgur.com/cPjaiXG.jpg
推 TMDTMD2487: 痾 這是我看多個解答之後自己的結論拉 老師沒有特別講
可是這也是多個孤立點的情況不是嗎QQ??
推 weilun911: 變成孤立點後應該是調整完後在由小到大插入進去 因為AV
→ weilun911: L也是屬於BST
推 TMDTMD2487: 沒有由小到大插入跟BST不會衝突壓@@
推 leoone: 感覺T大的比較對
我想法是 照題目插入的話是 6 4 7 與 照小到大插入的話是 4 6 7 是不衝突沒錯
可是如果今天題目是 7 4 6 這種順序的話 BST 插入
答案就會不一樣惹
※ 編輯: jerry900287 (111.243.93.245), 11/08/2017 12:09:22
→ leoone: 可是由小到大插跟亂序插入BST會長不一樣吧
※ 編輯: jerry900287 (111.243.93.245), 11/08/2017 12:11:14
※ 編輯: jerry900287 (111.243.93.245), 11/08/2017 12:11:53
※ 編輯: jerry900287 (111.243.93.245), 11/08/2017 12:13:05
歐...我好像有點了解T大的講法了 這樣真的就沒衝突了
頂多只有兩個孤立集合 {4},{6-7} 他會分別插在 那個中間鍵值得左右邊
※ 編輯: jerry900287 (111.243.93.245), 11/08/2017 12:18:05
推 TMDTMD2487: 我給你一個實作上的想法 我希望rotation能再最少時間
→ TMDTMD2487: 所以我只想去插入被孤立出來的root大概是這樣
OKOK 太感謝你了
※ 編輯: jerry900287 (111.243.93.245), 11/08/2017 12:20:01
※ 編輯: jerry900287 (111.243.93.245), 11/08/2017 12:20:57
→ TMDTMD2487: https://i.imgur.com/R354J85.jpg
→ TMDTMD2487: 我沒實做過AVL所以剛剛查了一下別人實作的code 概念上
→ TMDTMD2487: 是這樣 資結的東西沒實做過還真的不能講得太有把握
可以!!!
我覺得你講的是對的
※ 編輯: jerry900287 (111.243.93.245), 11/08/2017 12:28:29