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

作者: fishxd1096 (UN_ReAL)   2021-10-02 16:26:38
各位好,最近因為想練習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優先,能保證一定使該「子樹」平衡嗎?
查了幾篇教學好像都沒有提到這個部份,所以上來請教各位 <(_ _)>
作者: LPH66 (-6.2598534e+18f)   2021-10-02 19:26:00
以此例來說, 你應該要判斷 -5 偏哪邊 (它偏右)也就是正確應該是: 5 偏左→往左到 -5→-5 偏右→這是 LR這個偏哪邊就是你所紀錄的左右高度差的正負號
作者: skybrest (Be Still My Heart)   2020-06-24 10:17:00

Links booklink

Contact Us: admin [ a t ] ucptt.com