Red Black Tree Description

Red Black Tree

Red Black Tree is a Binary Search Tree which the following red-black properties

1- Every node is either black or red 
2- Every leaf(NULL) is black 
3- if a node is red then both its children will be black
4- Every simple path from a node to a descendent leaf contains the same number of black nodes. 

<implies that on any path from the root to a leaf, red nodes must not be adjacent. However, any number of black nodes may appear in a sequence > 

Image - <https://www.cs.auckland.ac.nz/software/AlgAnim/fig/rb_tree1.gif> this is a basic red black tree 

One of the greatest advantage of red black trees is that it is self balancing. In Binary search tree there is no guarantee that the search time will always will be 0(nlogn).

Let's take this example :

A regular Binary Search tree is not self balancing, meaning depending on the order of insertions you will get different time complexities.
For example;

    if you inserted in order {2, 3, 1}, the BST will be O( log(N) )

    however if you inserted {1,2,3}, the BST will be O( N ), like a linked list.

A Red Black tree however will reorganise itself so that you will always get O( log(N) ) complexity.

In short;
Red Black Tree : best case O(logN), worst case O(logN)
Binary Search Tree: best case O(logN), worst case O(N)


<The same property can be easily said like A red and black tree is self-balancing BST that ensures the worst case time  complexity is O(logN) and a height of logN. A binary search tree has no balancing and therefore has a worst case time complexity of O(N) and a worst case height of N. A BST could look exactly like a red and black tree and have O(logN) complexity, but sometimes will not> 


This is a real red black tree <https://www.cs.auckland.ac.nz/software/AlgAnim/fig/rb_tree1a.gif>  this is nothing just a basic red black tree with sentinel nodes are added. Implementations of the red-black tree algorithms will usually include the sentinel nodes as a convenient means of flagging that you have reached a leaf node. <The leaf nodes in red black tree is always NULL>