平衡二叉树——Balance Binary Sort Tree 设计与实现

骑猪看日落 2022-01-06 15:21 151阅读 0赞

平衡二叉树（Balanced Binary Tree）又被称为AVL树

平衡二叉树（Balanced Binary Tree）又被称为AVL树（有别于AVL算法），且具有以下性质：

它是一棵空树 或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

构造与调整方法

平衡二叉树的常用算法有红黑树、AVL、Treap、伸展树等。

本程序采用AVL方案进行平衡树的构建。

在AVL中任何节点的两个儿子子树的高度最大差别为一，所以它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下都是O（log n）。

增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。由于这个性质，导致整个树的代价要比红黑树大，所以在STL的一些地方，如map/set都是使用红黑树实现的，所以也就知道了map/set这两个模板的各种代价了。

平衡的树，大多数操作——增删改查，都是O(logn)的，其中红黑树对比AVL树的优势也仅仅在于插入删除这两个操作红黑树会有一个常数级别的优势。

下面是实现的代码，转载请注明出处。

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #define LENGTH 5
      2 #include <iostream>
      3 #include <vector>
      4 #include <windows.h>
      5 #include <cmath>
      6 using namespace std;
      7 class Balanced_Binary_Tree{
      8 private:
      9     int infor;
     10     int balance_index;
     11     Balanced_Binary_Tree *left;
     12     Balanced_Binary_Tree *right;
     13     Balanced_Binary_Tree *father;
     14 public:
     15     friend int get_height(Balanced_Binary_Tree*);
     16     friend void print_tree(Balanced_Binary_Tree*);
     17     friend Balanced_Binary_Tree* exist(int);
     18     friend Balanced_Binary_Tree* get_max(Balanced_Binary_Tree*);
     19     friend Balanced_Binary_Tree* get_min(Balanced_Binary_Tree*);
     20     friend Balanced_Binary_Tree* search(int);
     21     friend void insert_node(int);
     22     friend void delete_node(int);
     23     friend void rotate(Balanced_Binary_Tree*);
     24     friend int max_distance(Balanced_Binary_Tree*);// a function for count the max distance between any two node in a BT
     25     friend void Balanced_Binary_Tree_Test();
     26     Balanced_Binary_Tree(int a){
     27         infor=a;
     28         left=NULL;
     29         right=NULL;
     30         father=NULL;
     31         Set_Balance_Index();
     32     }
     33     Balanced_Binary_Tree(){
     34         left=NULL;
     35         right=NULL;
     36         father=NULL;
     37         infor = -1;
     38         Set_Balance_Index();
     39     }
     40     void Set_Balance_Index(){
     41         balance_index = get_height(left) - get_height(right);
     42     }
     43     ~Balanced_Binary_Tree(){cout<<"Delete    "<<infor<<"    !"<<endl;}
     44     void print(){
     45         cout<<infor;
     46     }
     47 };
     48 static Balanced_Binary_Tree* Start = new Balanced_Binary_Tree(-2147483648);
     49 int get_height(Balanced_Binary_Tree* t)
     50 {
     51     if(t == NULL)
     52         return 0;
     53     else{
     54         int leftH=get_height((*t).left);
     55         int rightH=get_height((*t).right);
     56         return (leftH > rightH)?(leftH+1):(rightH+1);
     57     }
     58 }
     59 //返回这个节点的高度
     60 int max_distance(Balanced_Binary_Tree* root){
     61     if(root == NULL)return 0;
     62     else{
     63         int distance;
     64         distance = get_height((*root).left)+get_height((*root).right);
     65         return distance;
     66     }
     67 }
     68 //返回整个树的最大距离
     69 Balanced_Binary_Tree* exist(int a){
     70     if((*Start).right == NULL)
     71     {            
     72         return NULL;
     73     }
     74     else{
     75         Balanced_Binary_Tree *t = new Balanced_Binary_Tree();
     76         t = (*Start).right;
     77         while(t!=NULL){
     78             if(a<(*t).infor){
     79                 t=(*t).left;
     80             }
     81             else if(a>(*t).infor){
     82                 t=(*t).right;
     83             }
     84             else if(a == (*t).infor)
     85                 break;
     86         }//while
     87         return t;
     88     }//else
     89 }//
     90 //exist 判断一个数据是否在排序树上，找到返回引用，未找到返回NULL；这是用在对数据进行判定的
     91 Balanced_Binary_Tree* search(int a){
     92     if(exist(a)==NULL)
     93     {
     94         if((*Start).right == NULL)
     95         {            
     96             return Start;
     97         }
     98         else{
     99             Balanced_Binary_Tree *t = new Balanced_Binary_Tree();
    100             Balanced_Binary_Tree *q = new Balanced_Binary_Tree();
    101             t = (*Start).right;
    102             while(t!=NULL){
    103                 q = t;
    104                 if(a<(*t).infor){
    105                     t=(*t).left;
    106                 }
    107                 else{
    108                     t=(*t).right;
    109                 }
    110             }//while
    111             return q;
    112         }//else
    113     }//if(!exist a)
    114     else return NULL;
    115 }//
    116 //search 查找一个数据应该插入的位置；不存在树时候返回头结点，存在树的时候，返回最后的结点的引用；这用于处理对数据插入过程中的插入位置判断。
    117 void insert_node(int a)
    118 {
    119     if(exist(a)==NULL)
    120     {
    121         Balanced_Binary_Tree *n = new Balanced_Binary_Tree(a);
    122         Balanced_Binary_Tree *t;
    123         t = search(a);
    124         (*n).father = t;
    125         if((*t).infor>a)
    126         {    (*t).left=n;    }
    127         else 
    128         {    (*t).right=n;    }
    129         // 首先将这个节点插入树上
    130         while(t!=Start){
    131             t->Set_Balance_Index();
    132             if(abs(t->balance_index)>=2)
    133                 break;
    134             t = t->father;
    135         }
    136         //判断这个树是不是平衡的
    137         if(t!=Start){
    138             rotate(t);
    139         }//这个子树不平衡
    140         //if(t!=Start)
    141     }//if(exist(a)==NULL)
    142 }
    143 //插入数据，如果数据不存在，就插入
    144 //当平衡的二叉排序树因为插入节点而失去平衡的时候，仅仅需要对最小不平衡子树进行平衡旋转处理。
    145 //因为经过旋转处理的子树深度与之前相同，因此不影响插入路径上所有祖先节点的平衡度。
    146 void rotate(Balanced_Binary_Tree *t){
    147             if(t->balance_index == 2){
    148                 t->left->Set_Balance_Index();
    149                 if(t->left->balance_index == 1){
    150                     Balanced_Binary_Tree *temp;
    151                     temp = t->left;
    152                     if((t->father->infor)>(t->infor))
    153                         t->father->left = temp;                    
    154                     else 
    155                         t->father->right = temp;
    156                     temp->father = t->father;
    157                     t->left = temp->right;
    158                     if(temp->right != NULL){
    159                         temp->right->father = t;                    
    160                     }
    161                     temp->right = t;
    162                     t->father = temp;    
    163                 }//if(t->left->balance_index == 1)
    164                 else{
    165                     Balanced_Binary_Tree *A,*B,*C;
    166                     A = t;
    167                     B = t->left;
    168                     C = B->right;
    169                     if((A->father->infor)>(A->infor))
    170                         A->father->left = C;                    
    171                     else 
    172                         A->father->right = C;
    173                     C->father = A->father;
    174 
    175                     A->father = C;
    176                     B->father = C;
    177 
    178                     A->left = C->right;
    179                     if(C->right != NULL)
    180                         C->right->father = A;
    181 
    182                     B->right = C->left;
    183                     if(C->left != NULL)
    184                         C->left->father = B;
    185 
    186                     C->right = A;
    187                     C->left = B;                    
    188 
    189                 }//if(t->left->balance_index == -1)
    190             }//if(t->balance_index == 2)
    191             else {
    192                 if(t->right->balance_index == -1){
    193                     Balanced_Binary_Tree *temp;
    194                     temp = t->right;
    195                     if((t->father->infor)>(t->infor))
    196                         t->father->left = temp;                    
    197                     else 
    198                         t->father->right = temp;
    199                     temp->father = t->father;
    200                     t->right = temp->left;
    201                     if(temp->left != NULL){
    202                         temp->left->father = t;
    203                     }
    204                     temp->left = t;
    205                     t->father = temp;
    206                 }//if(t->right->balance_index == -1)
    207                 else{
    208                     Balanced_Binary_Tree *A,*B,*C;
    209                     A = t;
    210                     B = t->right;
    211                     C = B->left;
    212                     if((A->father->infor)>(A->infor))
    213                         A->father->left = C;                    
    214                     else 
    215                         A->father->right = C;
    216                     C->father = A->father;
    217                     
    218                     A->father = C;
    219                     B->father = C;
    220 
    221                     A->right = C->left;
    222                     if(C->left != NULL)
    223                         C->left->father = A;
    224 
    225                     B->left = C->right;
    226                     if(C->right != NULL)
    227                         C->right->father = B;
    228 
    229                     C->right = B;
    230                     C->left = A;
    231                 }//if(t->right->balance_index == 1)
    232             }
    233 }
    234 
    235 
    236 Balanced_Binary_Tree* get_min(Balanced_Binary_Tree* a)
    237 {
    238     Balanced_Binary_Tree *t;
    239     t=a;
    240     while((*a).left!=NULL){
    241         t=a;
    242         a=(*a).left;
    243     }
    244     return t;
    245 }
    246 //找到最左节点
    247 Balanced_Binary_Tree* get_max(Balanced_Binary_Tree* a)
    248 {
    249     Balanced_Binary_Tree *t;
    250     while((*a).right!=NULL){
    251         t=a;
    252         a=(*a).right;
    253     }
    254     return t;
    255 }
    256 //找到最右节点
    257 void delete_node(int a){
    258     if(exist(a)!=NULL)
    259     {
    260         Balanced_Binary_Tree *t=exist(a);
    261         if((*t).left==NULL&&(*t).right==NULL)
    262         {
    263             if((*(*t).father).infor>(*t).infor){
    264                 (*(*t).father).left = NULL;
    265             }
    266             else (*(*t).father).right = NULL;
    267         }
    268         //删除的节点无子节点
    269         else if((*t).left==NULL||(*t).right==NULL)
    270         {
    271             
    272             if((*t).left == NULL)
    273             {
    274                 if((*(*t).father).infor>(*t).infor){
    275                     (*(*t).father).left = (*t).right;
    276                 }
    277                 else (*(*t).father).right = (*t).right;
    278                 (*(*t).right).father = (*t).father;
    279             }
    280             else{
    281                 if((*(*t).father).infor>(*t).infor){
    282                     (*(*t).father).left = (*t).left;
    283                 }
    284                 else (*(*t).father).right = (*t).left;
    285                 (*(*t).left).father = (*t).father;
    286             }
    287         }
    288         //删除的节点有一个子节点
    289         else{
    290             if((*(*t).father).infor>(*t).infor){
    291                     (*(*t).father).left = (*t).right;
    292                     (*(*t).left).father = get_min((*t).right);
    293                     Balanced_Binary_Tree *a = get_min((*t).right);
    294                     (*a).left = (*t).left;
    295                     (*(*t).right).father = (*t).father;
    296                 }
    297             else {
    298                 (*(*t).father).right = (*t).right;
    299                 (*(*t).left).father = get_min((*t).right);
    300                 Balanced_Binary_Tree *a = get_min((*t).right);
    301                 (*a).left = (*t).left;
    302                 (*(*t).right).father = (*t).father;
    303             }
    304         }
    305         //删除的节点有两个子节点
    306         Balanced_Binary_Tree *delete_node = t;
    307         while(t!=Start){
    308             t->Set_Balance_Index();
    309             if(abs(t->balance_index)>=2)
    310                 break;
    311             t = t->father;
    312         }
    313         if(t!=Start){
    314             rotate(t);
    315         }
    316         (*delete_node).left =NULL;
    317         (*delete_node).right =NULL;
    318         (*delete_node).father=NULL;
    319         delete delete_node;
    320         //delete t;
    321     }
    322 }
    323 //删除数据，如果数据存在，就删除
    324 void print_void(int k){
    325     while(k--)cout<<"  ";
    326 }
    327 //打印k个制表符
    328 void print_tree(Balanced_Binary_Tree* t){
    329     Balanced_Binary_Tree* temp = t;
    330     vector<Balanced_Binary_Tree*> list;
    331     list.push_back(temp);
    332     int k = get_height(t);
    333     while(k--){
    334         int print_length = pow((double)2,(double)k);
    335         int length = list.size();
    336         vector<Balanced_Binary_Tree*>::iterator iter;
    337         iter = list.begin();
    338         int number_son = list.size();
    339         print_void(print_length);
    340         for(int j=0;j<number_son;j++){
    341             if((*iter)->infor == -1)
    342                 cout<<"*";
    343             else 
    344                 (*iter)->print();
    345             if((*iter)->left == NULL)    {
    346                 t = new Balanced_Binary_Tree();
    347                 list.push_back(t);
    348                 iter = list.begin()+j;
    349             }
    350             else {
    351                 list.push_back((*iter)->left);
    352                 iter = list.begin()+j;
    353             }
    354             if((*iter)->right == NULL)    {
    355                 t = new Balanced_Binary_Tree();
    356                 list.push_back(t);
    357                 iter = list.begin()+j;
    358             }
    359             else {
    360                 list.push_back((*iter)->right);
    361                 iter = list.begin()+j;
    362             }
    363             iter++;
    364             print_void(print_length*2);
    365         }
    366         list.erase(list.begin(),list.begin()+number_son);
    367         cout<<endl;
    368     }
    369 }
    370 
    371 void Balanced_Binary_Tree_Test()
    372 {
    373     
    374     int test[LENGTH] = {
         1,3,5,4,2};
    375     for(int a=0;a<LENGTH;a++){
    376         insert_node(test[a]);
    377     }
    378     
    379 
    380     //TEST PART
    381     //int a;
    382     //while(cin>>a)insert_node(a);
    383     //TEST PART
    384     char c;
    385     int i;
    386     cout<<"AVL Tree!"<<endl;
    387     cout<<"d——delete a node;    "<<endl;
    388     cout<<"g——get the node's information;    "<<endl;
    389     cout<<"i——insert a node;    "<<endl;
    390     cout<<"l——get max length of the sub_tree;"<<endl;
    391     cout<<"c——clear the screen;"<<endl;
    392     cout<<"else——quit the test;"<<endl;
    393     while(cin>>c>>i){
    394         cout<<"AVL Tree!"<<endl;
    395         cout<<c<<" "<<i<<endl;
    396         cout<<"d——delete a node;    "<<endl;
    397         cout<<"g——get the node's information;    "<<endl;
    398         cout<<"i——insert a node;    "<<endl;
    399         cout<<"l——get max length of the sub_tree;"<<endl;
    400         cout<<"c——clear the screen;"<<endl;
    401         cout<<"else——quit the test;"<<endl;
    402         switch(c){
    403         case 'c':{
    404                 system("cls");
    405                 break;
    406                      }
    407         case 'g':
    408             {
    409                 Balanced_Binary_Tree *t = new Balanced_Binary_Tree();
    410                 t = exist(i);
    411                 if(t==NULL){
    412                     cout<<"The node "<<i<<" do not exist!"<<endl;
    413                         }
    414                 print_tree(Start->right);
    415                 break;
    416             }
    417         case 'd':
    418             {
    419                 Balanced_Binary_Tree *t = new Balanced_Binary_Tree();
    420                 t = exist(i);
    421                 if(t==NULL){
    422                     cout<<"The node "<<i<<" do not exist!"<<endl;
    423                 }
    424                 else{
    425                     delete_node((*t).infor);
    426                 }
    427                 print_tree(Start->right);
    428                 break;
    429             }
    430         case 'i':
    431             {
    432                 Balanced_Binary_Tree *t = new Balanced_Binary_Tree();
    433                 t = exist(i);
    434                 if(t==NULL){
    435                     cout<<"The node "<<i<<" do not exist!"<<endl;
    436                     insert_node(i);
    437                 }
    438                 else cout<<"The node "<<i<<" already exist!"<<endl;
    439                 print_tree(Start->right);
    440                 break;
    441             }
    442         case 'l':
    443             {
    444                 Balanced_Binary_Tree *t = new Balanced_Binary_Tree();
    445                 t = exist(i);
    446                 if(t==NULL){
    447                     cout<<"The node "<<i<<" do not exist!"<<endl;
    448                 }
    449                 else{
    450                     int l = max_distance(t);
    451                     print_tree(Start->right);
    452                     cout<<"max distance of sub tree "<<i<<" is " <<l<<endl;
    453                 }
    454                 break;
    455             }
    456         default:break;
    457         }
    458     }
    459 }
    460 
    461 
    462 int main(void)
    463 {
    464     Balanced_Binary_Tree_Test();
    465     return 0; 
    466 }

运行示例：

d——delete a node;  
g——get the node's information;  
i——insert a node;  
l——get max length of the sub\_tree;  
c——clear the screen;  
else——quit the test;  
The node 45 do not exist!  
                3  
        1                32  
    \*        2        5        33  
  \*    \*    \*    \*    4    12    \*    45  
i 66  
AVL Tree!  
i 66  
d——delete a node;  
g——get the node's information;  
i——insert a node;  
l——get max length of the sub\_tree;  
c——clear the screen;  
else——quit the test;  
The node 66 do not exist!  
                3  
        1                32  
    \*        2        5        45  
  \*    \*    \*    \*    4    12    33    66  
i 80  
AVL Tree!  
i 80  
d——delete a node;  
g——get the node's information;  
i——insert a node;  
l——get max length of the sub\_tree;  
c——clear the screen;  
else——quit the test;  
The node 80 do not exist!  
                32  
        3                45  
    1        5        33        66  
  \*    2    4    12    \*    \*    \*    80

转载于:https://www.cnblogs.com/wangbiaoneu/archive/2013/04/25/AVL\_Tree.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20211227/9a9f497c4bf14545a8159b16cf0b625d.png