平衡二叉树---》插入、删除

        平衡二叉树(Balancedbinary tree)是由阿德尔森-维尔斯和兰迪斯(Adelson-Velskiiand Landis)于1962年首先提出的，所以又称为AVL树。

定义：平衡二叉树或为空树,或为如下性质的二叉排序树:

 （1）左右子树深度之差的绝对值不超过1;

 （2）左右子树仍然为平衡二叉树.

        平衡二叉树可以避免排序二叉树深度上的极度恶化，使树的高度维持在O（logn）来提高检索效率。

平衡二叉树算法思想

      若向平衡二叉树中插入一个新结点后破坏了平衡二叉树的平衡性。首先要找出插入新结点后失去平衡的最小子树根结点的指针。然后再调整这个子树中有关结点之间的链接关系，使之成为新的平衡子树。当失去平衡的最小子树被调整为平衡子树后，原有其他所有不平衡子树无需调整，整个二叉排序树就又成为一棵平衡二叉树。失去平衡的最小子树是指以离插入结点最近，且平衡因子绝对值大于1的结点作为根的子树 。

  要维持二叉树的平衡需要使用左旋和右旋操作。

   右旋（如图1）：以A为中心顺时针旋转。实际就是把B移到A的位置，把B的右子树变为A的左子树，在把A作为B的右子树。在平衡二叉树中以平衡因子为2的节点进行右旋。

                        

                                     

                                          右旋前                                                            右旋后

右旋代码：

[cpp] view plaincopy

1. <span style="font-size:18px;">//右旋  
2.     void RotateRight(tNode** root)  
3.     {  
4.         tNode* p=*root;//图中相当于A  
5.         tNode* rc=p->pleft;//相当于B  
6.         tNode* rrc=rc->pright;//相当于D  
7.         p->pleft=rrc;  
8.         rc->pright=p;  
9.         *root=rc;  
10.     }</span>  

左旋（如图）：以A为中心逆时针旋转，实际就是：把B移到A的位置，把B的左子树作为A的右子树，再把A变成B的左子树。在平衡树种以平衡因子为-2的节点为中心做左旋操作。

                                         

                                                     

                                                             左旋前                                                      左旋后

左旋代码：

[cpp] view plaincopy

1. //左旋  
2. void RotateLeft(tNode** root)  
3. {  
4.     tNode * p=*root;//相当于A  
5.     tNode* lc=p->pright;//相当于B  
6.     tNode* llc=lc->pleft;//相当于C  
7.     p->pright=llc;  
8.     lc->pleft=p;  
9.     *root=lc;  
10. }  

插入新的节点：

1、LL的情况：

       由于在A的左孩子B的左子树上插入结点F，使A的平衡因子由1增至2而失去平衡。故需进行一次顺时针旋转操作。 即将A的左孩子B向右上旋转代替A作为根结点，A向右下旋转成为B的右子树的根结点。而原来B的右子树则变成A的左子树。

                        

2、LR情况：

       由于在A的左孩子B的右子数上插入结点F，使A的平衡因子由1增至2而失去平衡。故需进行两次旋转操作（先逆时针，后顺时针）。即先将A结点的左孩子B的右子树的根结点D向左上旋转提升到B结点的位置，然后再把该D结点向右上旋转提升到A结点的位置。即先使之成为LL型，再按LL型处理。

                          

左平衡代码：

[cpp] view plaincopy

1. <span style="font-size:18px;">void AVLTree::LeftBalance(tNode** root)  
2. {  
3.     tNode* p=*root;  
4.     tNode* c=p->pleft;  
5.     tNode* rc=c->pright;  
6.     switch(c->bf)  
7.     {  
8.         //LL情况  
9.     case 1:  
10.         {  
11.             p->bf=c->bf=0;  
12.             RotateRight(root);  
13.             break;  
14.         }  
15.         //LR情况  
16.     case -1:  
17.         {  
18.             switch(rc->bf)  
19.             {  
20.             case 1:  
21.                  {  
22.                      c->bf=0;  
23.                      p->bf=-1;  
24.                      break;  
25.                  }  
26.             case 0:  
27.                  {  
28.                      c->bf=0;  
29.                      p->bf=0;  
30.                      break;  
31.                  }  
32.             case -1:  
33.                 {  
34.                     c->bf=1;  
35.                     p->bf=0;  
36.                     break;  
37.                 }  
38.             }  
39.             rc->bf=0;  
40.             RotateLeft(&c);  
41.             RotateRight(root);  
42.                      break;  
43.         }  
44.     }  
45. }</span>  

