Red-Black Tree Implementation in Bash

This document explains how to implement a simplified Red-Black Tree using Bash. A Red-Black Tree is a self-balancing binary search tree where each node contains an extra bit for denoting the color of the node, either red or black. This ensures the tree remains balanced during insertions and deletions, allowing for efficient search, insertion, and deletion operations.

Program Structure

The program is structured into several key functions:

• initialize_tree: Initializes the Red-Black Tree.
• rotate_left: Performs a left rotation around a node.
• rotate_right: Performs a right rotation around a node.
• insert: Inserts a key into the Red-Black Tree.
• fix_insert: Fixes any violations of Red-Black Tree properties after insertion.
• search: Searches for a key in the Red-Black Tree.

Implementation

#!/bin/bash

# Initialize the Red-Black Tree
initialize_tree() {
    NIL_LEAF="nil"  # Sentinel node representing null leaf
    root=$NIL_LEAF
    color[$NIL_LEAF]="black"
}

# Left rotation
rotate_left() {
    local x=$1
    local y=${right[$x]}
    right[$x]=${left[$y]}
    if [ "${left[$y]}" != "$NIL_LEAF" ]; then
        parent[${left[$y]}]=$x
    fi
    parent[$y]=${parent[$x]}
    if [ "${parent[$x]}" == "$NIL_LEAF" ]; then
        root=$y
    elif [ "$x" == "${left[${parent[$x]}]}" ]; then
        left[${parent[$x]}]=$y
    else
        right[${parent[$x]}]=$y
    fi
    left[$y]=$x
    parent[$x]=$y
}

# Right rotation
rotate_right() {
    local y=$1
    local x=${left[$y]}
    left[$y]=${right[$x]}
    if [ "${right[$x]}" != "$NIL_LEAF" ]; then
        parent[${right[$x]}]=$y
    fi
    parent[$x]=${parent[$y]}
    if [ "${parent[$y]}" == "$NIL_LEAF" ]; then
        root=$x
    elif [ "$y" == "${right[${parent[$y]}]}" ]; then
        right[${parent[$y]}]=$x
    else
        left[${parent[$y]}]=$x
    fi
    right[$x]=$y
    parent[$y]=$x
}

# Fix violations after insertion
fix_insert() {
    local z=$1
    while [ "${color[${parent[$z]}]}" == "red" ]; do
        if [ "${parent[$z]}" == "${left[${parent[${parent[$z]}]}]}" ]; then
            y=${right[${parent[${parent[$z]}]}]}
            if [ "${color[$y]}" == "red" ]; then
                color[${parent[$z]}]="black"
                color[$y]="black"
                color[${parent[${parent[$z]}]}]="red"
                z=${parent[${parent[$z]}]}
            else
                if [ "$z" == "${right[${parent[$z]}]}" ]; then
                    z=${parent[$z]}
                    rotate_left $z
                fi
                color[${parent[$z]}]="black"
                color[${parent[${parent[$z]}]}]="red"
                rotate_right ${parent[${parent[$z]}]}
            fi
        else
            y=${left[${parent[${parent[$z]}]}]}
            if [ "${color[$y]}" == "red" ]; then
                color[${parent[$z]}]="black"
                color[$y]="black"
                color[${parent[${parent[$z]}]}]="red"
                z=${parent[${parent[$z]}]}
            else
                if [ "$z" == "${left[${parent[$z]}]}" ]; then
                    z=${parent[$z]}
                    rotate_right $z
                fi
                color[${parent[$z]}]="black"
                color[${parent[${parent[$z]}]}]="red"
                rotate_left ${parent[${parent[$z]}]}
            fi
        fi
    done
    color[$root]="black"
}

# Insert a new key into the Red-Black Tree
insert() {
    local z=$1
    local y=$NIL_LEAF
    local x=$root

    while [ "$x" != "$NIL_LEAF" ]; do
        y=$x
        if [ "$z" -lt "$x" ]; then
            x=${left[$x]}
        else
            x=${right[$x]}
        fi
    done

    parent[$z]=$y
    if [ "$y" == "$NIL_LEAF" ]; then
        root=$z
    elif [ "$z" -lt "$y" ]; then
        left[$y]=$z
    else
        right[$y]=$z
    fi

    left[$z]=$NIL_LEAF
    right[$z]=$NIL_LEAF
    color[$z]="red"

    fix_insert $z
}

# Search for a key in the Red-Black Tree
search() {
    local node=$root
    local key=$1

    while [ "$node" != "$NIL_LEAF" ]; do
        if [ "$key" == "$node" ]; then
            echo "Key $key found in the Red-Black Tree."
            return
        elif [ "$key" -lt "$node" ]; then
            node=${left[$node]}
        else
            node=${right[$node]}
        fi
    done

    echo "Key $key not found in the Red-Black Tree."
}

# Example usage
initialize_tree

insert 10
insert 20
insert 30
insert 15
insert 25
insert 5

# Searching for keys
search 15
search 100
    

Explanation

The program implements a basic Red-Black Tree with the following components:

Initialization

The initialize_tree function sets up an empty Red-Black Tree, represented by the root node and a sentinel node NIL_LEAF that represents all null leaves in the tree. The root initially points to NIL_LEAF.

Rotations

The rotate_left and rotate_right functions perform left and right rotations around a given node. These rotations are fundamental to maintaining the Red-Black Tree’s balance during insertions and deletions.

Inserting Keys

The insert function inserts a new key into the Red-Black Tree. The key is inserted as a red node, and the fix_insert function is called to restore the Red-Black Tree properties (e.g., no two consecutive red nodes and equal black heights). This may involve rotations and recoloring of nodes.

Fixing Insertions

The fix_insert function is responsible for correcting any violations of the Red-Black Tree properties after a new node is inserted. This involves checking the color of the node’s parent and adjusting the tree accordingly using rotations and recoloring.

Searching for Keys

The search function traverses the Red-Black Tree to find a specific key. It returns a message indicating whether the key is found or not.

Example Usage

The example usage section demonstrates initializing the Red-Black Tree, inserting several keys, and searching for specific keys. The program outputs whether each key is found or not.

Conclusion

This Bash implementation of a Red-Black Tree provides a basic understanding of how to maintain a balanced binary search tree using rotations and color properties. Red-Black Trees are commonly used in applications requiring efficient search, insertion, and deletion operations, such as in databases and file systems.