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

AVL Tree | Adelson-Velskii and Landis Tree

#include "AVLNode.cpp"
class AVL{
 private:
  int max(int a, int b);
  void fixHeight(AVLNode* N);
  AVLNode *rightRotate(AVLNode *k2);
  AVLNode *leftRotate(AVLNode *k1);
  int getBalance(AVLNode *N);
 public:
  int height(AVLNode* N);
  AVLNode* insert(AVLNode* node, int info);
  void inOrder(AVLNode *root);
  AVLNode* findMin(AVLNode* node);
  AVLNode* deleteNode(AVLNode* root, int key);
};
AVLNode* AVL::findMin(AVLNode* node)
{
    if( node == NULL ) 
        return NULL;
    if( node->getLeft() == NULL ) 
        return node;
    return findMin( node->getLeft() );
}
AVLNode* AVL::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
             *root = *temp;
        }
        else
        {
            AVLNode* temp = findMin(root->getRight());
            root->setInfo(temp->getInfo()) ;
            root->setRight(deleteNode(root->getRight(), temp->getInfo())) ;
        }
    }
    if (root == NULL)
      return root;
    fixHeight(root);
    int balance = getBalance(root);
    // Left Left Case
    if (balance > 1 && getBalance(root->getLeft()) >= 0)
    {
    cout<<"Left Left Case:"<<info;
        return rightRotate(root);
 }
    // Left Right Case
    if (balance > 1 && getBalance(root->getLeft()) < 0)
    {
    cout<<"Left Right Case:"<<info;
        root->setLeft(leftRotate(root->getLeft()));
        return rightRotate(root);
    }
    // Right Right Case
    if (balance < -1 && getBalance(root->getRight()) <= 0)
    {
    cout<<"Right Right Case:"<<info;
     return leftRotate(root);
 } 
    // Right Left Case
    if (balance < -1 && getBalance(root->getRight()) > 0)
    {
    cout<<"Right Left Case:"<<info;
        root->setRight(rightRotate(root->getRight())) ;
        return leftRotate(root);
    }
 
    return root;
}
int AVL::height(AVLNode *N)
{
    if (N == NULL)
        return 0;
    return N->getHeight();
} 
void AVL::fixHeight(AVLNode* N){ 
    N->setHeight(max(height(N->getLeft()), height(N->getRight()))+1);
}
int AVL::max(int a, int b)
{
    return (a > b)? a : b;
}
AVLNode* AVL::rightRotate(AVLNode *k2)
{
    AVLNode *k1 = k2->getLeft();
    AVLNode *Y = k1->getRight();
 
    k1->setRight(k2);
    k2->setLeft(Y);
 
  fixHeight(k2);
  fixHeight(k1);
 
    return k1;
}
AVLNode* AVL::leftRotate(AVLNode *k1)
{
    AVLNode *k2 = k1->getRight();
    AVLNode *Y = k2->getLeft();
 
    k2->setLeft(k1);
    k1->setRight(Y);
 
  fixHeight(k1);
  fixHeight(k2);
 
    return k2;
}
int AVL::getBalance(AVLNode *N)
{
    if (N == NULL)
        return 0;
    return height(N->getLeft()) - height(N->getRight());
}
AVLNode* AVL::insert(AVLNode* node, int info)
{
    if (node == NULL)
        return(new AVLNode(info));
 
    if (info < node->getInfo())
        node->setLeft(insert(node->getLeft(), info));
    else if (info > node->getInfo())
        node->setRight(insert(node->getRight(), info));
    else
        return node;
    fixHeight(node);
    int balance = getBalance(node);
    // Left Left Case
    if (balance > 1 && info < node->getLeft()->getInfo())
        return rightRotate(node);
 
    // Right Right Case
    if (balance < -1 && info > node->getRight()->getInfo())
        return leftRotate(node);
    // Left Right Case
    if (balance > 1 && info > node->getLeft()->getInfo())
    {
        node->setLeft(leftRotate(node->getLeft()));
        return rightRotate(node);
    }
    // Right Left Case
    if (balance < -1 && info < node->getRight()->getInfo())
    {
        node->setRight(rightRotate(node->getRight()));
        return leftRotate(node);
    }
    return node;
}
void AVL::inOrder(AVLNode *root)
{
    if(root != NULL)
    {
        inOrder(root->getLeft());
        cout<<root->getInfo()<<"\t";
        inOrder(root->getRight());
    }
}
int main()
{
 AVL tree;
   AVLNode *root = NULL;
    root = tree.insert(root, 17);
    root = tree.insert(root, 12);
    root = tree.insert(root, 21);
    root = tree.insert(root, 10);
    root = tree.insert(root, 15);
    root = tree.insert(root, 19);
    root = tree.insert(root, 27);
    root = tree.insert(root, 14);
    root = tree.insert(root, 16);
    
  cout<<"InOrder traversal of the constructed AVL "<<endl;
    tree.inOrder(root);
 cout<<endl; 
    root = tree.deleteNode(root, 10);
  cout<<"InOrder traversal of the constructed AVL "<<endl;
    tree.inOrder(root); 
 cout<<endl; 
    root = tree.deleteNode(root, 15);
  cout<<"InOrder traversal of the constructed AVL "<<endl;
    tree.inOrder(root); 
 cout<<endl; 
    root = tree.deleteNode(root, 17);
  cout<<"InOrder traversal of the constructed AVL "<<endl;
    tree.inOrder(root); 
 cout<<endl; 
    root = tree.deleteNode(root, 27);
  cout<<"InOrder traversal of the constructed AVL "<<endl;
    tree.inOrder(root); 
 cout<<endl; 
    root = tree.deleteNode(root, 19);
  cout<<"InOrder traversal of the constructed AVL "<<endl;
    tree.inOrder(root); 
 cout<<endl; 
    root = tree.deleteNode(root, 12);    
  cout<<"\nInOrder traversal of the constructed AVL "<<endl;    
 tree.inOrder(root);
    return 0;
}

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

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

Comments

Post a Comment