Red Black Tree: Definition, How It Works, and Usage

A red black tree is a type of self-balancing binary search tree where each node has a color (red or black) to ensure the tree remains balanced during insertions and deletions. This balance guarantees operations like search, insert, and delete run efficiently in O(log n) time.

How It Works

A red black tree keeps itself balanced by coloring each node either red or black and following specific rules. These rules prevent the tree from becoming too tall on one side, which would slow down operations.

Think of it like organizing books on a shelf where some books are marked red and others black. The rules ensure that no path from the top to the bottom has two red books in a row and that every path has the same number of black books. This way, the shelf stays balanced and easy to search through.

When you add or remove a node, the tree may temporarily break these rules. The tree then fixes itself by changing colors and rotating parts of the tree, similar to rearranging books to keep the shelf balanced.

Example

This example shows how to insert values into a red black tree and print the tree in order.

python

class Node:
    def __init__(self, data, color='red'):
        self.data = data
        self.color = color  # 'red' or 'black'
        self.left = None
        self.right = None
        self.parent = None

class RedBlackTree:
    def __init__(self):
        self.NIL = Node(None, color='black')
        self.root = self.NIL

    def insert(self, key):
        new_node = Node(key)
        new_node.left = self.NIL
        new_node.right = self.NIL
        parent = None
        current = self.root

        while current != self.NIL:
            parent = current
            if new_node.data < current.data:
                current = current.left
            else:
                current = current.right

        new_node.parent = parent
        if parent is None:
            self.root = new_node
        elif new_node.data < parent.data:
            parent.left = new_node
        else:
            parent.right = new_node

        new_node.color = 'red'
        self.fix_insert(new_node)

    def fix_insert(self, node):
        while node != self.root and node.parent.color == 'red':
            if node.parent == node.parent.parent.left:
                uncle = node.parent.parent.right
                if uncle.color == 'red':
                    node.parent.color = 'black'
                    uncle.color = 'black'
                    node.parent.parent.color = 'red'
                    node = node.parent.parent
                else:
                    if node == node.parent.right:
                        node = node.parent
                        self.left_rotate(node)
                    node.parent.color = 'black'
                    node.parent.parent.color = 'red'
                    self.right_rotate(node.parent.parent)
            else:
                uncle = node.parent.parent.left
                if uncle.color == 'red':
                    node.parent.color = 'black'
                    uncle.color = 'black'
                    node.parent.parent.color = 'red'
                    node = node.parent.parent
                else:
                    if node == node.parent.left:
                        node = node.parent
                        self.right_rotate(node)
                    node.parent.color = 'black'
                    node.parent.parent.color = 'red'
                    self.left_rotate(node.parent.parent)
        self.root.color = 'black'

    def left_rotate(self, x):
        y = x.right
        x.right = y.left
        if y.left != self.NIL:
            y.left.parent = x
        y.parent = x.parent
        if x.parent is None:
            self.root = y
        elif x == x.parent.left:
            x.parent.left = y
        else:
            x.parent.right = y
        y.left = x
        x.parent = y

    def right_rotate(self, y):
        x = y.left
        y.left = x.right
        if x.right != self.NIL:
            x.right.parent = y
        x.parent = y.parent
        if y.parent is None:
            self.root = x
        elif y == y.parent.right:
            y.parent.right = x
        else:
            y.parent.left = x
        x.right = y
        y.parent = x

    def inorder_helper(self, node):
        if node != self.NIL:
            self.inorder_helper(node.left)
            print(f'{node.data} ({node.color})', end=' ')
            self.inorder_helper(node.right)

    def inorder(self):
        self.inorder_helper(self.root)
        print()

# Usage example
rbt = RedBlackTree()
rbt.insert(10)
rbt.insert(20)
rbt.insert(30)
rbt.insert(15)
rbt.inorder()

Output

10 (black) 15 (red) 20 (black) 30 (red) 

When to Use

Use a red black tree when you need a data structure that keeps data sorted and allows fast search, insert, and delete operations. It is especially useful when you expect many insertions and deletions and want to avoid slowdowns caused by unbalanced trees.

Common real-world uses include database indexing, memory management in operating systems, and implementing associative arrays or sets where balanced search trees are preferred over simpler structures.

Key Points

• A red black tree is a balanced binary search tree with nodes colored red or black.
• It maintains balance using rules about node colors and rotations during insertions and deletions.
• This balance ensures operations run in logarithmic time.
• It is widely used in systems requiring efficient dynamic data storage and retrieval.

Key Takeaways

A red black tree keeps a binary search tree balanced using red and black node colors and specific rules.

It guarantees efficient search, insert, and delete operations in O(log n) time.

Balancing is maintained by recoloring nodes and rotating parts of the tree after changes.

It is ideal for applications needing fast dynamic data access with frequent updates.

Understanding rotations and color rules is key to implementing and using red black trees.