树算法笔记专题

1. AVL tree模板

   struct node{
       int data;
       int height;
       node* lchild;
       node* rchild;
   };
   
   node* newNode(int val){
       node* root = new node;
       root->data = val;
       root->height = 1;
       root->lchild = NULL;
       root->rchild = NULL;
       return root;
   }
   int getHeight(node* root){
       if (root == 0){
           return 0;
       }
       return root->height;
   }
   
   int getBalance(node* root){
       return getHeight(root->lchild) - getHeight(root->rchild);
   }
   
   void updataHeight(node* root){
       root->height = max(getHeight(root->lchild), getHeight(root->rchild)) + 1;
   }
   
   void L(node* &root){
       node* temp = root->rchild;
       root->rchild = temp->lchild;
       temp->lchild = root;
       updataHeight(root);
       updataHeight(temp);
       temp = root;
   }
   
   void R(node* &root){
       node* temp = root->lchild;
       root->lchild = temp->rchild;
       temp->rchild = root;
       updataHeight(root);
       updataHeight(temp);
       temp = root;
   }
   
   void insert(node* &root, int x){
       if (root == NULL){
           root = newNode(x);
           return;
       }
       if (x < root->data){
           insert(root->lchild, x);
           updataHeight(root);
           if(getBalance(root) == 2){
               if(getBalance(root->lchild) == 1){
                   R(root);
               }
               else if(getBalance(root->lchild) == -1){
                   L(root->lchild);
                   R(root);
               }
           }
       }
       else{
           insert(root->rchild, x);
           updataHeight(root);
           if(getBalance(root) == -2){
               if(getBalance(root->rchild) == -1){
                   L(root);
               }
               else if(getBalance(root->rchild) == 1){
                   R(root->rchild);
                   L(root);
               }
           }
       }
   }

赏

谢谢你请我吃糖果

支付宝