# Introduction to Red-Black Tree

** Binary search trees** are a fundamental data structure, but their performance can suffer if the tree becomes unbalanced.

**are a type of**

**Red Black Trees****that use a set of rules to maintain balance, ensuring logarithmic time complexity for operations like**

**balanced binary search tree****, regardless of the initial shape of the tree.**

**insertion, deletion, and searching****are self-balancing, using a simple color-coding scheme to adjust the tree after each modification.**

**Red Black Trees**Table of Content

- What is a Red-Black Tree?
- Properties of Red-Black Trees
- Example of Red-Black Tree
- Why Red-Black Trees?
- Comparison with AVL Tree:
- Interesting points about Red-Black Tree:
- Basic Operations on Red-Black Tree:
- 1. Insertion
- 2. Searching
- 3. Deletion
- 4. Rotation
- When to Perform Rotations?
- Implementation of Red-Black Tree:
- Advantages of Red-Black Trees:
- Disadvantages of Red-Black Trees:
- Applications of Red-Black Trees:

## What is a Red-Black Tree?

A ** Red-Black Tree **is a self-balancing binary search tree where each node has an additional attribute: a color, which can be either

**or**

**red****. The primary objective of these trees is to maintain balance during insertions and deletions, ensuring efficient data retrieval and manipulation.**

**black**## Properties of Red-Black Trees

A Red-Black Tree have the following properties:

: Each node is either red or**Node Color**.**black**: The root of the tree is always**Root Property**.**black**: Red nodes cannot have red children (no two consecutive red nodes on any path).**Red Property**: Every path from a node to its descendant null nodes (leaves) has the same number of**Black Property**nodes.**black**: All leaves (NIL nodes) are**Leaf Property**.**black**

These properties ensure that the longest path from the root to any leaf is no more than twice as long as the shortest path, maintaining the tree’s balance and efficient performance.

## Example of Red-Black Tree

The ** Correct Red-Black Tree** in above image ensures that every path from the root to a leaf node has the same number of black nodes. In this case, there is one (excluding the root node).

The** Incorrect Red Black Tree** does not follow the red-black properties as

**are adjacent to each other. Another problem is that one of the paths to a leaf node has zero black nodes, whereas the other two contain a black node.**

**two red nodes****Why Red-Black Trees?**

**Why Red-Black Trees?**

Most of the BST operations (e.g., search, max, min, insert, delete.. etc) take ** O(h) **time where h is the height of the BST. The cost of these operations may become

**for a skewed Binary tree. If we make sure that the height of the tree remains**

**O(n)****after every insertion and deletion, then we can guarantee an upper bound of**

**O(log n)****for all these operations. The height of a Red-Black tree is always**

**O(log n)****where n is the number of nodes in the tree.**

**O(log n)**Sr. No. | Algorithm | Time Complexity |
---|---|---|

1. | Search | O(log n) |

2. | Insert | O(log n) |

3. | Delete | O(log n) |

**Comparison with**** AVL Tree**:

**Comparison with**

**AVL Tree**

The AVL trees are more balanced compared to Red-Black Trees, but they may cause more rotations during insertion and deletion. So if your application involves frequent insertions and deletions, then Red-Black trees should be preferred. And if the insertions and deletions are less frequent and search is a more frequent operation, then AVL tree should be preferred over the Red-Black Tree.

**How does a Red-Black Tree ensure balance?**

**How does a Red-Black Tree ensure balance?**

A simple example to understand balancing is, that a chain of 3 nodes is not possible in the Red-Black tree. We can try any combination of colors and see if all of them violate the Red-Black tree property.

**Interesting points about Red-Black Tree:**

**Interesting points about Red-Black Tree:**

- The
height of the red-black tree is the number of black nodes on a path from the root node to a leaf node. Leaf nodes are also counted as**black**nodes. So, a red-black tree of height**black**has**h**.**black height >= h/2** - Height of a red-black tree with
nodes is**n****h<= 2 log**_{2}.**(n + 1)** - All leaves (NIL) are
.**black** - The
depth of a node is defined as the number of black nodes from the root to that node i.e the number of black ancestors.**black**

## Basic Operations on Red-Black Tree:

The basic operations on a Red-Black Tree include:

- Insertion
- Search
- Deletion
- Rotation

## 1. Insertion

Inserting a new node in a Red-Black Tree involves a two-step process: performing a standard binary search tree (BST) insertion, followed by fixing any violations of Red-Black properties.

### Insertion Steps

: Insert the new node like in a standard BST.**BST Insert**:**Fix Violations**- If the parent of the new node is
, no properties are violated.**black** - If the parent is
, the tree might violate the Red Property, requiring fixes.**red**

- If the parent of the new node is

### Fixing Violations During Insertion

