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

看板Prob_Solve (計算數學 Problem Solving)作者 (費許差D)時間3年前 (2021/10/02 16:26), 3年前編輯推噓2(205)
留言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

10/02 19:26, 3年前 , 1F
以此例來說, 你應該要判斷 -5 偏哪邊 (它偏右)
10/02 19:26, 1F

10/02 19:27, 3年前 , 2F
也就是正確應該是: 5 偏左→往左到 -5→-5 偏右→這是 LR
10/02 19:27, 2F

10/02 19:27, 3年前 , 3F
這個偏哪邊就是你所紀錄的左右高度差的正負號
10/02 19:27, 3F
原來還需要看子節點是偏左或右! 實作前看了一篇文章和影片都講成只需判斷形狀上是LL或LR...@@ 感謝你的解釋! ※ 編輯: fishxd1096 (182.234.66.58 臺灣), 10/03/2021 23:31:16

10/04 19:43, 3年前 , 4F
講判斷形狀也沒錯, 但並不是所有樹邊都要拿來判斷
10/04 19:43, 4F

10/04 19:44, 3年前 , 5F
要平衡的原因是因為歪了, 所以平衡的方法當然跟歪哪邊有關
10/04 19:44, 5F

10/04 19:44, 3年前 , 6F
那所謂「判斷形狀」也就只是判斷歪的形狀而已
10/04 19:44, 6F

06/24 10:17, , 7F
06/24 10:17, 7F
文章代碼(AID): #1XM1V0Xy (Prob_Solve)
文章代碼(AID): #1XM1V0Xy (Prob_Solve)