Programming Data Structure BST Rotation | Imbalanced Tree | Data Structure |...

BST Rotation | Imbalanced Tree | Data Structure | CS School

-

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.

BST Rotation

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.

BST Rotation | Imbalanced Tree | Data Structure | CS School

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. 

BST Rotation | Imbalanced Tree | Data Structure | CS School
Fig: Right BST Rotation

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.

BST Rotation | Imbalanced Tree | Data Structure | CS School
Fig: Left BST 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.

Latest Articles

Property Decorator | Getters Setters and Deleters in Python

In this article, we will talk about the Property Decorator in Python. It enables the class functionality...

Dictionaries | HashMap in Python | Working with Key-Values

Dictionaries in Python is similar to Hashmap comparing to other languages. It stores data as a key-value...

Hash Table | Indexing | Hashing Algorithm | Python Implementation

This article will talk about a high-level view of the Hash Table. As a programmer, this technique...

Eigenvector Eigenvalue | Linear Algebra Fundamentals

Eigenvector ($bar{v}$) in linear algebra is a non-zero vector (matrix) that doesn't change its direction during linear...

Pivot Table | Microsoft Excel | Create Data Insight Easily

Pivot table in microsoft Excel is an useful function that gives us a way to create insight...

Macro Function in Microsoft Excel | Automate Repetitive Task

This article we will talk about the Macro. It is a function in microsoft excel which basically...

Must read

Dictionaries | HashMap in Python | Working with Key-Values

Dictionaries in Python is similar to Hashmap...

You might also likeRELATED
Recommended to you