mardi 4 août 2020

AVL Tree Insertion and Rotation

While performing a rotation in an unbalanced binary search tree, we need to rotate the parent node[single rotation] if the imbalance is being caused in right-right or left-left. so the parent node can be easily accessed as it is being passed to the function.

 void add_node(T data,Node<T>* &node){
   if(this->root==nullptr){
     Node<T>* new_node= new Node<T>(data);
     this->root=new_node;
     
   }
   else{
     if(data<node->m_data){
       if(node->m_left!=nullptr){
         add_node(data,node->m_left);
     
       }else{
          
          Node<T>* new_node= new Node<T>(data);
          node->m_left=new_node;
          rebalance(node);
       }
     }
     if(data>node->m_data){
       if(node->m_right!=nullptr){
        add_node(data,node->m_right);
        
       }else{
          Node<T>* new_node= new Node<T>(data);
          node->m_right=new_node;
          
          rebalance(node);
       }
       
     }
   }
 }

But how do we access the ancestor node if we need to perform an LR or RL rotation?

Node<T>* rebalance(Node<T>* &node){
      int bal_fact=balance_factor(node);
       if(bal_fact>1){
           if(balance_factor(node->m_left)>0){
             node=ll_rotate(node);
           }else{
             node=lr_rotate(node);
           }
       }
       if(bal_fact<-1){
          if(balance_factor(node->m_right)>0){
             node=rl_rotate(node);
           }else{
             node=rr_rotate(node);
           }
       }
       return node;
     }

Aucun commentaire:

Enregistrer un commentaire