A self-balanced tree that flags each node as red or black and treats these flags in such a way to maintain a balanced structure.