作者fightforlive (學歷無用論是屁)
看板Grad-ProbAsk
標題[理工] 資結 AVLtree問題
時間Sun Jul 3 18:42:14 2022
底下是102中山資工的題目
想問一下這三個選項
(A)和(B)看起來都沒錯啊...有反例的?
(C)應該是不一定,主要是在刪除後需要向上調整,一直到全部平衡係數都正常為止
https://i.imgur.com/1ktnmUj.jpg
----
Sent from
BePTT on my iPhone XR
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 27.51.120.117 (臺灣)
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Grad-ProbAsk/M.1656844936.A.FFC.html
1F：推 NCTUCKCurry: B才是對的 AVL tree可以長得很歪 A就有可能會錯 07/04 16:14
2F：→ fightforlive: 為什麼AVL tree可以長得很歪? 07/04 17:56
3F：推 NCTUCKCurry: 因為AVL Tree限制的是左右subtree的高度 不是限制lea 07/04 18:06
4F：→ NCTUCKCurry: f 07/04 18:06
5F：→ NCTUCKCurry: 隨便畫應該就可以畫出反例了 07/04 18:07
6F：→ fightforlive: 還是畫不出來...左右subtree在長高,leaf也是跟增長 07/04 18:15
7F：→ fightforlive: ,偏左或偏右長下去,也會讓上面的Node不平衡,這樣不 07/04 18:15
8F：→ fightforlive: 是要讓另一邊跟著長? 07/04 18:15
10F：→ NCTUCKCurry: ht-difference-between-leaves-in-an-avl-tree 07/04 18:19
11F：→ fightforlive: 感謝~~我好笨...其實滿好畫的,剛剛畫出來了 07/04 18:23