Advanced Trees

Self-Balancing Trees

You already know that binary search trees (BSTs) are great for fast lookups, insertions, and deletions. But they have a major weakness. If you insert sorted data into a BST, it stops looking like a tree and starts acting like a linked list. All the nodes just line up in a single branch. This makes search operations slow down from a speedy $O(\log n)$ to a sluggish $O(n)$ .

To solve this, computer scientists developed self-balancing binary search trees. These trees automatically adjust their structure to stay balanced, ensuring that operations always remain efficient. First up is the AVL tree, one of the earliest self-balancing structures.

AVL Trees

An AVL tree is a BST with an extra rule: for every node, the heights of its left and right subtrees can differ by at most one. This difference is called the balance factor.

Balance Factor = Height(Right Subtree) - Height(Left Subtree)

An AVL tree is valid only if every single node has a balance factor of -1, 0, or 1. If an insertion or deletion ever creates a node with a balance factor of -2 or 2, the tree is considered unbalanced. It immediately performs a "rotation" to fix itself.

Rotations are the core mechanism for rebalancing. There are four types: left rotation, right rotation, left-right rotation, and right-left rotation. These operations rearrange nodes to restore the balance property while preserving the BST property (left child < parent < right child).

Let's look at the structure of an AVL tree node in C++. It's just like a standard BST node, but with an added height field to help calculate balance factors.

#include <iostream>
#include <algorithm>

struct Node {
    int key;
    Node *left;
    Node *right;
    int height;
};

// Function to get height of a node
int height(Node *N) {
    if (N == nullptr)
        return 0;
    return N->height;
}

// Function to create a new node
Node* newNode(int key) {
    Node* node = new Node();
    node->key = key;
    node->left = nullptr;
    node->right = nullptr;
    node->height = 1; // New node is initially at height 1
    return(node);
}

The rotation logic can be complex, but the key idea is simple: after an insert or delete, we trace the path back to the root, updating heights and checking balance factors. If we find an unbalanced node, we perform the correct rotation to fix it. This guarantees that the tree never becomes too lopsided.

B-Trees

While AVL trees keep binary trees balanced, B-trees are designed for a different problem. They are optimized for systems that read and write large blocks of data, like databases and file systems. Unlike binary trees, nodes in a B-tree can have many children.

A B-tree of order m has these properties:

Every node has at most m children.
Every non-leaf node (except the root) has at least m/2 children.
The root has at least two children unless it is a leaf node.
All leaves appear on the same level.
A non-leaf node with k children contains k-1 keys.

These rules ensure the tree is always wide and shallow. A shallow tree means fewer disk reads are needed to find a piece of data, which is a huge performance win for storage systems.

B-Trees are dynamic, balanced tree data structures widely used in databases and file systems to maintain sorted data and allow efficient insertions, deletions, and searches.

When a new key is inserted into a B-tree node that is already full, the node splits into two. The median key is moved up to the parent node. This splitting process is how the B-tree grows upwards and maintains its balance. Deletion works in reverse, sometimes requiring nodes to merge or borrow keys from siblings.

Threaded Binary Trees

Finally, let's look at a clever optimization for tree traversal. In a standard binary tree, many nodes have nullptr for their left or right child pointers. That's wasted space. A threaded binary tree reuses these null pointers to point to other nodes in the tree.

Specifically:

A nullptr right child pointer is replaced with a pointer to the node's in-order successor.
A nullptr left child pointer is replaced with a pointer to the node's in-order predecessor.

These special pointers are called "threads."

The primary advantage is that traversal becomes much easier. You can perform an in-order traversal without using recursion or a stack, which saves memory. You simply follow the pointers. If a node has a right child, you go to the leftmost node of that right subtree. If it doesn't have a right child, you just follow its right thread to the next node in the sequence.

By using threads, we can traverse the tree without the overhead of a stack, making the process faster and more memory-efficient, especially for very large trees.

To implement this, each node needs two boolean flags to indicate whether its left and right pointers are normal child links or threads. While clever, threaded trees are less common today because memory is more plentiful and the added complexity can make insertion and deletion logic harder to manage.

These advanced trees show how data structures can be adapted to solve specific problems, from maintaining balance for fast searches to optimizing for disk storage or efficient traversal.

Quiz Questions 1/6

What is the primary weakness of a standard binary search tree (BST) that self-balancing trees like AVL trees are designed to solve?

Quiz Questions 2/6

In an AVL tree, the balance factor of a node is calculated as: Height(Right Subtree) - Height(Left Subtree). For the tree to be considered valid, what must be true for every single node's balance factor?

Advanced Data Structures and Algorithms in C++