(Insert 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

(Insert 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);
int main()
{
 int x[]={10,1,9,2,8,3,7,4,6,5,-1};
   AVLNode *root = NULL;
 for(int i=0; x[i]>0; i++){
  root = insert(root, x[i]);
 inOrder(root); 
 cout<<endl;
 cout<<"height:"<<root->getHeight()<<endl;
 }
 cout<<"height:"<<root->getHeight()<<endl;
 inOrder(root); 
  return 0;
}
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());
}
AVLNode* 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 // Equal infos are not allowed in BST
        return node;
 
    /* 2. Update height of this ancestor node */
    fixHeight(node);
 
    /* 3. Get the balance factor of this ancestor
          node to check whether this node became
          unbalanced */
    int balance = getBalance(node);
 
    // If this node becomes unbalanced, then
    // there are 4 cases
 
    // 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 the (unchanged) node pointer */
    return node;
}
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:
AVL Tree Node Template In Data Structure Using C++

Comments

Post a Comment