Algorithm


Problem Name: Data Structures - Self Balancing Tree

Problem Link: https://www.hackerrank.com/challenges/swap-nodes-algo/problem?isFullScreen=true

In this HackerRank in Data Structures - Self Balancing Tree solutions

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)

 

 

Code Examples

#1 Code Example with C++ Programming

Code - C++ Programming


node* newAvlTreeNode(int data);
int heightOfSubtree(node *nod);
int maxVal(int a, int b);
node *leftRotate(node *x);
node* rightRotate(node *y);
int getBalance(node *Nod);

node* insert(node* root,int val)
{
	if (root == NULL)
		return  newAvlTreeNode(val);

	if (val  <  root -> val)
		root->left = insert(root->left,val );
	else if (val > root->val)
		root->right = insert(root->right,val );


	root->ht = 1 + maxVal(heightOfSubtree(root->left), heightOfSubtree(root->right));

	//Get the balance factor of parent node
	int balance = getBalance(root);

	if (balance > 1 && val  <  root->left->val)
		return rightRotate(root);

	// Right Right Case
	if (balance < -1 && val > root->right->val)
		return leftRotate(root);

	// Left Right Case
	if (balance > 1 && val > root->left->val)
	{
		root->left = leftRotate(root->left);
		return rightRotate(root);
	}

	// Right Left Case
	if (balance  <  -1 && val < root->right->val)
	{
		root->right = rightRotate(root->right);
		return leftRotate(root);
	}
	return root;
}

node* rightRotate(node *y)
{
	node* x = y->left;
	node* T2 = x->right;

	// Perform rotation
	x->right = y;
	y->left = T2;

	// Update heights
	y->ht = maxVal(heightOfSubtree(y->left), heightOfSubtree(y->right)) + 1;
	x->ht = maxVal(heightOfSubtree(x->left), heightOfSubtree(x->right)) + 1;

	// Return new root
	return x;
}


node *leftRotate(node *x)
{
	node *y = x->right;
	node *T2 = y->left;

	// Perform rotation
	y->left = x;
	x->right = T2;

	//  Update heights
	x->ht = maxVal(heightOfSubtree(x->left), heightOfSubtree(x->right)) + 1;
	y->ht = maxVal(heightOfSubtree(y->left), heightOfSubtree(y->right)) + 1;

	// Return new root
	return y;
}

int getBalance(node *Nod)
{
	if (Nod == NULL)
		return 0;
	return heightOfSubtree(Nod->left) - heightOfSubtree(Nod->right);
}

int maxVal(int a,int b)
{
	return (a > b) ? a : b;
}

node* newAvlTreeNode(int data)
{
	// Allocate memory for new node 
	node* treeNode = (node*)malloc(sizeof(node));

	// Assign data to this node
	treeNode->val = data;

	// Initialize left and right children as NULL
	treeNode->left = NULL;
	treeNode->right = NULL;
	treeNode->ht = 0;
	return(treeNode);
}

int heightOfSubtree(node *nod)
{
	if (nod == NULL)
		return -1;
	return nod->ht;
}
Copy The Code & Try With Live Editor

#2 Code Example with Java Programming

Code - Java Programming


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
 }
Copy The Code & Try With Live Editor

#3 Code Example with Javascript Programming

Code - Javascript Programming


const pr = console.log;

class AVLNode {
    constructor(val) {
        this.val = val;
        this.left = null;
        this.right = null;
        this.height = 1;
        this.cnt = 1;
    }
}

