[理工] 資結 AVLtree問題

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