Red Black Tree

Its a balanced binary search tree, so in worst case with n nodes in the tree, height of the tree can go upto only O(logn). So searching for a key in tree will take at most only O(height) => O(logn).

AVL is also balanced binary search tree with same complexity O(logn), even its more balanced than red black tree. Then why we need complex red black tree. AVL Tree implementation is quiet easy in comparison to red black tree.

Secret is in the definition of balanced tree.

For Red Black Tree:

The longest path from root to nil leaf node is no more than the twice of shortest path from root to nil node. So its have less strict balancing policy it may be not as balanced as AVL tree but balanced enough for achieving worst case O(logn) height.

In previous question we got to know that Red Black Tree is not as Balanced as AVL Tree because of  less strict balancing but this does not answer Why people are using Red Black tree and Why people invented a less balanced binary search tree.

It depends on your need. If your application wants to do lot of insert and delete in binary search tree then AVL tree will make many rotations to preserve balance factor during insert and delete operations but red black tree is less balanced so it will not do as many rotation as AVL. Red Black tree is better when application does lot of insert and deletion operation because it avoids some rotations with less balanced policy.

If any application does search operation frequently and does insert and delete rarely, then search operation will be faster in AVL tree than the Red Black Tree because of  more balanced AVL tree.

.tg {border-collapse:collapse;border-spacing:0;} .tg td{font-family:Arial, sans-serif;font-size:14px;padding:10px 5px;border-style:solid;border-width:1px;overflow:hidden;word-break:normal;border-color:black;} .tg th{font-family:Arial, sans-serif;font-size:14px;font-weight:normal;padding:10px 5px;border-style:solid;border-width:1px;overflow:hidden;word-break:normal;border-color:black;} .tg .tg-xldj{border-color:inherit;text-align:left} .tg .tg-0pky{border-color:inherit;text-align:left;vertical-align:top} .tg .tg-0lax{text-align:left;vertical-align:top}

Operations	AVL Tree	Red Black Tree
Frequent Insert, Delete	It suffers from overhead of rotations as compared to Red Black Tree.	Better
Frequent Search	Better	It is not as balanced as AVL so searches are little bit slower.

I have done a little experiment for comparing the heights of BST, AVL and red black tree. Insertion done with uniformed random keys to avoid worst case of insertion for BST, same key value pair inserted in all three trees. In graph you can see red line is representing the height of red black tree which some times goes down too unlike green line representing AVL tree height. AVL tree is balanced as much as possible, so new insert operation either will not change height or it will increase height. But red black tree is not fully balanced but balanced enough to get log(n) complexity, so it tries to delay balancing process as much as it can then some insert operation triggers balancing mechanism so height decreases in some cases after balancing. This behavior shows us red black tree tries to minimize rotations of balancing process by delaying the balancing. Note it has relation : height(AVL) <= height(Red Black Tree)

Asymptotic complexity is same for both trees.
insert O(logn)
delete O(logn)
search O(logn)
rotations O(1) internal operation to preserve balancing.

Red Black Tree Properties:
1. Every node is either red or black.
2. The root is black.
3. Every leaf (NIL) is black.
4. No Red–Red parent child relationship. In other words If a node is red, then both its children are black.
5. For each node, all paths from the node to descendant leaves contain the same number of black nodes.

Operations                                                                                                                         
User Operations:
Search(key) Its same as all other binary search tree. So we will not discuss search() here.
Insert(key)
Delete(key)

Internal Operations:
Recoloring(node x)
LeftRotate(node x)
RightRotate(node x)

LeftRotate(node x) 

Pseudo Code: 
LeftRotate(node x) 
1   y = right[x]                   //Set y 
2   right[x] = left[y]           //Turn y's left subtree into x's right subtree. 
3   if left[y] != NIL: 
4        then parent[left[y]] = x 
5   parent[y] = parent[x]     // Link x's parent to y. 
6   if parent[x] == NIL: 
7        then root = y 
8   else if x == left[parent[x]] 
9        then left[parent[x]] = y 
10 else 
11     right[parent[x]] = y 
11 left[y] = x                       //Put x on y's left. 
12 parent[x] = y

Pseudo Code: 
RightRotate(node x) 
1   y = left[x]                    //Set y 
2   left[x] = right[y]            //Turn y's right subtree into x's right subtree. 
3   if right[y] != NIL: 
4        then parent[right[y]] = x 
5   parent[y] = parent[x]     // Link x's parent to y. 
6   if parent[x] == NIL: 
7        then root = y 
8   else if x == left[parent[x]] 
9        then left[parent[x]] = y 
10 else 
11     right[parent[x]] = y 
11 right[y] = x                    //Put x on y's right. 
12 parent[x] = y

insert(node x)                                                                                          
step 1. Insert a node x and color it red.
step 2. Recolor and rotate to fix the violations.
case 1:  x is root.   ——————— => color black.
          case 2: x’s uncle is red. ————— => recolor
          case 3: x’s uncle is black (triangle).  => rotate x’s parent
          case 4: x’s uncle is black(line).        => rotate x’s grandparent and recolor.

Figures:
case2: x’s uncle red. => recolor

case 3: x’s uncle is black(triangle).  => rotate x’s parent


case 4: x’s uncle is black(line). => rotate x’s grandparent and recolor.

Code Link:
https://github.com/abhi1kush/BinarySearchTree/tree/master/src

WORK IN PROGRESS …
ptr