作者fishxd1096 (費許差D)
看板Prob_Solve
標題[問題] AVL Tree應該先做哪種旋轉？
時間Sat Oct 2 16:26:38 2021
各位好，最近因為想練習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://webptt.com/m.aspx?n=bbs/Prob_Solve/M.1633163200.A.87C.html
1F：推 LPH66: 以此例來說, 你應該要判斷 -5 偏哪邊 (它偏右) 10/02 19:26
2F：→ LPH66: 也就是正確應該是: 5 偏左→往左到 -5→-5 偏右→這是 LR 10/02 19:27
3F：→ LPH66: 這個偏哪邊就是你所紀錄的左右高度差的正負號 10/02 19:27
原來還需要看子節點是偏左或右！
實作前看了一篇文章和影片都講成只需判斷形狀上是LL或LR...@@
感謝你的解釋！
※ 編輯: fishxd1096 (182.234.66.58 臺灣), 10/03/2021 23:31:16
4F：推 LPH66: 講判斷形狀也沒錯, 但並不是所有樹邊都要拿來判斷 10/04 19:43
5F：→ LPH66: 要平衡的原因是因為歪了, 所以平衡的方法當然跟歪哪邊有關 10/04 19:44
6F：→ LPH66: 那所謂「判斷形狀」也就只是判斷歪的形狀而已 10/04 19:44
7F：→ skybrest: 推 06/24 10:17