Understanding Red-Black Trees

Introduction

Red-Black tree is a binary search tree in which every node is colored with either red or black.

It is a type of self-balancing binary search tree. It has a good efficient worst case running time complexity.

Key Features:

• Self-balancing
• Complexity guarantees
• Coloring and rotation rules

Rules That Every Red-Black Tree Follows:

1. Every node has a color either red or black.
2. The root of the tree is always black.
3. There are no two adjacent red nodes (A red node cannot have a red parent or red child).
4. Every path from a node (including root) to any of its descendants NULL nodes has the same number of black nodes.
5. Every leaf (e.i. NULL node) must be colored BLACK.

More Resources:

Visual Representation