A Binary Search Tree (BST) is a data structure with a unique starting node (the root), in which each node is capable of having two child nodes, and in which a unique path exists from the root to every other node. So the top node of tree structure refers to as root node, which has no parent. There is also the concept of leaf node which has no children. previously we have made some introductory discussion on BST, here. In this article we will discuss about Imbalanced Tree and BST rotation.
The reason of BST in data structure is that insertion, deletion or searching elements in BST takes order of log (N) time. But a tree wouldn’t be much efficient if it become imbalanced. An imbalanced tree may take maximum O(n) time for any operation, because an imbalanced tree behaves almost like a list. In such case to balance the tree we need to apply the rotation techniques.
For any binary tree the common rule is that nodes that left-side of the root always smaller than the root, and nodes that right-side of the root are always bigger that the root. Now, let we have some sorted number:
2, 4, 6, 8, 10, 12, 14, 16, 18
So to build a balanced tree we pick the number 10 as a root from the sorted list. Then for left child we pick the middle 6 from left half. Similarly for the right child we pick the middle 14 from right half, and so on. But if we a pick the left most number 2 as a root, and continue adding the subsequent numbers to its right, then we’ll have an imbalanced tree.
Right BST Rotation
As we see that if we manipulate the data carefully that we can easily create a balanced tree. But we also can manipulate the tree as we add element we can keep the tree balance. Suppose that part of our tree as: 10 is the root, then 6 is its left child, and 4 is it’s left grand child. So 4 is the element that causes the tree imbalanced. Therefore to make the tree balanced we have to rotate the grand parent 10, the root itself. As we have problem in the left child’s left sub-tree, therefore we have to do right rotation. In this case 6 will be the new root, and 4 is the left child, and 10 is its right child, hence our tree is balanced.
Left BST Rotation
Similarly if the imbalance happen in right child’s right sub-tree, then we will do the left rotation of the root. So if we have tree like: 4 is the root, 6 is the right child, and 10 is the right sub-tree. Here 10 cause the tree imbalanced. Therefore we have to rotate the grand parent, the root 4 the left rotation.
In BST rotation what we are actually doing is: we taking the median element rotate to the top. So for right-rotation root becomes the right child. Also for the left-rotation root becomes the left child.
We might also need to do both left and right rotation for a single problem. If we have problem in right child’s left sub-tree. In this case we have to do right rotation in parent, and then left-rotation in grand parent. Similarly if we have problem in left child’s right sub-tree, then left-rotation in parent, and then right-rotation in grand parent.