[问题] 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