Red-Black Trees

Overview:

A Red-Black Tree is a self-balancing binary search tree that maintains balance during insertion and deletion operations.

Red-Black Tree Properties:

1. The root is black.
2. Every leaf (Leaf is a NULL child of a node) is black in Red-Black tree.
3. The children of a red node are black. Hence possible parent of red node is a black node.
4. All the leaves have the same black depth.
5. Every simple path from root to descendant leaf node contains same number of black nodes.

Visual Representation:

Other Reading:

For more information about Red-Black Trees, please visit GeeksforGeeks' Red-Black Tree tutorial page.