左平衡操作在处理LR情况时又根据rc节点也就是图中D的平衡因子分三种情况来确定平衡后图中B和A的平衡因子。其他的平衡因子不变。

怎么来确定A和B左平衡操作后的平衡因子？

假设在LR情况下，新的节点插入后C的平衡因子是1，那么设C的左子树的高度为h则右子树为h-1，B的右子树为h+1，B的平衡因子是-1，则它左子树高度为h，A左子树高度为h+2，它的平衡因子为2，则它的右子树高度为h。在平衡化后，A的左子树以C为根，右子树为D，所以A的平衡因子为0.而B的右子树以A为根，则它的平衡因子为-1.

       在C的平衡因子为0，-1的情况下也可以用上面方法推出，平衡后A和B的平衡因子。

                                                      

3 RR情况：

       由于在A的右孩子C 的右子树上插入结点F，使A的平衡因子由-1减至-2而失去平衡。故需进行一次逆时针旋转操作。即将A的右孩子C向左上旋转代替A作为根结点，A向左下旋转成为C的左子树的根结点。而原来C的左子树则变成A的右子树。

                                      

4、RL情况：

        由于在A的右孩子C的左子树上插入结点F，使A的平衡因子由-1减至-2而失去平衡。故需进行两次旋转操作（先顺时针，后逆时针），即先将A结点的右孩子C的左子树。

                                

右平衡代码：

[cpp] view plaincopy

1. <span style="font-size:18px;">void AVLTree::RightBalance(tNode** root)  
2. {  
3.     tNode* p=*root;  
4.     tNode* c=p->pright;  
5.     tNode* lc=c->pleft;  
6.     switch(c->bf)  
7.     {  
8.         //RR情况  
9.     case -1:  
10.         {  
11.             p->bf=-1;  
12.             c->bf=0;  
13.             RotateLeft(root);  
14.             break;  
15.         }  
16.         //RL情况  
17.     case 1:  
18.         {  
19.             switch(lc->bf)  
20.             {  
21.             case 1:  
22.                 {  
23.                     p->bf=0;  
24.                     c->bf=-1;  
25.                     break;  
26.                 }  
27.             case 0:  
28.                 {  
29.                     p->bf=0;  
30.                     c->bf=0;  
31.                     break;  
32.                 }  
33.             case -1:  
34.                 {  
35.                     p->bf=1;  
36.                     c->bf=0;  
37.                     break;  
38.                 }  
39.                 lc->bf=0;  
40.                 RotateRight(&c);  
41.                 RotateLeft(root);  
42.                 break;  
43.             }  
44.         }  
45.     }  
46. }</span>  

右平衡在RL的情况下平衡因子的变化也分三种情况。因子推断与上面相同。

左旋，右旋，左平衡，右平衡都齐全了。那么插入新节点操作也只是把他们穿针引线的连起来而已。

          插入新的节点代码 ：

插入新节点以递归的方式。在插入新节点成功后回溯更新和维护树的平衡性。

[cpp] view plaincopy

