Introduction To Red-Black Trees

Properties of Red-Black Tree 

The properties of Red-Black trees are :

1. Node Color: Every node in a Red-Black tree is either red or black. This color property is used to ensure the balance of the tree.

2. Root Color: The root node of the tree is always black. This property ensures that the root is always at the top of the tree and has no parent.

3. Leaf Nodes: All leaf nodes (NIL or null nodes) are considered black. These nodes do not contain any data and serve as a sentinel to mark the end of a path.

4. Red Node Children: If a node is red, both its children must be black. This property ensures that no two adjacent nodes are red, which helps maintain the balance of the tree.

5. Black Height: Every path from a node to any of its descendant leaf nodes must contain the same number of black nodes. This property is known as the "black height" of the node and ensures that the tree remains balanced.

These properties work together to keep the Red-Black Tree balanced, ensuring the longest path is at most twice the shortest path. This balance helps maintain logarithmic time complexity for insertion, deletion, and search.

When a node is inserted or deleted, the tree may violate its properties. To fix this, it uses rotations and recoloring. For instance, if two consecutive red nodes appear, a rotation and recoloring correct the issue. Similarly, if the black height changes, the tree adjusts to restore balance.

Basic Operations on Red-Black Tree

1. Insertion in a Red-Black Tree :When inserting a new node, it is always added as a red node to maintain balance as much as possible. However, this may cause violations of Red-Black properties, particularly the rule that two consecutive red nodes cannot exist. To fix violations, the tree undergoes:

• Recoloring – If the parent and uncle are both red, they are recolored black, and the grandparent turns red.
• Rotation – If the uncle is black, the tree performs either left or right rotation (single or double) to maintain balance.

Example: If inserting a red node creates two consecutive red nodes, a rotation and recoloring restore balance.
 

2. Deletion in a Red-Black Tree: Removing a node can cause an imbalance, especially if the node being deleted is black (since it affects the black height). The deletion process follows these steps:

• Replace the node – If the node has two children, it is replaced with its in-order successor or predecessor.
• Fix double black problem – If deletion creates an imbalance (extra black height), the tree uses recoloring and rotations to restore balance.

Example: If a black node is removed and its child is red, the child is recolored black. If it was already black, additional rotations and recoloring are needed.
 

3. Search in a Red-Black Tree: Searching in a Red-Black Tree follows the same approach as in a Binary Search Tree (BST):

1. Start from the root.
2. Compare the key with the current node:
   • If the key is smaller, move to the left subtree.
   • If the key is larger, move to the right subtree.
   • If the key matches, return the node.

Since the tree remains balanced, the worst-case search time is O(log n).

Example: If searching for a value X, traverse the tree based on comparisons until X is found or a leaf node is reached.

Example of Red-Black Tree

Let's see an example of a Red-Black tree and how it maintains its balance while inserting elements. We'll start with an empty tree and insert the following elements in order: 10, 20, 30, 40, 50, 60, 70, 80.

1. Insert 10:
  - The tree is empty, so 10 becomes the root node and is colored black.
     10(B)

2. Insert 20:
  - 20 is inserted as the right child of 10 and is colored red.

     10(B)
       \
       20(R)

3. Insert 30:
  - 30 is inserted as the right child of 20 and is colored red.
  - This violates property 4 (a red node cannot have a red child), so we perform a left rotation on 10 and recolor the nodes.

     20(B)
    /    \
 10(R)  30(R)
 

4. Insert 40:
  - 40 is inserted as the right child of 30 and is colored red.

      20(B)
    /     \
 10(R)    30(R)
            \
            40(R)

5. Insert 50:
  - 50 is inserted as the right child of 40 and is colored red.
  - This violates property 4, so we perform a left rotation on 30 and recolor the nodes.

      20(B)
    /     \
 10(R)    40(B)
         /    \
      30(R)  50(R)
 

6. Insert 60:
  - 60 is inserted as the right child of 50 and is colored red.
  - This violates property 4, so we perform a left rotation on 20, a right rotation on 40, and recolor the nodes.

      40(B)
    /      \
 20(R)     50(B)
 /   \        \
10(B) 30(B)    60(R)

7. Insert 70 and 80:
  - 70 is inserted as the right child of 60 and is colored red.
  - 80 is inserted as the right child of 70 and is colored red.
  - This violates property 4, so we perform a left rotation on 50, a right rotation on 60, and recolor the nodes.

        40(B)
     /        \
  20(B)       60(B)
  /   \      /    \
