基于树的查找--------------平衡二叉查找树（2） 平衡

yuyang911220

1，LL型。（左边重，需往右边转）

       

        LL型的判断依据就是:A节点平衡因子为2，B节点的平衡因子为1.

        即: A->bf = 2, B->bf = 1.

        如果失衡类型是LL型，这调整算法如下：

       



       



        以B点为轴，将A节点做顺时针旋转，然后将B的右子树作为A的左子树。

        算法的代码实现如下：（可结合上面的图看）

       

•                         case LL:
  
•                                     B = A->lchild;//该类型B节点所在的位置
•                                     A->lchild = B->rchild;//将B节点的右子树交给A，作为A的左子树。
•                                     B->rchild = A;//把A作为B的右子树。
•                                     A->bf = B->bf = 0;//更新A，B节点的平衡因子的值。
•                                     if (father_A == NULL) *root = B;//如果A是根，则现在把B节点设置为根节点。
•                                     else if (A == father_A->lchild) father_A->lchild = B;//如果原来A是father_A的
•                         //左孩子，则现在把B，作为father_A的左孩子。否则，作为father_A的右孩子，就是用B的取代A原来的位置。
  
•                                     else    father_A->rchild = B;
•                                     break;

该算法的过程实现起来并不难，主要还是有人家的理论在这儿放着。详细的过程看代码注释。
                        2，RR型。与LL型是对称的。（右边重，需往左边转）
       

                        RR型的判断依据就是:A节点平衡因子为-2，B节点的平衡因子为-1.
       
                        即: A->bf = -2, B->bf = -1.
       
                        如果失衡类型是RR型，这调整算法如下：
       
                               
       
                        该类型的调整和LL型调整差不多。以B节点为轴，将A节点作逆时针旋转，然后，把B的       
                        左子树给A，作为A的右子树。
       
                        算法的代码实现如下：       
       
                       

•                                 case RR:
  
•                                     B = A->rchild;//该类型B节点所在的位置
•                                     A->rchild = B->lchild;//把B的左子树给A，充当A的右子树。
•                                     B->lchild = A;//将A充当B的左子树，完成了逆时针旋转。
•                                     A->bf = B->bf = 0;//重新设置平衡因子。
•                                     if (father_A == NULL) *root = B;//看原来A在整个树中的位置，现在将B取代A的位置
•                                     else if (A == father_A->lchild) father_A->lchild = B;
•                                     else father_A->rchild = B;
•                                     break;

       
该类型和LL型是对称的，只要理解了其中一个，另外一个很好理解。

                        3，LR型。（左边，右边都重，都需要转）
       
       
                        该类型又引入了一个特殊节点C。该节点很好判断，和判断B节点一样，插入节点的       
                        “祖先节点”那一线上，A的下一个是B，B的下一个就是C节点。
       
                               
       
                        LR型的判断依据就是:A节点平衡因子为2，B节点的平衡因子为-1.
       
                        即: A->bf = 2, B->bf = -1.
       
                        如果失衡类型是LR型，这调整算法如下：