Cerinta completa

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.

Sample Output

    3
  /  \
 2    5
     / \
    4   6

Explanation

After inserting 6 in the tree. the tree becomes:

    3 (Balance Factor = -2)
  /  \
 2    4 (Balance Factor = -2)
       \
        5 (Balance Factor = -1)
         \
          6 (Balance Factor = 0)

Balance Factor of nodes 3 and 4 is no longer in the range [-1,1]. We need to perform a rotation to balance the tree. This is the right right case. We perform a single rotation to balance the tree.

After performing the rotation, the tree becomes : 

                              3 (Balance Factor = -1)
                            /   \
      (Balance Factor = 0) 2     5 (Balance Factor = 0)
                                / \
           (Balance Factor = 0)4   6 (Balance Factor = 0)

Limbajul de programare folosit: cpp14

Cod:

int H(node* n) { return n ? n->ht : -1; }
void pull(node* n) { n->ht = 1 + max(H(n->left), H(n->right)); }
node* rotR(node* y) {
    node* x = y->left;
    node* t2 = x->right;
    x->right = y;
    y->left = t2;
    pull(y); pull(x);
    return x;
}
node* rotL(node* x) {
    node* y = x->right;
    node* t2 = y->left;
    y->left = x;
    x->right = t2;
    pull(x); pull(y);
    return y;
}
node * insert(node * root,int val) {
    if (!root) {
        node* n = new node();
        n->val = val; n->left = n->right = 0; n->ht = 0;
        return n;
    }
    if (val < root->val) root->left = insert(root->left, val);
    else if (val > root->val) root->right = insert(root->right, val);
    else return root;
    pull(root);
    int bal = H(root->left) - H(root->right);
    if (bal > 1 && val < root->left->val) return rotR(root);
    if (bal < -1 && val > root->right->val) return rotL(root);
    if (bal > 1 && val > root->left->val) { root->left = rotL(root->left); return rotR(root); }
    if (bal < -1 && val < root->right->val) { root->right = rotR(root->right); return rotL(root); }
    return root;
}

Scor obtinut: 1.0

Submission ID: 464654982

Link challenge: https://www.hackerrank.com/challenges/self-balancing-tree/problem

Self Balancing Tree