各位好,最近因为想练习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优先,能保证一定使该“子树”平衡吗?
查了几篇教学好像都没有提到这个部份,所以上来请教各位 <(_ _)>