Self Balancing Trees (Hackerrank)

An AVL tree (Georgy Adelson-Velsky and Landis' tree, named after the inventors) is a self-balancing binary search tree. In an AVL tree, the heights of the two child subtrees of any node differ by at most one; if at any time they differ by more than one, rebalancing is done to restore this property.


We define balance factor for each node as :

balanceFactor = height(left subtree) - height(right subtree)

The balance factor of any node of an AVL tree is in the integer range [-1,+1]. If after any modification in the tree, the balance factor becomes less than −1 or greater than +1, the subtree rooted at this node is unbalanced, and a rotation is needed.











Code - 

int height(node* root)

{

    if(root)

            return root->ht;

    else

        return -1;

}


void rotateright(node* &root)

{

    node* temp= root->left;

    root->left= root->left->right;

    temp->right=root;

    

    root->ht= 1+ ((height(root->right)>height(root->left))? height(root->right) : height(root->left));

    

    temp->ht= 1+ ((height(temp->right)>height(temp->left))? height(temp->right) : height(temp->left));

    

    root=temp;

    

}


void rotateleft(node* &root)

{

    node* temp= root->right;

    root->right=root->right->left;

    temp->left=root;

    

    root->ht= 1+ ((height(root->right)> height(root->left)) ? height(root->right) : height(root->left));

    

    temp->ht = 1 + ((height(temp->right) > height(temp->left)) ? height(temp->right) : height(temp->left));

    root = temp;


}


void rotateleftright(node* &root)

{

    rotateleft(root->left);

    rotateright(root);

}


void rotaterightleft(node* &root)

{

    rotateright(root->right);

    rotateleft(root);

}


void insert1(node* &root, int val)

{

    if(root==NULL)

    {

        root= new node();

        root->val= val;

        root->left = NULL;

        root->right = NULL;

        root->ht=0;

    }

    else if(root->val > val)

    {

        insert1(root->left, val);

        int balance = height(root->right) - height(root->left);

        

        int leftbalance = height(root->left->right) - height(root->left->left);

        

        if(balance == -2)

        {

            if(leftbalance==-1)

                    rotateright(root);

            if(leftbalance==+1)

                    rotateleftright(root);

        }

    }

    else if(root->val<val)

    {

        insert1(root->right, val);

        

        int balance= height(root->right) - height(root->left);

        int rightbalance= height(root->right->right)- height(root->right->left);

        

        if(balance ==2)

        {

            if(rightbalance==1)

                rotateleft(root);

            if(rightbalance==-1)

                rotaterightleft(root);

        }

    }

    root->ht= 1+ ((height(root->right)>height(root->left))? height(root->right) : height(root->left));

}


node* insert(node* root, int val)

{

    insert1(root, val);

    return root;

}

Popular posts from this blog

Finding the Subarrays (Hackerearth)

Image
Finding subarrays can become a cumbersome task to handle if we don't know the right approach for it. In this particular question we will be using a new method.  Pair is used to combine together two values which may be different in type. Pair provides a way to store two heterogeneous objects as a single unit. Such as vector<first attribute, second attribute>. To access these attributes we use keywords 'first' and 'second' Approach - Input values and find total sum of all terms Create a loop and calculate average term by term, use logic ->  sum= first element this_average=sum/elements in the sum SZ= Elements left in array= size-elements in sum other_average=(total-sum)/SZ Use if loop to find whether this_average is bigger than other_average or not. If true, input the (i+1)th and (j+1)th element in the pair, Increment counter by 1 Sort the pair and output it. Code- #include< bits/stdc++.h > using namespace std ; int main () {       ...
Read more

Missing Numbers (Hackerrank)

Image
Sometimes the easiest of the questions can become cumbersome and actually put our knowledge to the test. The following question had me writing code for 30 minutes, only to be rejected by the compiler telling me that I was missing something! Question-  Approach -  Make a new array with last element = 0   Input all values of Bigger array Delete similar values found in Smaller array Print all the values which are higher than 0 Now what took me so long? I made nested for loops to check every value of A if it lies in B, if it doesn't, I would append this value to an empty array, sort it and print it. But when i did that, It gave me repeating values and the output was in the form of m+n where m and n are sizes of the array respectively. Hence, I had to do some brainstorming and research which led me to a realization that i can simply add all elements of bigger array brr[m] in a new array C, then delete the same values from C taking elements of arr[n] into consideration!...
Read more

Find Missing Number (Amazon SDE)

Problem - You are given an array from 1 to n, such that all numbers are present except 'x'.  Find 'x' Approach - We know that the sum of all numbers from 1 to n is n(n+1)/2, If we know this value, then we can easily delete the sum of all the elements except x to find x. Code - #include< bits/stdc++.h > using   namespace  std ; int  main () {    int  n ;  cin >> n ;    int  sum_of_n  =   ( n *( n + 1 ))/ 2 ;    int  arr [ n ];    int  sum_of_arr ;    for ( int  i = 0 ; i < n ; i ++)    {     cin >> arr [ i ];     sum_of_arr += arr [ i ];    }    int  x =  sum_of_arr  -  sum_of_n ;   cout << x ;    return   0 ; }
Read more