Red-Black Tree

Overview

In computer science, a Red-Black Tree is a type of binary search tree in which every node is colored with either red or black.

Key Features

• Self-balancing tree with specific properties.
• Time complexity for all operations are O(log n).
• Height of a red-black tree with n nodes is less than or equal to 2log2(n + 1).
• Insertion, deletion and rotation operations are efficient.

Red-Black Tree Properties

1. Root property: Every node is either red or black, with the root always black.
2. Depth property: All the leaves have the same black depth.
3. External property: Every leaf node (null child of a node) is black.
4. Internal property: Children of a red node are black.

Red-Black Tree Example

Learn More

For more information about Red-Black Trees, visit GeeksForGeeks.