PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

[問題] AVL Tree應該先做哪種旋轉？

看板Prob_Solve (計算數學 Problem Solving)作者fishxd1096 (費許差D)時間3年前 (2021/10/02 16:26)推噓2(2推 0噓 5→)

留言7則, 2人參與討論串1/1

各位好，最近因為想練習C語言，因此在實作一些Tree的結構和演算法剛才在測試AVL是否有bug時發現有一個case同時是LL和LR狀況那我目前邏輯是：如果同時是LL和LR就當作LL case去右旋如果同時是RR和RL就當作RR case去左旋但剛好我自己隨手寫的tree，在這個邏輯下是無法平衡的 insert(5) insert(-5) insert(10) insert(-7) insert(0) insert(-1) 會發生這樣的事情：判斷為LL:右旋 -> 判斷為RR:左旋（回到原始tree）經過在紙上試驗我知道應該當作LR case去處理就能解決但我想問的是：如果邏輯改成LR或者RL優先，能保證一定使該「子樹」平衡嗎？查了幾篇教學好像都沒有提到這個部份，所以上來請教各位 <(_ _)> -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 182.234.66.58 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1633163200.A.87C.html

推

LPH66

10/02 19:26, 3年前 , 1^F

10/02 19:26, 1^F

→

LPH66

10/02 19:27, 3年前 , 2^F

10/02 19:27, 2^F

→

LPH66

10/02 19:27, 3年前 , 3^F

10/02 19:27, 3^F

原來還需要看子節點是偏左或右！實作前看了一篇文章和影片都講成只需判斷形狀上是LL或LR...@@ 感謝你的解釋！ ※ 編輯: fishxd1096 (182.234.66.58 臺灣), 10/03/2021 23:31:16