A binary search tree which uses a one-bit flag on each node to identify the node by color: either red or black. A set of constraints on node color helps form an approximately balanced binary tree.