Red Black Tree Introduction

Time complexity:

O(log n) in every operation

1. Nodes are either red or black
2. NIL nodes (empty leaf nodes) are black
3. Children of red nodes are black
4. The number of black nodes on each path from the root node to the NIL node is the same