**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 :

` ````
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 →