1. <span style="font-size:18px;">int AVLTree::Insert(tNode** root,int key,int& taller)  
2. {  
3.     if(*root==NULL)  
4.     {  
5.         tNode* newNode=new tNode(key);  
6.         taller=1;  
7.         *root=newNode;  
8.         return 1;  
9.     }  
10.     else if((*root)->mvalue==key)  
11.     {  
12.         return 0;  
13.     }  
14.     else if(key<(*root)->mvalue)  
15.     {  
16.         if(Insert(&((*root)->pleft),key,taller))  
17.         {  
18.             return 1;  
19.         }  
20.         if(taller)  
21.         {  
22.             switch((*root)->bf)  
23.             {  
24.             case 1:  
25.                 LeftBalance(root);  
26.                 taller=0;  
27.                 break;  
28.             case 0:  
29.                 (*root)->bf=1;  
30.                 taller=1;  
31.                 break;  
32.             case -1:  
33.                 (*root)->bf=0;  
34.                 taller=0;  
35.                 break;  
36.             }  
37.         }  
38.         return 0;  
39.     }  
40.     else if(key>(*root)->mvalue)  
41.     {  
42.         if(Insert(&((*root)->pright),key,taller))  
43.         {  
44.             return 1;  
45.         }  
46.         if(taller)  
47.         {  
48.             switch((*root)->bf)  
49.             {  
50.             case -1:  
51.                 RightBalance(root);  
52.                 taller=0;  
53.                 break;  
54.             case 0:  
55.                 (*root)->bf=-1;  
56.                 taller=1;  
57.                 break;  
58.             case 1:  
59.                 (*root)->bf=0;  
60.                 taller=0;  
61.                 break;  
62.             }  
63.               
64.         }  
65.         return 0;  
66.     }  
67. }</span>  

         删除节点操作：

      删除节点操作比插入稍微复杂。插入只需要一次平衡操作即可恢复树的平衡性。而删除节点在删除后，可能需要多次操作才能恢复树的平衡。

      要先找到最底部不平衡的子树，将其恢复平衡。在根据情况判断需不需要继续沿着子树向上恢复平衡。

     为了找到最底部不平衡的子树，将删除操作迁移到最底部的子树上进行。

     删除节点的代码为：

[cpp] view plaincopy

1. //返回1表示要删除的点在最底部子树上，删除成功。返回0表示将删除节点向下迁移。  
2. int AVLTree::deleteNode(tNode* p,tNode* pp,int& key,bool& shorter)  
3. {  
4.       //p表示当前节点，pp表示当前节点的父节点。key表示要删除元素的键值，  
5.        //shorter 表示是否需要平衡化操作。  
6.        if(p->pleft&&p->pright)  
7.     {  
8.         tNode* s=p->pleft;  
9.         tNode* ps=p;  
10.         while(s->pright!=NULL)  
11.         {  
12.             ps=s;  
13.             s=s->pright;  
14.         }  
15.         p->mvalue=s->mvalue;//覆盖原来要删除的点的值。  
16.         key=s->mvalue;//将关键字的值更改。  
17.         return 0;//没删除成功只是替换了要删除的元素  
18.     }  
19.     tNode* c=NULL;  
20.     if(p->pleft)  
21.         c=p->pleft;  
22.     else  
23.         c=p->pright;  
24.     if(p==pRoot)//pRoot表示树的根  
25.         pRoot=c;  
26.     else  
27.     {  
28.        if(p==pp->pleft)  
29.        {  
30.            pp->pleft=c;  
31.             
32.        }  
33.        else  
34.        {  
35.            pp->pright=c;  
36.        }  
37.     }  
38.     shorter=true;  
39.     delete p;  
40.     return 1;  
41. }  

删除节点的代码

[cpp] view plaincopy

