1
我已经阅读了许多AVL树的源代码,但没有找到解决此问题的人:当AVL树不平衡时,应首先旋转哪个节点?AVL旋转 - 要旋转哪个节点
假设我有树:
10
/\
5 25
/
20
,我尝试添加15,则根及其子25将是不平衡的。
10
/\
5 25
/
20
/
15
我可以做的25 RR循环(或单个旋转),导致下面的树:
10
/\
5 20
/\
15 25
或RL旋转(双旋转)约根,创建下列树:
20
/\
10 25
/\
5 15
我很困惑哪些轮换在这里和类似情况下最合适。