AVL Tree Rotation

一.LL rotation:

   1.插入一个节点后,使某个节点的平衡因子大于1,设该节点为A,他的左子节点为B

   2.将A的左子节点指针指向B的右子节点

   3.将B的右子节点指针指向A

   4.将原来指向A节点的指针(A的父节点的左/右子节点指针)指向B

Figure 1 LL rotation:

Figure1

 

二: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:

Figure 2

三: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

 

 

 


版权声明:本文为cceefor原创文章,遵循CC 4.0 BY-SA版权协议,转载请附上原文出处链接和本声明。