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. By enforcing these rules, the tree ensures that the longest path from the root to a leaf is no more than twice the length of the shortest path. This balance is crucial for maintaining the logarithmic time complexity of basic operations, such as insertion, deletion, and search.

When a node is inserted or deleted, the tree may violate one or more of these properties. In such cases, the tree performs rotations and recoloring of nodes to restore the balance and maintain the Red-Black tree properties.

For example, if a red node is inserted as a child of another red node, violating property 4, the tree will perform a rotation and recolor the nodes to ensure that the property is satisfied. Similarly, if an insertion or deletion causes the black height of a path to change, violating property 5, the tree will perform rotations and recoloring to restore the balance and maintain the same black height for all paths.

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 descendants 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 element that is present in the red Black Tree.

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).

Comparison B/w Red Black tree and AVL tree:

The AVL tree is more balanced than the Red-black tree, but when the deletion of the insertion operation is performed, the AVL tree requires more rotations. So when an operation requires frequent insertion and deletion then a Red-black tree is preferred more than the AVL tree to reduce time complexity.

How does a Red-Black Tree ensure balance?

The following is not a Red-Black tree because the chain of three-nodes is not possible.

The following is a red-black tree with three keys.

Facts about Red-Black tree:

1. The black height of the tree is the total count of black nodes on a path from the base node to a leaf node. Leaf nodes also are counted as black nodes. So, the red-black tree of height (h) has the black height >= h/2.
2. The height of a red-black tree with n nodes is h<= 2 log2(n + 1)
3. All bottom leaf nodes are black.
4. The red-Black tree is the remarkable variety of the Binary Tree.
5. No of Black Nodes is defined as the no of black nodes from the nodes to the given node that was no of an ancestor.

Black Height of Red-Black Tree:

The count of nodes from a node to its farthest descendant leaf is not quite twice because of the number of nodes to the closest descendant leaf.

Height h of red-black Tree is >=h/2;

Note: Red-Black Tree which has a height h and nodes count(n) has height<= 2Log2(n+1);

Searching in Red Black Tree:

Since the red-black tree is a special case of the binary tree, searching is similar to binary tree searching.

Algorithm:

For more refer coding ninjas tree article.

Example

Search 11 in the given Tree

Solutions:

Basic Operations on Red-Black Tree:

1. Insertion
Insertion in a Red-Black tree follows these steps:
1. Insert the new node as you would in a standard binary search tree.
2. Color the new node red.
3. If the parent of the new node is black, the tree is still valid.
4. If the parent is red, check the color of the uncle (the sibling of the parent).
 -: If the uncle is red, recolor the parent, uncle, and grandparent, and then repeat step 3 with the grandparent as the new node.
 -: If the uncle is black, perform rotations and recoloring to balance the tree.

2. Deletion
Deletion in a Red-Black tree is more complex than insertion and work in below mentioned steps:
1. Delete the node as you would in a standard binary search tree.
2. If the deleted node is black, the tree might become unbalanced. Perform rotations and recoloring to restore the Red-Black tree properties.

3. Search
Searching in a Red-Black tree is the same as in a standard binary search tree. The color of the nodes does not affect the search operation.

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.

Implementation of Red-Black Tree:

Implementing a Red-Black tree involves creating a Node class with properties for the key, color, left child, right child, and parent. The Red-Black tree class should have methods for insertion, deletion, and search.

The insertion method follows the steps mentioned earlier, inserting the new node as in a standard binary search tree, coloring it red, and then checking for violations of the Red-Black tree properties. If violations occur, perform the necessary rotations and recoloring.

The deletion method starts by deleting the node as in a standard binary search tree. If the deleted node is black, the tree may become unbalanced. The algorithm then performs a series of rotations and recoloring operations to restore the Red-Black tree properties.

The search method is the same as in a standard binary search tree, comparing the keys and traversing the tree accordingly.

Rotations (left and right) and recoloring are helper methods used by the insertion and deletion methods to maintain the balance of the tree.

Advantages of Red-Black Trees

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 of Red-Black Trees

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