Red-Black Tree

Introduction

A Red-Black Tree is a self-balancing binary search tree, commonly used for efficient data storage and retrieval.

Key Properties

• Every node is either red or black.
• The root node is always black.
• All leaves (null pointers) are black.
• Red nodes cannot have red children (no two red nodes can be adjacent).
• Every path from a node to its descendant leaves has the same number of black nodes.

Red-Black Tree Operations

1. Insertion: Maintains balance using rotations and recoloring.
2. Deletion: Involves fix-up procedures to restore properties.
3. Search: Similar to binary search trees, with O(log n) time complexity.

Diagram

Learn More

For additional information, visit Wikipedia's Red-Black Tree page.