FREE E LEARNING PLATFORM
☰ HOMEEXCEPTIONSOOPSJVMINTRO
SYLLABUS TUTORIALS FORUM
 

Red-Black Tree



Introduction

A Red-Black Tree (RBT) is a self-balancing Binary Search Tree (BST) in which every node is assigned either a Red or a Black colour. The colouring rules ensure that the height of the tree remains balanced after insertion and deletion operations.

Since the tree remains approximately balanced, searching, insertion and deletion operations can be performed efficiently in O(log n) time.

Why Do We Need a Red-Black Tree?

In a normal Binary Search Tree, inserting sorted data may create a skewed tree, causing search operations to take O(n) time. A Red-Black Tree automatically performs rotations and recolouring to keep the tree balanced.

Binary Search Tree Red-Black Tree
May become skewed. Always approximately balanced.
Worst Case : O(n) Worst Case : O(log n)
No balancing. Automatic balancing.

Properties of Red-Black Tree

Property Description
Property 1 Every node is either Red or Black.
Property 2 The root node is always Black.
Property 3 Every NULL leaf is considered Black.
Property 4 A Red node cannot have a Red child.
Property 5 Every path from a node to its descendant NULL nodes contains the same number of Black nodes.

Basic Structure


             20(B)

            /     \

        10(R)    30(R)

        /   \

     5(B) 15(B)

Figure 1 : Example of a Red-Black Tree

Real-Life Example

Suppose a large library stores millions of book records. Whenever a new book is added or removed, the database should remain balanced so that searching for any book remains fast. Red-Black Trees are widely used for maintaining such balanced data structures.

How Balancing is Performed?

Whenever a new node is inserted or an existing node is deleted, the Red-Black Tree checks whether any property has been violated. If necessary, it performs one or more of the following operations:

  • Recolouring of nodes.
  • Left Rotation.
  • Right Rotation.
  • Combination of rotation and recolouring.

Solved Example (Insertion)

Insert the values: 20, 10, 30, 15 into an empty Red-Black Tree.

Step Action
1 Insert 20 as Root (Black).
2 Insert 10 as Red child.
3 Insert 30 as Red child.
4 Insert 15. Perform recolouring to maintain Red-Black properties.

Tree After Insertion


             20(B)

            /     \

        10(B)    30(B)

            \

           15(R)

Figure 2 : Balanced Red-Black Tree after insertion

Working Principle

Whenever a new node is inserted, it is initially coloured Red. The algorithm then checks whether any Red-Black property has been violated. If a violation occurs, the tree is balanced using recolouring and tree rotations. This process continues until all Red-Black properties are satisfied.

Red-Black Tree Insertion Algorithm

Insert(Node) Step 1 : Insert the new node as in a Binary Search Tree. Step 2 : Colour the new node Red. Step 3 : If the parent is Black, No violation occurs. Step 4 : If the parent is Red, Check the colour of the Uncle. Step 5 : If the Uncle is Red, Perform Recolouring. Step 6 : If the Uncle is Black, Perform Left Rotation or Right Rotation. Step 7 : Continue until all Red-Black properties are restored. Step 8 : Colour the Root Black.

Left Rotation

A Left Rotation is performed when the right child becomes the new parent while maintaining the Binary Search Tree property. 


Before Rotation

        X

         \

          Y

         / \

        T1 T2


After Rotation

        Y

       / \

      X  T2

       \

       T1

Figure 3 : Left Rotation

Right Rotation

A Right Rotation is performed when the left child becomes the new parent while maintaining the Binary Search Tree property. 


Before Rotation

          Y

         /

        X

       / \

      T1 T2


After Rotation

        X

       / \

      T1  Y

         /

       T2

Figure 4 : Right Rotation

Complexity Analysis

Operation Time Complexity Explanation
Searching O(log n) Tree remains balanced.
Insertion O(log n) May require recolouring and rotations.
Deletion O(log n) Balancing operations maintain height.
Traversal O(n) Visits every node exactly once.
Space Complexity O(n) Storage for all tree nodes.

Advantages of Red-Black Tree

  • Automatically maintains a balanced tree.
  • Searching, insertion and deletion are performed in O(log n) time.
  • Requires fewer rotations than AVL Trees.
  • Suitable for applications involving frequent updates.
  • Widely used in system libraries and databases.

Limitations of Red-Black Tree

  • More difficult to implement than a Binary Search Tree.
  • Requires recolouring and rotation operations.
  • Slightly slower searching than AVL Trees because balancing is less strict.
  • Tree structure is more complex to understand.

Applications of Red-Black Tree

Application Description
Database Systems Efficient indexing and searching.
Operating Systems Memory management and process scheduling.
C++ STL Implementation of map, multimap, set and multiset.
Java Collections TreeMap and TreeSet internally use Red-Black Trees.
Compiler Design Efficient symbol table implementation.

Red-Black Tree vs AVL Tree

Red-Black Tree AVL Tree
Loosely balanced. Strictly balanced.
Fewer rotations. More rotations.
Insertion is generally faster. Searching is generally faster.
Preferred for frequent insertions and deletions. Preferred for search-intensive applications.
Used in TreeMap and STL Map. Used in database and memory indexing.

Red-Black Tree vs Binary Search Tree

Red-Black Tree Binary Search Tree
Self-balancing. May become skewed.
Worst Case : O(log n) Worst Case : O(n)
Uses colours and rotations. No balancing mechanism.
Height remains nearly balanced. Height depends on insertion order.

💡 Remember This

New Node → Red

Violation?

Recolour or Rotate

Root Always Black

Important Points

  • Every node is either Red or Black.
  • The Root is always Black.
  • No Red node can have a Red child.
  • Every path contains the same number of Black nodes.
  • Searching, insertion and deletion require O(log n) time.
  • Balancing is performed using rotations and recolouring.

💼 Interview Corner

  • Why is a Red-Black Tree called a self-balancing tree?
  • State the five properties of a Red-Black Tree.
  • Differentiate between Red-Black Tree and AVL Tree.
  • Why are rotations required?
  • Which Java Collection classes internally use a Red-Black Tree?

🎓 AKTU / Placement Tip

University examinations and placement interviews frequently ask students to explain the five properties of a Red-Black Tree, perform insertion with recolouring and rotations, compare it with AVL Trees, and state its practical applications.

Summary

A Red-Black Tree is a self-balancing Binary Search Tree that maintains efficient searching, insertion and deletion operations by using node colours, recolouring and tree rotations. Its balancing rules ensure that the height of the tree remains approximately balanced, resulting in O(log n) time complexity for most operations. Due to its excellent performance, it is widely used in databases, operating systems and programming language libraries.







Copyright 2020 by Noidatut. All Rights Reserved.

Noidatut.com