数据结构与算法系列研究五——树、二叉树、三叉树、平衡排序二叉树AVL(4)

View Code

四、平衡排序二叉树AVL

4.1．实验内容

建立排序平衡二叉树。

4.2．输入与输出

输入：输入一组节点，从而构建平衡排序二叉树。

输出：输出平衡二叉树的先序，中序遍历，以及每个结点的平衡因子，以便进行还原二叉树的形状，判断算法能否恰当。

4.3．关键数据结构与核心算法

关键数据结构：

因为是二叉树，则要有基本的节点，左右孩子指针，因为要顺序转动，则要知道平衡因子，注意这里可以按照需要来添加双亲指针，因为采用了引用，则省去了这里。因此数据结构为：

typedef struct BSTNode

{

int data;//信息

int bf;//平衡因子

struct BSTNode *lchild,*rchild; //平衡树左右儿子指针

}BSTNode,*BSTree;//平衡二叉排序树结构的定义

核心算法：

建立平衡排序二叉树算是算法中非常复杂的一个了，但是找到核心以后，也就仅仅相当复杂一些罢了，多训练一下即可。那核心是哪个呢？要提问这个疑问，就要深刻理解“平衡”和“排序”两个词的涵义。顾名思义，平衡二叉树加上排序二叉树即是所要建的树。1.平衡二叉树要求每一个节点的左子树深度减去右子树的深度的绝对值要大于1。2.排序二叉树要求根据中序遍历该二叉树得到从小到大排序的序列。因此在每插入一个结点的之后都要判定是否平衡，1.若平衡则根据排序二叉树的方式插入之，然后刷新平衡因子即可。2.重要是不平衡的之后还要从最接近的不平衡的地方旋转的让它平衡，这样再次进去，不断插入就可以得到顺序平衡二叉树。

下面主要解释一下旋转技巧：旋转共有4种方式，其实二叉排序树 数据结构，最核心的唯有两种基本操作即是L_Rotate( )和R_Rotate( )，分别是左旋和右旋。

对于LL型，即是最先出错的节点平衡因子是2，左儿子平衡因子是1，运用一次右旋操作再刷新平衡因子即可。根据镜像对称方法，RR型与此是对应的，如法炮制即可。

