Self Balancing Tree


Problem Statement :


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.


(https://en.wikipedia.org/wiki/AVL_tree)

You are given a pointer to the root of an AVL tree. You need to insert a value into this tree and perform the necessary rotations to ensure that it remains balanced.

Input Format

You are given a function,

node *insert(node * root,int new_val)
{


}
'node' is defined as :

struct node
{
int val;            //value
struct node* left;  //left child
struct node* right; //right child
int ht;             //height of the node
} node;
You only need to complete the function.

Note: All the values in the tree will be distinct. Height of a Null node is -1 and the height of the leaf node is 0.


Output Format

Insert the new value into the tree and return a pointer to the root of the tree. Ensure that the tree remains balanced.

Sample Input

    3
  /  \
 2    4
       \
        5
The value to be inserted is 6.


Solution :



title-img 


                            Solution in C :

In C++ :




/* Node is defined as :
typedef struct node
{
    int val;
    struct node* left;
    struct node* right;
    int ht;
} node; */


node * insert(node * T,int x)
{
    if (T == NULL)
    {
        T = (node*)malloc(sizeof(node));
        T->val = x;
        T->left = NULL;
        T->right = NULL;
    }
    else if (x > T->val)
    {
        T->right = insert_hidden(T->right, x);
        if (BF_hidden(T) == -2)
        {
            if (x > T->right->val)
            {
                T = RR_hidden(T);
            }
            else
            {
                T = RL_hidden(T);
            }
        }
    }
    else if (x < T->val)
    {
        T->left = insert_hidden(T->left, x);
        if (BF_hidden(T) == 2){
            if (x < T->left->val)
            {
                T = LL_hidden(T);
            }
            else
            {
                T = LR_hidden(T);
            }
        }
    }
    T->ht = ht_hidden(T);
    return(T);
   
  
}








In Java :



   /* Class node is defined as :
    class Node 
       int val;   //Value
       int ht;      //Height
       Node left;   //Left child
       Node right;   //Right child

   */

static Node insert(Node root,int val) {
    Node newNode = new Node(); 
    newNode.val = val;
    newNode.ht = 0;
    newNode.left = null;
    newNode.right = null;
    
    if (root==null) {
        root = newNode;
    } else {
        root=avlinsert(newNode, root);
    }
    
    return root;
} 

// return height of tree rooted at x
static public int height(Node x) {
    if (x == null) return -1;
    else return x.ht;
}

static public Node rotatewithleft(Node c) {
    Node p;  // left child of c

    p = c.left;
    c.left = p.right;
    p.right = c;

    c.ht = Math.max(height(c.left), height(c.right)) + 1;
    p.ht = Math.max(height(p.left), height(p.right)) + 1;

    return p;
}

static public Node rotatewithright(Node c) {
    Node p;  // right child of c

    p = c.right;
    c.right = p.left;
    p.left = c;

    c.ht = Math.max(height(c.left), height(c.right)) + 1;
    p.ht = Math.max(height(p.left), height(p.right)) + 1;

    return p;
}

static public Node doublerotatewithleft(Node c) {
    Node tmp;

    c.left = rotatewithright(c.left);
    tmp = rotatewithleft(c);

    return tmp;
}

static public Node doublerotatewithright(Node c) {
    Node tmp;

    c.right = rotatewithleft(c.right);
    tmp = rotatewithright(c);

    return tmp;
}

static public Node avlinsert(Node newNode, Node par) {
   Node newpar = par;  // root of subtree par

    if (newNode.val < par.val)  {
        if (par.left == null) {
            par.left = newNode;  //attach new node as leaf
        }
    else {
         par.left = avlinsert(newNode, par.left);   // branch left
         if ((height(par.left) - height(par.right)) == 2) {
            if (newNode.val < par.left.val) {
                newpar=rotatewithleft(par);
            } else {
                newpar=doublerotatewithleft(par);
            } //else
         } //if
      } // else
   } // if
    else if (newNode.val > par.val) { // branch right
        if (par.right == null) {
            par.right = newNode;   // attach new node as leaf
        } else {
            par.right = avlinsert(newNode, par.right);  // branch right
            if ((height(par.right) - height(par.left)) == 2) {
                if (newNode.val > par.right.val) {
                    newpar=rotatewithright(par);
                } //if
                else {
                    newpar=doublerotatewithright(par);
                } //else
            } //if
        } //else
    }  // else if

    // Update the height, just in case

    if ((par.left == null) && (par.right != null))
        par.ht = par.right.ht + 1;
    else if ((par.right == null) && (par.left != null))
        par.ht = par.left.ht + 1;
    else
        par.ht = Math.max(height(par.left), height(par.right)) + 1;

    return newpar; // return new root of this subtree
 }








View More Similar Problems

Minimum Average Waiting Time

Tieu owns a pizza restaurant and he manages it in his own way. While in a normal restaurant, a customer is served by following the first-come, first-served rule, Tieu simply minimizes the average waiting time of his customers. So he gets to decide who is served first, regardless of how sooner or later a person comes. Different kinds of pizzas take different amounts of time to cook. Also, once h

View Solution →

Merging Communities

People connect with each other in a social network. A connection between Person I and Person J is represented as . When two persons belonging to different communities connect, the net effect is the merger of both communities which I and J belongs to. At the beginning, there are N people representing N communities. Suppose person 1 and 2 connected and later 2 and 3 connected, then ,1 , 2 and 3 w

View Solution →

Components in a graph

There are 2 * N nodes in an undirected graph, and a number of edges connecting some nodes. In each edge, the first value will be between 1 and N, inclusive. The second node will be between N + 1 and , 2 * N inclusive. Given a list of edges, determine the size of the smallest and largest connected components that have or more nodes. A node can have any number of connections. The highest node valu

View Solution →

Kundu and Tree

Kundu is true tree lover. Tree is a connected graph having N vertices and N-1 edges. Today when he got a tree, he colored each edge with one of either red(r) or black(b) color. He is interested in knowing how many triplets(a,b,c) of vertices are there , such that, there is atleast one edge having red color on all the three paths i.e. from vertex a to b, vertex b to c and vertex c to a . Note that

View Solution →

Super Maximum Cost Queries

Victoria has a tree, T , consisting of N nodes numbered from 1 to N. Each edge from node Ui to Vi in tree T has an integer weight, Wi. Let's define the cost, C, of a path from some node X to some other node Y as the maximum weight ( W ) for any edge in the unique path from node X to Y node . Victoria wants your help processing Q queries on tree T, where each query contains 2 integers, L and

View Solution →

Contacts

We're going to make our own Contacts application! The application must perform two types of operations: 1 . add name, where name is a string denoting a contact name. This must store name as a new contact in the application. find partial, where partial is a string denoting a partial name to search the application for. It must count the number of contacts starting partial with and print the co

View Solution →