In this tutorial, we are going to solve or make a solution to the Self Balancing Tree problem. so here we have given a pointer to the root node of an AVL tree. and we need to insert a value into the tree and perform the necessary rotation to balance a tree.
Problem solution in Java Programming.
static Node insert(Node root,int val) { if(root == null) { root = new Node(); root.val = val; root.ht = setHeight(root); return root; } if(val <= root.val) { root.left = insert(root.left, val); } else if (val > root.val) { root.right = insert(root.right, val); } int balance = height(root.left) - height(root.right); if(balance > 1) { if(height(root.left.left) >= height(root.left.right)) { root = rightRotation(root); } else { root.left = leftRotation(root.left); root = rightRotation(root); } } else if(balance < -1) { if(height(root.right.right) >= height(root.right.left)) { root = leftRotation(root); } else { root.right = rightRotation(root.right); root = leftRotation(root); } } else { root.ht = setHeight(root); } return root; } private static Node rightRotation(Node root) { Node newRoot = root.left; root.left = newRoot.right; newRoot.right = root; root.ht = setHeight(root); newRoot.ht = setHeight(newRoot); return newRoot; } private static Node leftRotation(Node root) { Node newRoot = root.right; root.right = newRoot.left; newRoot.left = root; root.ht = setHeight(root); newRoot.ht = setHeight(newRoot); return newRoot; } private static int height(Node root) { if(root == null) return -1; else return root.ht; } private static int setHeight(Node root) { if(root == null) { return -1; } else { return 1 + Math.max(height(root.left), height(root.right)); } }
Problem solution in C++ programming.
int height(node * root) { if (root) return root->ht; else return -1; } void rotateRight(node * & root) { node* temp = root->left; root->left = root->left->right; temp->right = root; root->ht = 1 + ((height(root->right) > height(root->left)) ? height(root->right) : height(root->left)); temp->ht = 1 + ((height(temp->right) > height(temp->left)) ? height(temp->right) : height(temp->left)); root = temp; } void rotateLeft(node * & root) { node* temp = root->right; root->right = root->right->left; temp->left = root; root->ht = 1 + ((height(root->right) > height(root->left)) ? height(root->right) : height(root->left)); temp->ht = 1 + ((height(temp->right) > height(temp->left)) ? height(temp->right) : height(temp->left)); root = temp; } void rotateLeftRight(node * & root) { rotateLeft(root->left); rotateRight(root); } void rotateRightLeft(node * & root) { rotateRight(root->right); rotateLeft(root); } void insert1(node * & root, int val) { if(root == NULL) { root = new node(); root->val = val; root->left = NULL; root->right = NULL; root->ht = 0; } else if(root->val > val) { insert1(root->left, val); int balance = height(root->right) - height(root->left); int leftbalance = height(root->left->right) - height(root->left->left); if(balance == -2) { if(leftbalance == -1) { rotateRight(root); } if(leftbalance == +1) { rotateLeftRight(root); } } } else if(root->val < val) { insert1(root->right, val); int balance = height(root->right) - height(root->left); int rightbalance = height(root->right->right) - height(root->right->left); if(balance == 2) { if(rightbalance == 1) { rotateLeft(root); } if(rightbalance == -1) { rotateRightLeft(root); } } } root->ht = 1 + ((height(root->right) > height(root->left)) ? height(root->right) : height(root->left)); } node * insert(node * root,int val) { insert1(root, val); return root; }