Balanced Trees

Balanced Trees

Balanced trees are a category of data structures that maintain a balanced height across their nodes, ensuring that operations such as search, insertion, and deletion can be performed efficiently. The primary goal of a balanced tree is to minimize the height of the tree to guarantee logarithmic time complexity for these operations.

Key Characteristics

1. Height-Balanced: A balanced tree ensures that the height of the left and right subtrees of any node differ by no more than a certain factor, typically one. This is crucial for maintaining performance.

2. Logarithmic Time Complexity: Most operations, including search, insert, and delete, can be performed in $O(\log n)$ time, where $n$ is the number of nodes in the tree.

3. Self-Balancing: Balanced trees automatically adjust their structure during insertions and deletions to maintain balance.

Common Types of Balanced Trees

1. AVL Trees:

   • Named after inventors Adelson-Velsky and Landis.
   • Each node maintains a balance factor (the difference in height between the left and right subtrees).
   • Requires rotations to maintain balance after insertions or deletions.

2. Red-Black Trees:

   • Each node is colored either red or black.
   • The tree satisfies specific properties that ensure balanced height and structure.
   • Operations involve color changes and rotations to maintain balance.

3. B-Trees:

   • Generalized balanced search trees used in databases and file systems.
   • Nodes can have multiple keys and children.
   • B-trees remain balanced through a set of rules about node filling and splitting.

Example: AVL Tree

Let’s look at an implementation of an AVL Tree, focusing on insertion and rotation to maintain balance.

AVL Tree Implementation

#include <iostream>
using namespace std;

struct Node {
    int data;
    Node* left;
    Node* right;
    int height;

    Node(int val) : data(val), left(nullptr), right(nullptr), height(1) {}
};

class AVLTree {
private:
    Node* root;

    int getHeight(Node* node) {
        return node ? node->height : 0;
    }

    int getBalance(Node* node) {
        return node ? getHeight(node->left) - getHeight(node->right) : 0;
    }

    Node* rotateRight(Node* y) {
        Node* x = y->left;
        Node* T2 = x->right;

        // Perform rotation
        x->right = y;
        y->left = T2;

        // Update heights
        y->height = max(getHeight(y->left), getHeight(y->right)) + 1;
        x->height = max(getHeight(x->left), getHeight(x->right)) + 1;

        return x; // New root
    }

    Node* rotateLeft(Node* x) {
        Node* y = x->right;
        Node* T2 = y->left;

        // Perform rotation
        y->left = x;
        x->right = T2;

        // Update heights
        x->height = max(getHeight(x->left), getHeight(x->right)) + 1;
        y->height = max(getHeight(y->left), getHeight(y->right)) + 1;

        return y; // New root
    }

    Node* insert(Node* node, int key) {
        if (!node) return new Node(key);

        if (key < node->data)
            node->left = insert(node->left, key);
        else if (key > node->data)
            node->right = insert(node->right, key);
        else // Duplicate keys not allowed
            return node;

        // Update height
        node->height = 1 + max(getHeight(node->left), getHeight(node->right)));

        // Get balance factor
        int balance = getBalance(node);

        // Perform rotations if needed
        // Left Left Case
        if (balance > 1 && key < node->left->data)
            return rotateRight(node);

        // Right Right Case
        if (balance < -1 && key > node->right->data)
            return rotateLeft(node);

        // Left Right Case
        if (balance > 1 && key > node->left->data) {
            node->left = rotateLeft(node->left);
            return rotateRight(node);
        }

        // Right Left Case
        if (balance < -1 && key < node->right->data) {
            node->right = rotateRight(node->right);
            return rotateLeft(node);
        }

        return node; // Return unchanged node
    }

    void inOrder(Node* node) {
        if (node) {
            inOrder(node->left);
            cout << node->data << " ";
            inOrder(node->right);
        }
    }

public:
    AVLTree() : root(nullptr) {}

    void insert(int key) {
        root = insert(root, key);
    }

    void inOrder() {
        inOrder(root);
        cout << endl;
    }
};

int main() {
    AVLTree tree;
    tree.insert(10);
    tree.insert(20);
    tree.insert(30); // Causes a left rotation

    cout << "In-order Traversal: ";
    tree.inOrder(); // Output: 10 20 30

    return 0;
}

Explanation of the Code

1. Node Structure: Each node contains data, pointers to left and right children, and the height of the node.
2. AVLTree Class:
   • Height and Balance: Functions to get the height of a node and calculate its balance factor.
   • Rotations: Methods for right and left rotations to maintain balance.
   • Insert Function: Recursively inserts a new key and performs rotations if the tree becomes unbalanced.
   • In-Order Traversal: Prints the keys in sorted order.

Complexity Analysis

• Search: $O(\log n)$
• Insertion: $O(\log n)$
• Deletion: $O(\log n)$
• Space Complexity: $O(n)$ for storing nodes.

Applications of Balanced Trees

1. Databases: Used in indexing and quick retrieval of records.
2. Memory Management: Used in systems that manage free and occupied memory spaces.
3. Dynamic Sets: Implemented in various data structures for dynamic set operations.

Conclusion

Balanced trees, such as AVL and Red-Black trees, are essential for maintaining efficient performance in dynamic data management. By keeping the tree balanced, they ensure that operations remain efficient, making them invaluable in various applications, particularly in databases and systems requiring quick data retrieval. Understanding balanced trees equips you with the tools to design efficient algorithms and data structures.