Red-black Tree

Red-black tree is a balanced binary search tree.

Rules for Red-black trees:

• every node is red or black

• root is always black

• new insertions are always red

• every path from root to leav has the same number of black nodes

• no path can have two consecutive red nodes

• nulls are black