(Remove Function) AVL Tree | Adelson-Velskii and Landis Tree In Data Structure Using C++

on

Data Structure Using C++

Tree Data Structure

AVL (Adelson-Velskii and Landis) Tree

(Remove Function) AVL Tree | Adelson-Velskii and Landis Tree

#include "AVLNode.cpp"
int max(int a, int b);
int height(AVLNode* N);
void fixHeight(AVLNode* N);
AVLNode *rightRotate(AVLNode *k2);
AVLNode *leftRotate(AVLNode *k1);
int getBalance(AVLNode *N);
AVLNode* insert(AVLNode* node, int info);
void inOrder(AVLNode *root);
AVLNode* findMin(AVLNode* node);
AVLNode* deleteNode(AVLNode* root, int key);
int main()
{
  AVLNode *root = NULL;
 
  /* Constructing tree given in the above figure */
    root = insert(root, 17);
    root = insert(root, 12);
    root = insert(root, 21);
    root = insert(root, 10);
    root = insert(root, 15);
    root = insert(root, 19);
    root = insert(root, 27);
    root = insert(root, 14);
    root = insert(root, 16);
    
    inOrder(root);
    cout<<endl; 
    root = deleteNode(root, 10);
 
    inOrder(root); 
    cout<<endl; 
    root = deleteNode(root, 15); 
 
    inOrder(root); 
    cout<<endl;
    root = deleteNode(root, 19);
 
    inOrder(root); 
    cout<<endl; 
    root = deleteNode(root, 12);
    inOrder(root);
 
    return 0;
}
AVLNode* findMin(AVLNode* node)
{
    if( node == NULL ) 
        return NULL;
    if( node->getLeft() == NULL ) 
        return node; // this is it.
    return findMin( node->getLeft() );
}
AVLNode* deleteNode(AVLNode* root, int info)
{
    if (root == NULL)
        return root;
    if ( info < root->getInfo() )
        root->setLeft(deleteNode(root->getLeft(), info)) ;
    else if( info > root->getInfo() )
        root->setRight(deleteNode(root->getRight(), info));
    else
    {
        // node with only one child or no child
        if( (root->getLeft() == NULL) || (root->getRight() == NULL) )
        {
            AVLNode *temp = root->getLeft() ? root->getLeft() : root->getRight();
 
            // No child case
            if (temp == NULL)
            {
                temp = root;
                root = NULL;
            }
            else // One child case
             *root = *temp; // Copy the contents of
                            // the non-empty child
        }
        else
        {
            // node with two children: Get the inorder
            // successor (smallest in the right subtree)
            AVLNode* temp = findMin(root->getRight());
 
            // Copy the inorder successor's data to this node
            root->setInfo(temp->getInfo()) ;
 
            // Delete the inorder successor
            root->setRight(deleteNode(root->getRight(), temp->getInfo())) ;
        }
    }
 
    // If the tree had only one node then return
    if (root == NULL)
      return root;
 
    // STEP 2: UPDATE HEIGHT OF THE CURRENT NODE
    fixHeight(root);
 
    // STEP 3: GET THE BALANCE FACTOR OF THIS NODE (to
    // check whether this node became unbalanced)
    int balance = getBalance(root);
 
    // If this node becomes unbalanced, then there are 4 cases
 
    // Left Left Case
    if (balance > 1 && getBalance(root->getLeft()) >= 0)
    {
        return rightRotate(root);
 }
    // Left Right Case
    if (balance > 1 && getBalance(root->getLeft()) < 0)
    {
        root->setLeft(leftRotate(root->getLeft()));
        return rightRotate(root);
    }
    // Right Right Case
    if (balance < -1 && getBalance(root->getRight()) <= 0)
    {
     return leftRotate(root);
 } 
    // Right Left Case
    if (balance < -1 && getBalance(root->getRight()) > 0)
    {
        root->setRight(rightRotate(root->getRight())) ;
        return leftRotate(root);
    }
 
    return root;
}
int height(AVLNode *N)
{
    if (N == NULL)
        return 0;
    return N->getHeight();
} 
void fixHeight(AVLNode* N){ 
    N->setHeight(max(height(N->getLeft()), height(N->getRight()))+1);
}
int max(int a, int b)
{
    return (a > b)? a : b;
}
AVLNode *rightRotate(AVLNode *k2)
{
    AVLNode *k1 = k2->getLeft();
    AVLNode *Y = k1->getRight();
 
    k1->setRight(k2);
    k2->setLeft(Y);
 
  fixHeight(k2);
  fixHeight(k1);
 
    return k1;
}
AVLNode *leftRotate(AVLNode *k1)
{
    AVLNode *k2 = k1->getRight();
    AVLNode *Y = k2->getLeft();
 
    k2->setLeft(k1);
    k1->setRight(Y);
 
  fixHeight(k1);
  fixHeight(k2);
 
    return k2;
}
int getBalance(AVLNode *N)
{
    if (N == NULL)
        return 0;
    return height(N->getLeft()) - height(N->getRight());
}
void inOrder(AVLNode *root)
{
    if(root != NULL)
    {
        inOrder(root->getLeft());
        cout<<root->getInfo()<<"\t";
        inOrder(root->getRight());
    }
}

Let me know in the comment section if you have any question.

Previous Post:
(Insert Function) AVL Tree | Adelson-Velskii and Landis Tree In Data Structure Using C++

Comments

Post a Comment