[理工] 資結 AVLtree問題 fightforlive PTT批踢踢實業坊

作者: fightforlive (學歷無用論是屁) 2022-07-03 18:42:14

底下是102中山資工的題目
想問一下這三個選項
(A)和(B)看起來都沒錯啊...有反例的?
(C)應該是不一定,主要是在刪除後需要向上調整,一直到全部平衡係數都正常為止
https://i.imgur.com/1ktnmUj.jpg

作者: NCTUCKCurry (CKNCTUCurry) 2022-07-04 16:14:00

B才是對的 AVL tree可以長得很歪 A就有可能會錯

作者: fightforlive (學歷無用論是屁) 2022-07-04 17:56:00

為什麼AVL tree可以長得很歪?

作者: NCTUCKCurry (CKNCTUCurry) 2022-07-04 18:06:00

因為AVL Tree限制的是左右subtree的高度不是限制leaf隨便畫應該就可以畫出反例了

作者: fightforlive (學歷無用論是屁) 2022-07-04 18:15:00

還是畫不出來...左右subtree在長高,leaf也是跟增長,偏左或偏右長下去,也會讓上面的Node不平衡,這樣不是要讓另一邊跟著長?

作者: NCTUCKCurry (CKNCTUCurry) 2022-07-04 18:19:00

作者: fightforlive (學歷無用論是屁) 2022-07-04 18:23:00

感謝~~我好笨...其實滿好畫的,剛剛畫出來了

繼續閱讀