# What Is a Red-Black Tree Data Structure?

//

Larry Thompson

A red-black tree is a self-balancing binary search tree that maintains balance during insertion and deletion operations. It is named after the two colors assigned to each node in the tree – red or black.

## Properties of a Red-Black Tree

• 1. Balanced Tree: A red-black tree ensures that the longest path from the root to any leaf is no more than twice as long as the shortest path.
• 2. Coloring: Each node in a red-black tree is either colored red or black.
• 3. Root Property: The root of the tree is always black.
• 4.

Red Property: No two adjacent nodes can both be red. In other words, a red node cannot have a red parent or child.

• 5. Black Depth Property: All paths from any given node to its descendant leaves contain an equal number of black nodes (black depth).

## The Insertion Process

The insertion process in a red-black tree consists of several steps to ensure that all properties are maintained:

### 1. Binary Search Tree Insertion

The new node is inserted into the binary search tree following the standard procedure for binary search trees, based on its key value.

### 2. Coloring the New Node

The newly inserted node is colored red to preserve property 4 (no adjacent red nodes).

### 3. Rotations and Re-coloring

If necessary, rotations and re-coloring are performed to fix any violations of properties 1 (balanced tree) and 4 (no adjacent red nodes).

There are several cases that may require rotations and re-coloring:

• Case 1: If the parent of the newly inserted node is black, no further actions are required, and the tree remains balanced.
• Case 2: If the parent of the newly inserted node is red and its sibling is also red, a recoloring and possible rotations are performed to balance the tree.
• Case 3: If the parent of the newly inserted node is red and its sibling is black or null, rotations and re-coloring are performed to balance the tree.

## The Deletion Process

The deletion process in a red-black tree also involves several steps to maintain all properties:

### 1. Binary Search Tree Deletion

The node to be deleted is removed from the binary search tree using standard deletion techniques for binary search trees. Re-coloring or Rotation

If necessary, re-coloring or rotations are performed to fix any violations of properties 1 (balanced tree) and 4 (no adjacent red nodes).

The deletion process has different cases based on whether the deleted node has zero, one, or two children. Each case has its own set of rules for balancing the tree after deletion.