After inserting the new node as a ** red** node, we might encounter several cases depending on the colors of the node’s parent and uncle (the sibling of the parent):

: Recolor the parent and uncle to**Case 1: Uncle is Red**, and the grandparent to**black**. Then move up the tree to check for further violations.**red**:**Case 2: Uncle is Black**: Perform a left rotation on the parent.**Sub-case 2.1: Node is a right child**: Perform a right rotation on the grandparent and recolor appropriately.**Sub-case 2.2: Node is a left child**

## 2. Searching

Searching for a node in a Red-Black Tree is similar to searching in a standard ** Binary Search Tree (BST)**. The search operation follows a straightforward path from the

**to a**

**root****, comparing the target value with the current node’s value and moving left or right accordingly.**

**leaf**### Search Steps

: Begin the search at the root node.**Start at the Root**:**Traverse the Tree**- If the target value is equal to the current node’s value, the node is found.
- If the target value is less than the current node’s value, move to the left child.
- If the target value is greater than the current node’s value, move to the right child.

: Continue this process until the target value is found or a NIL node is reached (indicating the value is not present in the tree).**Repeat**

## 3. Deletion

Deleting a node from a Red-Black Tree also involves a two-step process: performing the BST deletion, followed by fixing any violations that arise.

### Deletion Steps

: Remove the node using standard BST rules.**BST Deletion**:**Fix Double Black**- If a black node is deleted, a “double black” condition might arise, which requires specific fixes.

### Fixing Violations During Deletion

When a black node is deleted, we handle the double black issue based on the sibling’s color and the colors of its children:

: Rotate the parent and recolor the sibling and parent.**Case 1: Sibling is Red**:**Case 2: Sibling is Black**: Recolor the sibling and propagate the double black upwards.**Sub-case 2.1: Sibling’s children are black**:**Sub-case 2.2: At least one of the sibling’s children is red**: Perform a rotation on the parent and sibling, and recolor appropriately.**If the sibling’s far child is red**: Rotate the sibling and its child, then handle as above.**If the sibling’s near child is red**

## 4. Rotation

Rotations are fundamental operations in maintaining the balanced structure of a Red-Black Tree (RBT). They help to preserve the properties of the tree, ensuring that the longest path from the root to any leaf is no more than twice the length of the shortest path. Rotations come in two types:** left rotations **and

**right rotations.**### 1. Left Rotation

A left rotation at node 𝑥* x* moves 𝑥

*down to the left and its right child 𝑦*

*x**up to take 𝑥*

*y**’s place.*

*x*Before Rotation:
x
\
y
/ \
a b
After Left Rotation:
y
/ \
x b
/
a

**Left Rotation Steps:**

**Left Rotation Steps:**

- Set
to be the right child of*y*.*x* - Move
’s left subtree to*y*’s right subtree.*x* - Update the parent of
and*x*.*y* - Update
’s parent to point to*x*instead of*y*.*x* - Set
’s left child to*y*.*x* - Update
’s parent to*x*.*y*

**Pseudocode of Left Rotation:**

**Pseudocode of Left Rotation:**

// Utility function to perform left rotation
void leftRotate(Node* x)
{
Node* y = x->right;
x->right = y->left;
if (y->left != NIL) {
y->left->parent = x;
}
y->parent = x->parent;
if (x->parent == nullptr) {
root = y;
}
else if (x == x->parent->left) {
x->parent->left = y;
}
else {
x->parent->right = y;
}
y->left = x;
x->parent = y;
}

### 2. Right Rotation

A right rotation at node 𝑥* x* moves 𝑥

*down to the right and its left child 𝑦*

*x**up to take 𝑥*

*y**’s place.*

*x*Befor Right Rotation:
x
/
y
/ \
a b
After Right Rotation:
y
/ \
a x
/
b

**Right Rotation Steps:**

**Right Rotation Steps:**

- Set
to be the left child of**y**.**x** - Move
’s right subtree to*y*’s left subtree.*x* - Update the parent of
and**x**.**y** - Update
’s parent to point to*x*instead of**y**.**x** - Set
’s right child to*y*.*x* - Update
’s parent to*x*.*y*

**Pseudocode of Right Rotation:**

**Pseudocode of Right Rotation:**

// Utility function to perform right rotation
void rightRotate(Node* x)
{
Node* y = x->left;
x->left = y->right;
if (y->right != NIL) {
y->right->parent = x;
}
y->parent = x->parent;
if (x->parent == nullptr) {
root = y;
}
else if (x == x->parent->right) {
x->parent->right = y;
}
else {
x->parent->left = y;
}
y->right = x;
x->parent = y;
}

## When to Perform Rotations?

