一.LL rotation:
1.插入一个节点后,使某个节点的平衡因子大于1,设该节点为A,他的左子节点为B
2.将A的左子节点指针指向B的右子节点
3.将B的右子节点指针指向A
4.将原来指向A节点的指针(A的父节点的左/右子节点指针)指向B
Figure 1 LL rotation:
二:LR rotation:
插入一个节点后,使某个节点的平衡因子大于1,设该节点为A,A的左子节点为B,B的右子节点为C,只有当插入节点在A的左子树的右子树(即C)下面时,才进行这种旋转
1.将B的右子节点指针指向C的左子节点
2.将C的左子节点指针指向B
3.将A的左子节点指针指向C的右子节点
4.将C的右子节点指针指向A
5.将原来指向A节点的指针(即A的父节点左/右子节点指针)指向C
Figure 2 LR rotation:
三:RR rotation:
插入一个节点间,使某个节点平衡因子为非1,0,-1三个值,设该节点为A,其右子节点为B,B的右子节点为C,只有当插入节点在A的右子节点的右子节点(即C)时,才进行这种旋转,RR rotation与LL rotation是对称的
1.将A的游子节点间指针指向B的左子节点
2.将B的左子节点指针指向A
3.将原来指向A节点的指针(即A的父节点的左/右子节点指针)指向B
四:RL rotation:
插入一个节点后,使某个节点平衡因子为非1,0,-1三个值,设该节点为A,其右子节点有B,B的左子节点为C,只有当插入节点在A的右子节点的左子节点时,才进行这种旋转,RL rotation与LR rotation是对称的
1.将B的左子节点指针指向C的右子节点
2.将C的右子节点指针指向B
3.将A的右子节点指针指向C的左子节点
4.将C的左子节点指针指向A
5.将原来指向A节点的指针(即A的父节点左/右子节点指针)指向C