class AVLTree {
    constructor() {
        this.root = null;
    }
    getHeight(node) {
        return node != null ? node.height : 0;
    }
    getBalance(node) {
        return node != null ? this.getHeight(node.left) - this.getHeight(node.right) : 0;
    }
    LR(z) {
        let y = z.right;
        let T2 = y.left;
        y.left = z;
        z.right = T2;
        z.height = 1 + Math.max(this.getHeight(z.left), this.getHeight(z.right));
        y.height = 1 + Math.max(this.getHeight(y.left), this.getHeight(y.right));
        return y;
    }
    RR(z) {
        let y = z.left;
        let T3 = y.right;
        y.right = z
        z.left = T3
        z.height = 1 + Math.max(this.getHeight(z.left), this.getHeight(z.right));
        y.height = 1 + Math.max(this.getHeight(y.left), this.getHeight(y.right));
        return y;
    }
    insert(v) {
        this.root = this.insertUtil(this.root, v);
    }
    insertUtil(node, v) {
        if (node == null) {
            return new AVLNode(v);
        } else if (v  <  node.val) {
            node.left = this.insertUtil(node.left, v);
        } else if (v > node.val) {
            node.right = this.insertUtil(node.right, v);
        } else {
            node.cnt++;
            return node;
        }
        node.height = 1 + Math.max(this.getHeight(node.left), this.getHeight(node.right));
        let bal = this.getBalance(node);
        if (bal > 1 && v  <  node.left.val) return this.RR(node);
        if (bal > 1 && v > node.left.val) {
            node.left = this.LR(node.left);
            return this.RR(node);
        }
        if (bal  <  -1 && v > node.right.val) return this.LR(node);
        if (bal < -1 && v < node.right.val) {
            node.right = this.RR(node.right);
            return this.LR(node);
        }
        return node;
    }
    remove(v) {
        this.root = this.removeUtil(this.root, v);
    }
    removeUtil(node, v) {
        if (node == null) {
            return node;
        } else if (v  <  node.val) {
            node.left = this.removeUtil(node.left, v);
        } else if (v > node.val) {
            node.right = this.removeUtil(node.right, v);
        } else {
            if (node.cnt > 1) {
                node.cnt--;
                return node;
            }
            if (node.left == null) {
                let tmp = node.right;
                node = null;
                return tmp;
            } else if (node.right == null) {
                let tmp = node.left;
                node = null;
                return tmp;
            }
            let tmp = this.findMin(node.right);
            node.val = tmp.val;
            node.right = this.removeUtil(node.right, tmp.val);
        }
        if (node == null) return node;
        node.height = 1 + Math.max(this.getHeight(node.left), this.getHeight(node.right));
        let bal = this.getBalance(node);
        if (bal > 1 && this.getBalance(node.left) >= 0) return this.RR(node);
        if (bal  <  -1 && this.getBalance(node.right) <= 0) return this.LR(node);
        if (bal > 1 && this.getBalance(node.left) < 0) {
            node.left = this.LR(node.left);
            return this.RR(node);
        }
        if (bal  <  -1 && this.getBalance(node.right) > 0) {
            node.right = this.RR(node.right);
            return this.LR(node);
        }
        return node;
    }
    FindFirstOf(value) {
        let node = this.root, res = null;
        while (node != null) {
            if (value  <  node.val) {
                node = node.left;
            } else if (value > node.val) {
                node = node.right;
            } else {
                res = node;
                node = node.left;
            }
        }
        return res;
    }
    FindLastOf(value) {
        let node = this.root, res = null;
        while (node != null) {
            if (value  <  node.val) {
                node = node.left;
            } else if (value > node.val) {
                node = node.right;
            } else {
                res = node;
                node = node.right;
            }
        }
        return res;
    }
    maxx() {
        let node = this.findMax(this.root);
        return node == null ? null : node.val;
    }
    minx() {
        let node = this.findMin(this.root);
        return node == null ? null : node.val;
    }
    findMin(node) {
        return node == null || node.left == null ? node : this.findMin(node.left);
    }
    findMax(node) {
        return node == null || node.right == null ? node : this.findMax(node.right);
    }
    preOrder_DFS() {
        let d = [];
        this.dfs(this.root, d);
        return d;
    }
    dfs(node, d) {
        if (!node) return;
        d.push(node.val);
        this.dfs(node.left, d);
        this.dfs(node.right, d);
    }
}

let tree;
const solve = (n, a, v) => {
    tree = new AVLTree();
    for (const x of a) tree.insert(x);
    a.push(v);
    tree.insert(v);
    op(a);
};

const op = (a) => {
    let res = [], orderPrint = [], m = new Map();
    for (const x of a) {
        // FindFirstOf FindLastOf both works
        let node = tree.FindFirstOf(x), bal = tree.getBalance(node), s = `${x}(BF=${bal})`;
        m.set(x, s);
        orderPrint.push([x, s])
    }
    orderPrint.sort((x, y) => x[0] - y[0]);
    pr(orderPrint.map(x => x[1]).join(" "));
    let preorder = tree.preOrder_DFS();
    for (const x of preorder) res.push(m.get(x));
    pr(res.join(" "));
};

const main = () => {
    const readLine = () => input[currentLine++];
    const ni = () => readLine() - '0';
    const nas = () => readLine().split(" ");
    const nai = () => nas().map(Number);
    const nal = () => nas().map(BigInt);
    let input = '', currentLine = 0;
    process.stdin.on('data', (stdin) => input += stdin)
    process.stdin.on('end', () => {
        input = input.split('\n');
        let n = ni(), a = nai(), v = ni();
        solve(n, a, v);
    });
};

main()
Copy The Code & Try With Live Editor
Advertisements

Demonstration


Previous
[Solved]Is This a Binary Search Tree? solution in Hackerrank - Hacerrank solution C, C++, java,js, Python
Next
[Solved] Queue using Two Stacks solution in Hackerrank - Hacerrank solution C, C++, java,js, Python