AVL Tree Implementation in Bash

This document explains how to implement a simplified AVL Tree using Bash. An AVL Tree is a self-balancing binary search tree, where the height of the two child subtrees of any node differs by at most one. If at any time they differ by more than one, rebalancing is performed to restore this property.

Program Structure

The program is structured into several key functions:

• initialize_tree: Initializes the AVL Tree.
• rotate_left: Performs a left rotation around a node.
• rotate_right: Performs a right rotation around a node.
• get_height: Returns the height of a node.
• get_balance: Calculates the balance factor of a node.
• insert: Inserts a key into the AVL Tree and balances it.
• search: Searches for a key in the AVL Tree.

Implementation

#!/bin/bash

# Initialize the AVL Tree
initialize_tree() {
    NIL="nil"
    root=$NIL
    height[$NIL]=0
}

# Left rotation
rotate_left() {
    local x=$1
    local y=${right[$x]}
    right[$x]=${left[$y]}
    left[$y]=$x
    update_height $x
    update_height $y
    echo $y
}

# Right rotation
rotate_right() {
    local y=$1
    local x=${left[$y]}
    left[$y]=${right[$x]}
    right[$x]=$y
    update_height $y
    update_height $x
    echo $x
}

# Get height of a node
get_height() {
    local node=$1
    echo ${height[$node]:-0}
}

# Update height of a node
update_height() {
    local node=$1
    local left_height=$(get_height ${left[$node]})
    local right_height=$(get_height ${right[$node]})
    height[$node]=$((1 + (left_height > right_height ? left_height : right_height)))
}

# Get balance factor of a node
get_balance() {
    local node=$1
    local left_height=$(get_height ${left[$node]})
    local right_height=$(get_height ${right[$node]})
    echo $((left_height - right_height))
}

# Insert a key into the AVL Tree
insert() {
    local node=$1
    local key=$2

    if [ "$node" == "$NIL" ]; then
        echo $key
        return
    fi

    if [ "$key" -lt "$node" ]; then
        left[$node]=$(insert ${left[$node]} $key)
    else
        right[$node]=$(insert ${right[$node]} $key)
    fi

    update_height $node

    local balance=$(get_balance $node)

    if [ "$balance" -gt 1 ]; then
        if [ "$key" -lt "${left[$node]}" ]; then
            echo $(rotate_right $node)
        else
            left[$node]=$(rotate_left ${left[$node]})
            echo $(rotate_right $node)
        fi
    elif [ "$balance" -lt -1 ]; then
        if [ "$key" -gt "${right[$node]}" ]; then
            echo $(rotate_left $node)
        else
            right[$node]=$(rotate_right ${right[$node]})
            echo $(rotate_left $node)
        fi
    else
        echo $node
    fi
}

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

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

    echo "Key $key not found in the AVL Tree."
}

# Example usage
initialize_tree

root=$(insert $root 10)
root=$(insert $root 20)
root=$(insert $root 30)
root=$(insert $root 40)
root=$(insert $root 50)
root=$(insert $root 25)

# Searching for keys
search 20
search 60
    

Explanation

The program implements a basic AVL Tree with the following components:

Initialization

The initialize_tree function sets up an empty AVL Tree, with a sentinel node NIL representing all null leaves. The root initially points to NIL.

Rotations

The rotate_left and rotate_right functions perform left and right rotations around a given node. These rotations are essential to maintaining the balance of the AVL Tree after insertions.

Height Calculation

The get_height and update_height functions manage the height of each node in the tree. The height is used to calculate the balance factor, which determines if the tree is balanced or requires rotation.

Balance Factor Calculation

The get_balance function calculates the balance factor of a node, which is the difference between the heights of its left and right subtrees. This factor is used to decide whether rotations are needed during insertion.

Inserting Keys

The insert function inserts a new key into the AVL Tree, recursively placing it in the correct position. After insertion, the tree is rebalanced if necessary, using rotations based on the balance factor.

Searching for Keys

The search function traverses the AVL Tree to find a specific key, returning a message indicating whether the key is found or not.

Example Usage

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

Conclusion

This Bash implementation of an AVL Tree provides a simple yet effective way to maintain a balanced binary search tree. AVL Trees are widely used in scenarios where quick lookup, insertion, and deletion operations are essential, such as in databases and memory management systems.