Red-Black Tree

• Every node is either red or black.
• The root is black.
• The leaves are black.
• A red node has only black child nodes.
• If there is a node [math]\displaystyle{ x }[/math], then all nodes from x to a leaf have the same height.