Red-Black Trees

A balanced binary search tree that keeps operations near O(log n).

Key Properties

Every node is red or black.
The root is black; no red node has a red child.
All paths from a node to null leaves have the same black height.

Diagram

Diagram of a Red-Black Tree

More info: Wikipedia — Red–black tree