Red- Black Tree (M2.1)

Binary Search Tree is a node-based binary tree data structure which has the following properties:

• The left sub tree of a node contains only nodes with keys lesser than the node’s key.
• The right sub tree of a node contains only nodes with keys greater than the node’s key.
• The left and right sub tree each must also be a binary search tree.

A red-black tree is a binary search tree (self balancing) with one extra bit of storage per node: its color, which can be either RED or BLACK .

By constraining the node colors on any simple path from the root to a leaf, red-black trees ensure that no such path is more than twice as long as any other, so that the tree is approximately balanced.

These colors are used to ensure that the tree remains balanced during insertions and deletions. Although the balance of the tree is not perfect, it is good enough to reduce the searching time and maintain it around O(log n) time, where n is the total number of elements in the tree.

Each node of the tree contains the attributes color, key, left, right, and p. 

If a child or the parent of a node does not exist, the corresponding pointer attribute of the node contains the value NIL. We shall regard these NIL s as being pointers to leaves (external nodes) of the binary search tree and the normal, key-bearing nodes as being internal nodes of the tree.

 

A red-black tree is a binary tree that satisfies the following red-black properties:
1. Every node is either red or black.
2. The root is black.
3. Every leaf ( NIL ) is black.
4. If a node is red, then both its children are black.
5. For each node, all simple paths from the node to descendant leaves contain the same number of black nodes. 

Why Red-Black Trees?

Most of the BST operations (e.g., search, max, min, insert, delete.. etc) take O(h) time where h is the height of the BST. The cost of these operations may become O(n) for a skewed Binary tree. If we make sure that the height of the tree remains O(log n) after every insertion and deletion, then we can guarantee an upper bound of O(log n) for all these operations. The height of a Red-Black tree is always O(log n) where n is the number of nodes in the tree. 

Comparison with AVL Tree:( Is RB tree is more balanced than any other trees??

AVL tree is a self-balancing Binary Search Tree (BST) where the difference between heights of left and right sub trees cannot be more than one for all nodes.

The AVL trees are more balanced compared to Red-Black Trees, but they may cause more rotations during insertion and deletion. So if your application involves frequent insertions and deletions, then Red-Black trees should be preferred. And if the insertions and deletions are less frequent and search is a more frequent operation, then AVL tree should be preferred over Red-Black Tree.

General Insertion Algorithm

In a Red Black Tree, every new node must be inserted with color RED. The insertion
operation in Red Black Tree is similar to insertion operation in Binary Search Tree. But it is
inserted with a color property. After every insertion operation, we need to check all the
properties of Red Black Tree. If all the properties are satisfied then we go to next operation
otherwise we need to perform following operation to make it Red Black Tree.
Recolor
Rotation followed by Recolor 

 
The insertion operation in Red Black tree is performed using following steps...

1. Check whether tree is Empty. 
2. If tree is Empty then insert the newNode as Root node with color Black and exit from the operation.  
3. If tree is not Empty then insert the newNode as a leaf node with Red color.  
4. If the parent of newNode is Black then exit from the operation.  
5. If the parent of newNode is Red then check the color of parent node's sibling of newNode.  
6. If it is Black or NULL node then make a suitable Rotation and Recolor it.  
7. If it is Red colored node then perform Recolor and Recheck it. Repeat the same until tree becomes Red Black Tree.
   

Fixing nodes:

1. If a node is red at the root, change it to black.
2. If the new node is red, and its parent is black you don't need to do anything.
3. If a new node is red and its parent is red, what you do depends on colour of sibling of the parent
   • if the sibling of the parent is black, a rotation needs to be performed
   • if the sibling of the parent is red, a color swap with grandparent must be performed