Red Black Trees

Introduction

A Red-Black Tree is a self-balancing binary search tree that maintains a balanced structure through rotations. Search, insertion, and deletion are all O(log n), where n represents the number of nodes.

Rules of Red Black Trees

• Every node is either red or black.
• The root node is always black.
• Red nodes cannot have red children.
• Every path from a node down to a null node must have the same number of black nodes along that path.
• A null node is considered to be black.

Red Black Tree Diagram