Algorithm
Problem Name: Data Structures -
In this HackerRank in Data Structures -
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;
}
#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
}
#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()