作者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/cn.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