The World of Tree Data Structures: Self-Balancing Trees

The Challenges of Maintaining Balance in Binary Search Trees

Why BSTs Can Become Unbalanced

1. Insertion Order: The sequence in which elements are inserted into a BST significantly affects its shape. If elements are inserted in a sorted order (either ascending or descending), the tree can degenerate into a linked list. This results in poor performance for search, insertion, and deletion operations, as the time complexity can degrade to O(n).

2. Unbalanced Insertions: When elements are inserted randomly, some subtrees may become deeper than others. Without rebalancing, this uneven growth can lead to inefficient operations, as the tree's height may increase disproportionately.

3. Lack of Rotation: Unlike self-balancing trees, standard BSTs do not automatically perform rotations to maintain balance. Rotations, such as left or right rotations, are essential for keeping the tree height balanced and ensuring efficient search times.

4. Deletion Complexity: Removing nodes from a BST can be complex, especially when dealing with nodes that have two children. Selecting the correct replacement node is crucial to maintaining the BST property. Incorrect replacements can lead to further imbalance.

The Solution: Self-Balancing Trees

Self-Balancing Trees: The Acrobats of Data Structures

The Self-Balancing Family

1. AVL Trees: Named after Adelson-Velskii and Landis, these trees maintain a strict balance, ensuring that the heights of left and right subtrees differ by at most one. They're the perfectionists of the tree world!

2. Red-Black Trees: With nodes colored either red or black, these trees use a set of properties to keep balance. They're less rigid than AVL trees but often require fewer rotations during modifications.

3. Splay Trees: These trees take a unique approach by moving recently accessed nodes to the root. They're like the social butterflies of trees, always bringing the popular elements to the forefront.

B-Trees: The Data Management Powerhouses

Key Features of B-Trees

• Multi-Key Nodes: Each node can hold multiple keys, reducing tree height and improving access times.

• Balanced Growth: B-trees grow and shrink from the root, maintaining balance effortlessly.

• Disk I/O Optimization: By minimizing disk accesses, B-trees are perfect for systems with slow secondary storage.

The Importance of Keys in Tree Nodes

Implementation of B-tree in C++

#include <iostream>
using namespace std;

class BTreeNode {
    int *keys;
    int t;
    BTreeNode **C;
    int n;
    bool leaf;

public:
    BTreeNode(int _t, bool _leaf);

    void insertNonFull(int k);

    void splitChild(int i, BTreeNode *y);

    void traverse();

    BTreeNode *search(int k);

    friend class BTree;
};

class BTree {
    BTreeNode *root;
    int t;

public:
    BTree(int _t) {
        root = NULL;
        t = _t;
    }

    void traverse() {
        if (root != NULL) root->traverse();
    }

    BTreeNode* search(int k) {
        return (root == NULL) ? NULL : root->search(k);
    }

    void insert(int k);
};

BTreeNode::BTreeNode(int t1, bool leaf1) {
    t = t1;
    leaf = leaf1;

    keys = new int[2*t-1];
    C = new BTreeNode *[2*t];

    n = 0;
}

void BTreeNode::traverse() {
    int i;
    for (i = 0; i < n; i++) {
        if (leaf == false)
            C[i]->traverse();
        cout << " " << keys[i];
    }

    if (leaf == false)
        C[i]->traverse();
}

BTreeNode *BTreeNode::search(int k) {
    int i = 0;
    while (i < n && k > keys[i])
        i++;

    if (keys[i] == k)
        return this;

    if (leaf == true)
        return NULL;

    return C[i]->search(k);
}

void BTree::insert(int k) {
    if (root == NULL) {
        root = new BTreeNode(t, true);
        root->keys[0] = k;
        root->n = 1;
    }
    else {
        if (root->n == 2*t-1) {
            BTreeNode *s = new BTreeNode(t, false);

            s->C[0] = root;

            s->splitChild(0, root);

            int i = 0;
            if (s->keys[0] < k)
                i++;
            s->C[i]->insertNonFull(k);

            root = s;
        }
        else
            root->insertNonFull(k);
    }
}

void BTreeNode::insertNonFull(int k) {
    int i = n-1;

    if (leaf == true) {
        while (i >= 0 && keys[i] > k) {
            keys[i+1] = keys[i];
            i--;
        }

        keys[i+1] = k;
        n = n+1;
    }
    else {
        while (i >= 0 && keys[i] > k)
            i--;

        if (C[i+1]->n == 2*t-1) {
            splitChild(i+1, C[i+1]);

            if (keys[i+1] < k)
                i++;
        }
        C[i+1]->insertNonFull(k);
    }
}

void BTreeNode::splitChild(int i, BTreeNode *y) {
    BTreeNode *z = new BTreeNode(y->t, y->leaf);
    z->n = t - 1;

    for (int j = 0; j < t-1; j++)
        z->keys[j] = y->keys[j+t];

    if (y->leaf == false) {
        for (int j = 0; j < t; j++)
            z->C[j] = y->C[j+t];
    }

    y->n = t - 1;

    for (int j = n; j >= i+1; j--)
        C[j+1] = C[j];

    C[i+1] = z;

    for (int j = n-1; j >= i; j--)
        keys[j+1] = keys[j];

    keys[i] = y->keys[t-1];

    n = n + 1;
}

// Driver program to test above functions
int main() {
    BTree t(3);

    t.insert(10);
    t.insert(20);
    t.insert(5);
    t.insert(6);
    t.insert(12);
    t.insert(30);
    t.insert(7);
    t.insert(17);

    cout << "Traversal of the constructed tree is ";
    t.traverse();

    int k = 6;
    (t.search(k) != NULL)? cout << "\\nPresent" : cout << "\\nNot Present";

    k = 15;
    (t.search(k) != NULL)? cout << "\\nPresent" : cout << "\\nNot Present";

    return 0;
}

Wrapping Up