self balancing tree and red black tree and solve unbalance problem of binary search tree

 

Binary search tree is a binary tree which satisfy some rules. The value of the key in the left child or left sub-tree is less than the value of the root. The value of the key in the right child or right sub-tree is more than or equal to the value of the root.The main advantage of this tree data structure is the that take Log(n) time to search the element.

The main problem of Binary search tree is unbalancing problem.

For example

10,20,30,40,50

                                                            Unbalanced Binary search tree

That is unbalance Binary search tree. To search a element 50 that take 5 comparison that is O(n) time just like linear search.

So main problem of binary search tree is unbalance problem. 

Solution of unbalance problem is to balance the binary search tree.To balance the tree use AVL tree or balanced tree using rotation in binary search tree balance the binary search tree.

Another solution is to use self balancing tree or red black tree. That solve the problem of unbalance problem of binary search tree.

Red-Black tree or self balancing tree

Red black tree is a type of self balancing binary search tree. A red black tree is a binary tree where each node has color as extra attribute either red or black.by constraining the coloring of the nodes it is ensured that the longest path from the root to leaf is no longer than twice the length of shortest path.This means that the tree is balanced.

Red Black tree satisfy some problems

• Every node is either red or black in red black tree.
• Root is always black in red black tree.
• Every leaf which is nil is black.
• If node is red then its children is black.
• Every path from a node to any of its descendant Nil node has same number of black node.

Example

Create Red Black tree or self balancing tree of the data

1,2,5,,8,7

Solution 

If create a Binary search tree of the data that tree is unbalanced so create Red black tree or self balancing tree.

First  node is 1 and color is Black because that is root node according to the property of  red black tree.

Next node is 2  and color is red because parent node color is black.

Next node is 5 color is red  because every path has same number of black node.

According to red black tree property node is red then its children is black.

So apply rotation to balance the color of tree

Next node is 8 and color is red 

No two node has same color(Red-Red)

That is red black tree or self balanced binary search tree. because that tree is balance root node is black color. no two node has same color. Every path has same number of black nodes.So that tree follow all property and balanced. If tree is balanced reduce search time. Reduce time complexity. that is main benefit of self  balancing tree.