[理工] 資結 AVL Tree

作者: jerry900287 (滷蛋)   2017-11-08 10:05:23
題目 :
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插入?
謝謝~~
作者: TMDTMD2487 (ㄚ冰)   2017-11-08 11:21:00
插入孤點 4 跟 (6-7) , 7不是孤點7的阿拔是6https://i.imgur.com/cPjaiXG.jpg痾 這是我看多個解答之後自己的結論拉 老師沒有特別講
作者: weilun911 (阿偷)   2017-11-08 11:57:00
變成孤立點後應該是調整完後在由小到大插入進去 因為AVL也是屬於BST
作者: TMDTMD2487 (ㄚ冰)   2017-11-08 12:00:00
沒有由小到大插入跟BST不會衝突壓@@
作者: leoone (里歐一代)   2017-11-08 12:05:00
感覺T大的比較對可是由小到大插跟亂序插入BST會長不一樣吧
作者: TMDTMD2487 (ㄚ冰)   2017-11-08 12:17:00
我給你一個實作上的想法 我希望rotation能再最少時間所以我只想去插入被孤立出來的root大概是這樣https://i.imgur.com/R354J85.jpg我沒實做過AVL所以剛剛查了一下別人實作的code 概念上是這樣 資結的東西沒實做過還真的不能講得太有把握

Links booklink

Contact Us: admin [ a t ] ucptt.com