Rotations in Red-Black Trees are typically performed during insertions and deletions to maintain the properties of the tree. Below are the scenarios for rotations:

### 1. Fixing Violations after Insertion

When a new node is inserted, it is always colored red. This can create violations of Red-Black Tree properties, specifically:

- The root must be
.**black** nodes cannot have**Red**children.**red**

**Case Analysis for Fixing Insertions:**

**Case 1: Recoloring and Propagating Upwards**- If the parent and uncle of the new node are both
, recolor the parent and uncle to**red**, and the grandparent to**black**. Then, recursively apply the fix-up to the grandparent.**red**

- If the parent and uncle of the new node are both
**Case 2: Rotation and Recoloring**- If the new node’s uncle is
and the new node is the right child of a left child (or vice versa), perform a rotation to move the new node up and align it.**black** - If the new node’s uncle is
and the new node is the left child of a left child (or right of a right), perform a rotation and recolor the parent and grandparent to fix the violation.**black**

- If the new node’s uncle is

### 2. Fixing Violations after Deletion

After deletion, the tree might need fixing to restore properties:

- When a black node is removed, or a red node is replaced by a black node, a double-black situation can arise.

**Case Analysis for Fixing Deletions:**

**Case 1: Sibling is Red**- Recolor the sibling and the parent, and perform a rotation.

**Case 2: Sibling is Black with Black Children**- Recolor the sibling to red and move the problem up to the parent.

**Case 3: Sibling is Black with at least one Red Child**- Rotate and recolor to fix the double-black issue.

## Implementation of Red-Black Tree:

Here’s a detailed implementation of a Red-Black Tree including insertion, search, and rotation functions:

#include <iostream>
using namespace std;
// Node structure for the Red-Black Tree
struct Node {
int data;
string color;
Node *left, *right, *parent;
Node(int data)
: data(data)
, color("RED")
, left(nullptr)
, right(nullptr)
, parent(nullptr)
{
}
};
// Red-Black Tree class
class RedBlackTree {
private:
Node* root;
Node* NIL;
// Utility function to perform left rotation
void leftRotate(Node* x)
{
Node* y = x->right;
x->right = y->left;
if (y->left != NIL) {
y->left->parent = x;
}
y->parent = x->parent;
if (x->parent == nullptr) {
root = y;
}
else if (x == x->parent->left) {
x->parent->left = y;
}
else {
x->parent->right = y;
}
y->left = x;
x->parent = y;
}
// Utility function to perform right rotation
void rightRotate(Node* x)
{
Node* y = x->left;
x->left = y->right;
if (y->right != NIL) {
y->right->parent = x;
}
y->parent = x->parent;
if (x->parent == nullptr) {
root = y;
}
else if (x == x->parent->right) {
x->parent->right = y;
}
else {
x->parent->left = y;
}
y->right = x;
x->parent = y;
}
// Function to fix Red-Black Tree properties after
// insertion
void fixInsert(Node* k)
{
while (k != root && k->parent->color == "RED") {
if (k->parent == k->parent->parent->left) {
Node* u = k->parent->parent->right; // uncle
if (u->color == "RED") {
k->parent->color = "BLACK";
u->color = "BLACK";
k->parent->parent->color = "RED";
k = k->parent->parent;
}
else {
if (k == k->parent->right) {
k = k->parent;
leftRotate(k);
}
k->parent->color = "BLACK";
k->parent->parent->color = "RED";
rightRotate(k->parent->parent);
}
}
else {
Node* u = k->parent->parent->left; // uncle
if (u->color == "RED") {
k->parent->color = "BLACK";
u->color = "BLACK";
k->parent->parent->color = "RED";
k = k->parent->parent;
}
else {
if (k == k->parent->left) {
k = k->parent;
rightRotate(k);
}
k->parent->color = "BLACK";
k->parent->parent->color = "RED";
leftRotate(k->parent->parent);
}
}
}
root->color = "BLACK";
}
// Inorder traversal helper function
void inorderHelper(Node* node)
{
if (node != NIL) {
inorderHelper(node->left);
cout << node->data << " ";
inorderHelper(node->right);
}
}
// Search helper function
Node* searchHelper(Node* node, int data)
{
if (node == NIL || data == node->data) {
return node;
}
if (data < node->data) {
return searchHelper(node->left, data);
}
return searchHelper(node->right, data);
}
public:
// Constructor
RedBlackTree()
{
NIL = new Node(0);
NIL->color = "BLACK";
NIL->left = NIL->right = NIL;
root = NIL;
}
// Insert function
void insert(int data)
{
Node* new_node = new Node(data);
new_node->left = NIL;
new_node->right = NIL;
Node* parent = nullptr;
Node* current = root;
// BST insert
while (current != NIL) {
parent = current;
if (new_node->data < current->data) {
current = current->left;
}
else {
current = current->right;
}
}
new_node->parent = parent;
if (parent == nullptr) {
root = new_node;
}
else if (new_node->data < parent->data) {
parent->left = new_node;
}
else {
parent->right = new_node;
}
if (new_node->parent == nullptr) {
new_node->color = "BLACK";
return;
}
if (new_node->parent->parent == nullptr) {
return;
}
fixInsert(new_node);
}
// Inorder traversal
void inorder() { inorderHelper(root); }
// Search function
Node* search(int data)
{
return searchHelper(root, data);
}
};
int main()
{
RedBlackTree rbt;
// Inserting elements
rbt.insert(10);
rbt.insert(20);
rbt.insert(30);
rbt.insert(15);
// Inorder traversal
cout << "Inorder traversal:" << endl;
rbt.inorder(); // Output: 10 15 20 30
// Search for a node
cout << "\nSearch for 15: "
<< (rbt.search(15) != rbt.search(0))
<< endl; // Output: 1 (true)
cout << "Search for 25: "
<< (rbt.search(25) != rbt.search(0))
<< endl; // Output: 0 (false)
return 0;
}

