A balanced BST where each node has a color (red or black) which determines when a node needs to be rotated.