Red-Black Trees

Red-Black Trees are a kind of self-balancing Binary Search Tree.

Properties

• Color property: Every node is either red (0) or black (1). (NOTE: root can and always will be black)
• Black Height Property: The number of black nodes is the same along every path from any fixed node to every descendent null reference.
• Red Child Property: Red nodes cannot have a red node as a child.
• RBTs are BSTs. If an RBT violates the BST order property, it is not a valid RBT.

Example of a Red-Black Tree

Here's some more useful info about RBTs.