A nearly-balanced tree that uses an extra bit per node to maintain balance. No leaf is more than twice as far from the root as any other. Formal Definition: A red-black tree with n internal nodes has height at most 2log₂(n+1).