Red Black Tree (thing)

A binary tree that satisfies these properties:
1. Every node is either red or black.
2. Every leaf is black.
3. If a node is red, then both its children are black.
4. Every simple path from a node to a descendant leaf contains the same number of black trees.
By preserving these properties you create an approximately balanced tree that can be searched at O( lg n).