1. int AVLTree::Delete(tNode* root,tNode* parent,int key,bool& shorter)  
2. {  
3.     if(root==NULL)  
4.     {  
5.         shorter=false;  
6.         return 0;  
7.     }  
8.     else if(root->mvalue==key)  
9.     {  
10.         if(deleteNode(root,parent,key,shorter))  
11.            return 1;  
12.     }  
13.     else if(root->mvalue>=key)  
14.     {  
15.         if(Delete(root->pleft,root,key,shorter))  
16.         {  
17.             if(shorter)  
18.             {  
19.   
20.                 switch(root->bf)  
21.                 {  
22.                 case 1:  
23.                     {  
24.                         root->bf=0;  
25.                         shorter=true;  
26.                         break;  
27.                     }  
28.                 case 0:  
29.                     {  
30.                         root->bf=-1;  
31.                         shorter=false;  
32.                         break;  
33.                     }  
34.                 case -1:  
35.                                       {  
36.                                                 <pre name="code" class="cpp">                                                if(root->pright->bf==0)  
37.                         {//为L0情况经过平衡化后子树  
38.                                                  //的高度和删除前一样   
39.                                                  shorter=false;  
40.                         }  
41.                         else  
42.                                                    //L1,L-1,平衡化后与删除前  
43.                                                    //比子树高度减小1，其父树  
44.                                                     //还需要平衡化操作  
45.                                                      shorter=true;</pre>  RightBalance(&root);break;}}}return 1;}return 0;}else if(root->mvalue<key){if(Delete(root->pright,root,key,shorter)){if(shorter){switch(root->bf){case 1:{<br>  
46. <pre name="code" class="cpp">                                                if(root->pleft->bf==0)  
47.                             shorter=false;  
48.                         else  
49.                             shorter=true;</pre><br>  
50.  LeftBalance(&root);break;}case 0:{root->bf=1;shorter=false;break;}case -1:{root->bf=0;shorter=true;break;}}}return 1;}return 0;}}  
51. <pre></pre>  
52. <p></p>  
53. <pre></pre>  
54. 平衡树类定义代码：  
55. <p></p>  
56. <p align="left" style=""><span style="font-size:24px; color:#333333"></span></p>  
57. <pre name="code" class="cpp">struct tNode  
58. {  
59.     int bf;//平衡因子  
60.     int mvalue;  
61.     tNode* pleft,  
62.         *pright,  
63.         *parent;  
64.     tNode():bf(0),mvalue(0),pleft(0),pright(0),parent(0)  
65.     {  
66.   
67.     }  
68.     tNode(int ivalue):bf(0),mvalue(ivalue),pleft(0),pright(0),parent(0)  
69.     {  
70.   
71.     }  
72. };  
73. class AVLTree  
74. {  
75. public:  
76.     AVLTree(void):pRoot(0){}  
77.     ~AVLTree(void);  
78.     //插入值为key的节点  
79.     int AVL_Insert(int key)  
80.     {  
81.         int taller;  
82.         Insert(&pRoot,key,taller);  
83.     }  
84.     //删除值为key的节点  
85.     int AVL_Delete(int key)  
86.     {  
87.         bool shorter;  
88.         Delete(pRoot,0,key,shorter);  
89.     }  
90. private:  
91.     //左旋  
92.     void RotateLeft(tNode** root)  
93.     {  
94.         tNode * p=*root;  
95.         tNode* lc=p->pright;  
96.         tNode* llc=lc->pleft;  
97.         p->pright=llc;  
98.         lc->pleft=p;  
99.         *root=lc;  
100.     }  
101.     //右旋  
102.     void RotateRight(tNode** root)  
103.     {  
104.         tNode* p=*root;  
105.         tNode* rc=p->pleft;  
106.         tNode* rrc=rc->pright;  
107.         p->pleft=rrc;  
108.         rc->pright=p;  
109.         *root=rc;  
110.     }  
111.     //左平衡  
112.     void LeftBalance(tNode** root);  
113.     //右平衡  
114.     void RightBalance(tNode** root);  
115.     //插入新的节点  
116.      int Insert(tNode** root,int key,int& taller);  
117.      //删除某个节点  
118.      int Delete(tNode* root,tNode* parent,int key,bool& shorter);  
119.      //删除节点的实际操作  
120.      int deleteNode(tNode* p,tNode* pp,int& key,bool& shorter);  
121. private:  
122.     tNode* pRoot;  
123. };       
124. </pre>  
125. <pre></pre>  
126. <p><br>  
127. </p>  
128. <p><span style="font-size:18px">程序有Bug，大概的实现方法是这样的。整了几天，还是觉得和方法和代码结合。容易被接受。总结出来也方便以后查看。</span></p>