10(B) 30(B) 50(B) 70(B)
                     \
                     80(R)

In this example, we can see how the Red-Black tree maintains its balance by performing rotations and recoloring nodes whenever an insertion violates one of the Red-Black tree properties. The resulting tree has a balanced structure, ensuring efficient operations with a time complexity of O(log n).

Rules for Red-Black Tree

1. A node can have Either Red colour or Black Colour.
2. Root nodes always have Black Colour.
3. No two Red nodes can be adjacent to each other.
4. The path from any Node to any descendant null node has the same count of black nodes.

Why do we Use Red Black Trees?

Most of the best operations (e.G.,  max, min, insert, delete.. Etc) take o(h) time in which (h) is the height of the Bst. The cost of these operations may also emerge as o(n) for a skewed binary tree. If we are sure that the height of the binary tree stays o(log n) after each insertion and deletion, then we can guarantee an upper certain of o(log n) for all these operations. The height of a red-black tree is constantly o(log n), wherein n is the number of nodes inside the tree.

Here “n” represents the total no of the elements that are present in the red Black Tree.

Types of Rotations

There are two types of rotations:

1. Left Rotation: Performed when the right child of a node is red, and its left child is black.

2. Right Rotation: Performed when the left child of a node is red, and its left child's left child is also red.

Recoloring involves changing the color of nodes to maintain the Red-Black tree properties. It is done in conjunction with rotations to rebalance the tree.

The time complexity of basic operations (insertion, deletion, and search) in a Red-Black tree is O(log n), where n is the number of nodes in the tree. This is because the tree maintains its balance, ensuring that the height of the tree is always logarithmic.

Red-Black trees are widely used in various applications and libraries that require efficient sorting, searching, and maintaining ordered data. 

Some common examples are:

1. The Java TreeMap and TreeSet classes
2. The C++ STL map and set associative containers
3. The Linux kernel's Completely Fair Scheduler (CFS)
4. The Nginx HTTP server's timer implementation

When to Perform Rotations?

Rotations in Red-Black trees are performed to maintain balance and ensure the Red-Black tree properties are satisfied. There are two main scenarios when rotations are necessary:

1. Insertion: When inserting a new node, if the parent of the new node is red and the uncle is black, perform a rotation to balance the tree. The specific rotation (left or right) depends on the arrangement of the nodes.

2. Deletion: When deleting a black node, the tree may become unbalanced. Perform rotations along with recoloring to restore the Red-Black tree properties. The specific rotations required depend on the structure of the tree and the color of the sibling of the deleted node.

Rotations are always performed in conjunction with recoloring to maintain the Red-Black tree properties. The goal is to ensure that the tree remains balanced and no red node has a red parent or child.

Advantages

1. Guaranteed logarithmic time complexity for basic operations (insertion, deletion, search)
2. Maintains balance automatically, preventing the tree from becoming skewed
3. Efficient memory utilization compared to other self-balancing trees like AVL trees
4. Used as the underlying data structure for many standard library implementations, such as Java's TreeMap and C++'s map

Disadvantages

1. Complex implementation compared to other self-balancing trees
2. Requires extra storage for the color of each node
3. Slower than AVL trees for lookup-intensive applications due to the slightly higher average tree height
4. It may not be the best choice if the data is known to be mostly in sorted order, as the overhead of maintaining balance may outweigh the benefits

Application

1. It is used in CPU scheduling in an operating system like Linux.
2. Mysql also uses the Red-Black Tree for storing the indexes of tables.
3. They are also used in the k-means clustering algorithm for reducing complexity.

Frequently Asked Questions:

Are red-black trees 2/3 trees?

Red-black trees are not 2-3 trees but they are closely related. Both maintain a balanced state using different methods, with red-black trees using color properties to ensure balance.

Why do we use the Red-black Tree over the AVL tree?

In every case, the time complexity of the Red-black Tree is Less than the AVL tree.

What is the Time complexity of the Red-Black Tree for insertion, deletion, and searching?

Time complexity for every case is o(log(n));

How does searching take place in Red-Black Tree?

Searching in the red-black Tree is similar to searching in the AVL tree.

Conclusion

In this article, we talked about red-black trees and compared them to AVL trees. We looked into their advantages, disadvantages, implementations, and important properties. This comparison highlighted how each structure addresses balance and efficiency in data organization and retrieval, which provides valuable insights into choosing the appropriate tree type based on specific application requirements.

Recommended problems -

• Zig Zag Tree Traversal 
• Preorder Traversal
• Largest BST In Binary Tree