## Advantages of Red-Black Trees:

Red-Black Trees are self-balancing, meaning they automatically maintain a balance between the heights of the left and right subtrees. This ensures that search, insertion, and deletion operations take O(log n) time in the worst case.**Balanced:**Due to their balanced structure, Red-Black Trees offer efficient operations. Search, insertion, and deletion all take O(log n) time in the worst case.**Efficient search, insertion, and deletion:**The rules for maintaining the Red-Black Tree properties are relatively simple and straightforward to implement.**Simple to implement:**Red-Black Trees are a popular choice for implementing various data structures, such as maps, sets, and priority queues.**Widely used:**

## Disadvantages of Red-Black Trees:

Compared to simpler balanced trees like AVL trees, Red-Black Trees have more complex insertion and deletion rules.**More complex than other balanced trees:**Maintaining the Red-Black Tree properties adds a small overhead to every insertion and deletion operation.**Constant overhead:**While efficient for most operations, Red-Black Trees might not be the best choice for applications where frequent insertions and deletions are required, as the constant overhead can become significant.**Not optimal for all use cases:**

## Applications of Red-Black Trees:

Red-Black Trees are often used to implement maps and sets, where efficient search, insertion, and deletion are crucial.**Implementing maps and sets:**Red-Black Trees can be used to implement priority queues, where elements are ordered based on their priority.**Priority queues:**Red-Black Trees are used in some file systems to manage file and directory structures.**File systems:**Red-Black Trees are sometimes used in in-memory databases to store and retrieve data efficiently.**In-memory databases:**Red-Black Trees can be used in graphics and game development for tasks like collision detection and pathfinding.**Graphics and game development:**

## Frequently Asked Questions (FAQs) on Red-Black Tree:

### 1. What is a Red-Black Tree?

A Red-Black Tree is a self-balancing binary search tree that maintains a balance between the heights of its left and right subtrees. This ensures that search, insertion, and deletion operations take O(log n) time in the worst case. Red-Black Trees are widely used in various applications where efficient data structures are required.

### 2. How does a Red-Black Tree maintain its balance?

Red-Black Trees maintain their balance by enforcing specific rules on the colors of nodes (RED or BLACK) and the relationships between them. These rules ensure that the tree remains balanced and that the height difference between the left and right subtrees is at most 1.

### 3. What are the advantages of using a Red-Black Tree?

Red-Black Trees are self-balancing, ensuring efficient search, insertion, and deletion operations.Balanced:They offer O(log n) time complexity for most operations.Efficient:The rules for maintaining Red-Black Tree properties are relatively straightforward.Simple to implement:They are a popular choice for implementing various data structures and algorithms.Widely used:

### 4. What are the disadvantages of using a Red-Black Tree?

- Compared to simpler balanced trees like AVL trees, Red-Black Trees have more complex insertion and deletion rules.
- Maintaining the Red-Black Tree properties adds a small overhead to every insertion and deletion operation.
- For applications with frequent insertions and deletions, other balanced tree structures might be more suitable.

### 5. What are some common applications of Red-Black Trees?

- Implementing maps and sets
- Priority queues
- File systems
- In-memory databases
- Graphics and game development (collision detection, pathfinding)

**Related Articles:**

**Related Articles:**

- Red-Black Tree definition & meaning in DSA
- Self-Balancing Binary Search Trees
- Red Black Tree vs AVL Tree
- What is the difference between Heap and Red-Black Tree?
- Insertion in Red-Black Tree
- Deletion in Red-Black Tree
- Red-Black Trees | Top-Down Insertion