Red-Black Tree

Introduction

A Red-Black Tree is a type of self-balancing binary search tree where each node carries an extra attribute, color, either red or black. The name 'Red-Black Tree' is derived from this color attribute. This tree was invented in 1972 by Rudolf Bayer who introduced it as a type of binary search tree where additional bits are used to ensure the tree remains balanced during insertions and deletions.

Properties

A Red-Black Tree maintains balance by preserving the following properties:

1. Every node is either red or black.
2. The root node is always black.
3. All leaves (NIL or empty nodes) are black.
4. If a node is red, then both its children are black.
5. Every path from a node (including root) to any of its descendant NIL nodes contains the same number of black nodes.

These properties ensure that the longest path (root to the farthest leaf) is no more than twice as long as the shortest path (root to the nearest leaf). This balance is what gives Red-Black Trees their search, insertion, and deletion times of O(log n).

A Red-Black Tree with nodes colored either red or black.

A Red-Black Tree with nodes colored either red or black.

Operations

Red-Black Trees support the following operations:

1. Search: This operation works exactly the same as it does in a binary search tree.
2. Insertion: This operation is complex because it involves maintaining the Red-Black Tree properties. The new node is always inserted as a red node. If the parent of this new node is black, then all properties are preserved. However, if the parent is red, then we have a violation of the properties (property 4). This violation is corrected by a series of rotations and recoloring.
3. Deletion: This operation is also complex. When a node is removed, a double black node is created and we run a procedure to remove this double black.

Insertion in Red-Black Tree

The insertion operation in a Red-Black Tree involves the following steps:

1. The new node is inserted at the correct position using the binary search tree insertion procedure.
2. The color of the new node is set to red.
3. If the parent of the new node is black, then we are done. If it's red, then we have a violation of the Red-Black Tree properties. This violation is corrected using a procedure called rotation.

The rotation procedure involves changing the colors of certain nodes and performing left or right rotations. This procedure ensures that the Red-Black Tree properties are preserved.

Deletion in Red-Black Tree

The deletion operation in a Red-Black Tree involves the following steps:

1. The node to be deleted is removed using the binary search tree deletion procedure.
2. If the deleted node is red, then we are done. If it's black, then we have a violation of the Red-Black Tree properties. This violation is corrected using a procedure called double black removal.

The double black removal procedure involves changing the colors of certain nodes and performing left or right rotations. This procedure ensures that the Red-Black Tree properties are preserved.

Applications

Red-Black Trees are used in many search applications where the data is constantly entering and leaving. For example, they are used in the Linux kernel, Java's TreeMap and TreeSet, C++'s map and set objects, and many more.

See Also

1. Binary Search Tree
2. Tree rotation
3. Linux Kernel
4. Java (programming language)
5. C++