This is a C++ implementation of a Red Black Tree. A Red Black Tree is a self balancing binary search tree that obeys the following properties:

• Nodes are either red or black
• The root is black
• Every leaf node has two NIL children which are black
• If a node is red then its children are both black
• Every path from root to a NIL node passes through the same amount of black nodes