Red-Black Trees

What are they?

A Red-Black Tree is a special variant of a binary search tree (BST) that is self-balancing. It has rules about "coloring" each node (either red or black) to ensure that the tree stays balanced, which keeps search times as O(log n).

Key Properties

• Every node is either red or black.
• The root node and all leaf nodes (NIL) are always black.
• A red node cannot have a red child.
• Every path from a node to its leaves has same number of black nodes.

To learn more, check out the RBT listing on this Wikipedia page.