重要的而且复杂的是LR和RL操作，这两个操作也有镜像对称的只讲一个即可。就包括LR吧，最先出错的节点的平衡因子是2，该节点的左孩子的平衡因子是-1.则要对左孩子为根的子树进行左旋，然后对该最近节点进行右旋，刷新平衡因子即可。具体算法如下：

  1 /**************************两个基本操作*****************************/
  2 void L_Rotate(BSTree &p)  
  3 {
  4     //对以*p为根的二叉排序树做左旋处理，处理之后p指向新的树根结点
  5     //和R_Rotate()镜像对称
  6    BSTree rc;
  7    rc = p->rchild;
  8    p->rchild = rc->lchild;
  9    rc->lchild = p;
 10    p = rc;    
 11 }  
 12 void R_Rotate(BSTree &p)  
 13 {
 14     //对以*p为根的二叉排序树做右旋处理，处理之后p指向新的树根结点
 15     //注意此处引用的好处就是不用再出现双亲指针
 16    BSTree lc;
 17    lc=p->lchild; //指向B的位置
 18    p->lchild=lc->rchild; //此处转换仍保持中序遍历不变性
 19    lc->rchild=p; //更改a的指针位置
 20    p=lc;        //lc变成新的a
 21 }  
 22 /**********************四个旋转操作，每两个在一起*****************/
 23 //包含LL和LR
 24 void LeftBalance(BSTree &T)     
 25 {  //对已*T为根的二叉排序树做左平衡旋转处理
 26    BSTree lc,rd;
 27    lc = T->lchild; //lc调整左边
 28    switch(lc->bf)  
 29    {
 30      case LH://若是左边高则为LL型，只需旋转即可
 31          T->bf = lc->bf = EH; //旋转后平衡因子均为0
 32          R_Rotate(T); //LL型需要右旋转
 33          break;  
 34      case RH://若是右边高，则为LR型，需分两步调整
 35          rd = lc->rchild; //找到不确定因子rd
 36          switch(rd->bf)//对不确定因子进行讨论
 37          {
 38            case LH://左边高调整后
 39              T->bf = RH;//根节点右边变高
 40              lc->bf = EH; //lc变平衡
 41              break;
 42           case EH://rd有左右节点
 43             T->bf = lc->bf = EH; //调整后持平
 44             break;
 45           case RH://右边高
 46             T->bf = EH;//根节点平衡
 47             lc->bf = LH;//lc节点变成左边高
 48             break;  
 49          }  
 50         rd->bf=EH; //调整后rd节点一定平衡，且变成新的头节点
 51         L_Rotate(T->lchild); //1.先左旋
 52         R_Rotate(T);         //2.再右旋
 53    }
 54 }  
 55 /*************右平衡操作，包含RR和RL*******************************/
 56 void RightBalance(BSTree &T)  
 57 {
 58     //对已*T为根的二叉排序树做右平衡旋转处理
 59     //因为为LeftBalance(BSTree &T)的镜像，注释则省略
 60    BSTree lc,rd;
 61    lc = T->rchild;
 62    switch(lc->bf)
 63    {
 64     case RH://右边高，RR型
 65         T->bf = lc->bf = EH;
 66         L_Rotate(T);
 67         break;
 68     case LH://左边高，RL型，分两步旋转
 69        rd = lc->lchild;
 70        switch(rd->bf)
 71        {  
 72         case RH:
 73            T->bf = LH;
 74            lc->bf = EH;
 75            break;
 76         case LH:
 77            T->bf = EH;
 78            lc->bf = RH;
 79            break;
 80        case EH:
 81            T->bf = lc->bf = EH;
 82            break;
 83        }
 84        rd->bf = EH;
 85        R_Rotate(T->rchild); //1.先右旋
 86        L_Rotate(T);         //2.再左旋
 87    }
 88 }
 89     至于插入操作主要就是判断树是不是平衡，若不平衡是左边还是右边，对于添加的新节点改变了树的平衡了没有，改变了左边的还是右边的，然后进行相应的旋转处理。具体算法如下：
 90 int InsertAVL(BSTree &T, int key, bool &taller)  
 91 {
 92 //若在平衡二叉排序树中不存在与关键字key相等的结点，则将关键字插入树中
 93 //布尔变量taller表示树是否“长高”
 94   if(T==NULL)
 95   {
 96     T = (BSTree)malloc(sizeof(BSTNode));
 97     T->data = key;
 98     T->bf = EH;//叶子结点其平衡因子肯定为0
 99     T->lchild = T->rchild = NULL;
100     taller = 1;//树长高了
101   }
102   else
103   {
104      if(key==T->data)
105      {//如果树中已存放此关键字则不予插入
106        taller = 0;
107        return 0;
108      }
109      if(key<T->data)
110      {//关键字小于根结点则插入其左子树中
111           if(!InsertAVL(T->lchild,key,taller))
112                return 0;
113           if(taller)
114           {//如果树长高了，判断是否平衡
115             switch(T->bf)
116             {
117              case LH://若左边高，这次又加上一个左边的节点，则肯定变为2，即需要调整
118                  LeftBalance(T);//不平衡时调用左平衡函数，使左子树平衡
119                  taller = 0;
120                  break;
121              case EH://若相等，在左边加一个节点，则变为左边高
122                 T->bf = LH;
123                 taller = 1; //树变高
124                 break;
125              case RH://若右边高，在左边加一个节点，则持平
126                 T->bf = EH;
127                 taller = 0;
128                break;
129             }
130           }
131      }
132      else
133      {//插入右子树中
134         if(!InsertAVL(T->rchild,key,taller))
135           return 0;
136         if(taller)
137         {
138           switch(T->bf)
139           {
140             case LH://同理，本来左边高，在右边加一个节点则持平
141                 T->bf = EH;
142                 taller = 0;
143                 break;
144             case EH://右边变高
145                 T->bf = RH;
146                 taller = 1;
147                 break;
148             case RH://右边不平衡了，需要调整
149                 RightBalance(T);
150                 taller = 0;
151                 break;
152           }
153         }
154      }
155   }
156         return 1;
157 }  

本文来自电脑杂谈，转载请注明本文网址：
http://www.pc-fly.com/a/jisuanjixue/article-121392-4.html