Red-Black Tree

Red-Black Tree is a self-balancing height-balanced Binary Search Tree.

Red-Black Tree approximately balances itself on insert and deletion operations to guarantee O(log n) search. Insertion and deletion time are also in O(log n) even in the worst case. This data structure is valuable for time-sensitive application such as real-time applications.

Requirements:

1. Each node is either red or black.
2. The root and the leaf nodes are black.
3. The leaf node does not contain data.
4. A red node cannot have a red parent or children.
5. The number of black nodes from the root to a given node is called the black depth. Every paths from root to the leaves have the same black depth and it is called the black-height.

Property: the path from the root to the farthest left is no more than twice as long as the path from the root to the nearest leaf. That is why, the Red-Black Tree is height-balanced.

Resources

https://en.wikipedia.org/wiki/Red%E2%80%93black_tree
http://www.computepatterns.com/problem-solving/data-structures/binary-tree/binary-search-tree-bst/splay-tree-and-red-black-tree/