Advanced Tree Structures: BSTs, AVL, and Heaps

Trees are fundamental non-linear data structures widely used in computer science for efficient data organization and retrieval. Building upon basic binary trees, this chapter delves into specialized tree structures: Binary Search Trees (BSTs) for ordered data management, AVL trees as self-balancing variants of BSTs, and Heaps for priority queue implementations.

1. Binary Trees: The Foundation

A binary tree, $T$ , is a hierarchical data structure where each node has at most two children, referred to as the left child and the right child.

Definition: A binary tree is either empty or consists of a special node called the root, and two disjoint binary trees called the left subtree and right subtree of the root.
Node Terminology:
- Root: The topmost node of the tree.
- Parent: A node that has at least one child node.
- Child: A node directly connected to another node when moving away from the root.
- Leaf: A node that has no children.
- Level of a node: The number of branches (edges) on the path from the root to the node. The root is typically at level 0.
- Height of a binary tree: The maximum number of edges in a path from the root node to any leaf node. An empty tree has height -1, a single-node tree has height 0.
- Subtree: The tree formed by a child node and all its descendants.

Here's an example of a binary tree:

text

       12 (Level 0, Parent of 8, 11)
      /  \
     8    11 (Level 1, Children of 12)
    / \    /
   4   9  6  (Level 2, Children of 8, 11)
  / \
 1   5     (Level 3, Children of 4)
 
Height of the tree = 3 (path 12-8-4-1 or 12-8-4-5)
Leaves: 1, 5, 9, 6

1.1 Binary Tree Traversal

Traversal refers to the process of visiting each node in the tree exactly once. There are three primary methods for binary tree traversal:

Preorder Traversal (Root-Left-Right):
1. Visit the root node.
2. Traverse the left subtree.
3. Traverse the right subtree.
Inorder Traversal (Left-Root-Right):
1. Traverse the left subtree.
2. Visit the root node.
3. Traverse the right subtree.
Postorder Traversal (Left-Right-Root):
1. Traverse the left subtree.
2. Traverse the right subtree.
3. Visit the root node.

2. Binary Search Trees (BSTs)

A Binary Search Tree (BST) is a special type of binary tree that maintains a specific ordering property to enable efficient searching, insertion, and deletion of elements.

BST Property:
1. All nodes in the left subtree of a node contain values strictly less than the node's value.
2. All nodes in the right subtree of a node contain values strictly greater than the node's value.
3. Both the left and right subtrees must also be BSTs.

The BST property ensures that an inorder traversal of a BST will yield elements in sorted order.

text

2.1 Operations on BSTs

The BST property makes operations like searching, insertion, and deletion highly efficient, especially when the tree is balanced.

Search for a Value:
1. Start at the root.
2. If the target value matches the current node's value, the search is successful.
3. If the target value is less than the current node's value, move to the left child.
4. If the target value is greater than the current node's value, move to the right child.
5. If a child is NULL and the value hasn't been found, the value is not in the tree.
Insert an Item:
1. Start at the root.
2. Compare the new value with the current node's value.
3. If the new value is less, go left; if greater, go right.
4. Continue traversing until an empty (NULL) spot is found.
5. Insert the new node at that empty position, maintaining the BST property.
Delete an Item: Deletion is more complex, handling three cases:
1. Node is a leaf: Simply remove it.
2. Node has one child: Replace the node with its child.
3. Node has two children: Find the inorder successor (smallest node in the right subtree) or inorder predecessor (largest node in the left subtree). Replace the node's value with the successor's/predecessor's value, then delete the successor/predecessor node (which will have at most one child).

Time Complexity: For a balanced BST, operations like search, insertion, and deletion take $O(\log N)$ time, where $N$ is the number of nodes. In the worst case (a skewed tree, resembling a linked list), these operations degrade to $O(N)$ .

3. AVL Trees: Self-Balancing BSTs

The primary drawback of a standard BST is its potential to become unbalanced, leading to $O(N)$ worst-case performance. An AVL tree (named after its inventors Adelson-Velsky and Landis) is a self-balancing Binary Search Tree that guarantees $O(\log N)$ time complexity for all major operations.

3.1 Balance Factor

The key to an AVL tree's self-balancing nature is the balance factor. For any node $x$ in an AVL tree, its balance factor is defined as: $\text{Balance Factor}(x) = \text{Height}(\text{Left Subtree of } x) - \text{Height}(\text{Right Subtree of } x)$ For an AVL tree to be valid, the balance factor of every node must be either $-1, 0,$ or . If any node has a balance factor outside this range (i.e., or ), the tree is considered unbalanced at that node, and rotations are performed to restore balance.

text

       Node Height (h) and Balance Factor (BF = h_left - h_right)
       
       (Balanced AVL Trees)
       
        4 (h=2, BF=1)
       / \
      2   6 (h=1, BF=0)
     /   / \
    1   5   7 (h=0, BF=0 for all leaves)
   (h=0)
 
        6 (h=2, BF=0)
       / \
      4   8 (h=1, BF=0)
     / \   \
    2   5   9 (h=0, BF=0 for all leaves)
   (h=0)
   
   
       (Unbalanced after insertion - BF=2)
 
       4 (h=2, BF=2)
      /
     2 (h=1, BF=1)
    /
   1 (h=0, BF=0)
  (insert 0 here will cause unbalance at 4)

3.2 Rotations

When an insertion or deletion causes a node's balance factor to become $-2$ or $2$ , a series of tree rotations are performed to restore the AVL property. There are four types of rotations:

Left Rotation (LL Imbalance): When a node becomes heavy on its left-left child's side.

text

    Z             Y
   / \           / \
  Y   T4  ->    X   Z
 / \           / \ / \
X   T3        T1 T2 T3 T4

/
T1 T2

plaintext

2.  **Right Rotation (RR Imbalance):** When a node becomes heavy on its right-right child's side.
```text
  Z                 Y
 / \               / \
T1  Y      ->     Z   X
   / \           / \ / \
  T2  X         T1 T2 T3 T4
     / \
    T3 T4

Left-Right Rotation (LR Imbalance): When a node is left-heavy, but its left child is right-heavy. It's a Left Rotation on the child, then a Right Rotation on the original node.
Right-Left Rotation (RL Imbalance): When a node is right-heavy, but its right child is left-heavy. It's a Right Rotation on the child, then a Left Rotation on the original node.

3.3 Operations in AVL Trees

Insertion: Insert the node as in a standard BST. Then, traverse back up from the inserted node to the root, updating heights and checking balance factors. If an imbalance ( $|\text{BF}| > 1$ ) is found, perform the appropriate rotation(s) to rebalance the subtree.
Deletion: Delete the node as in a standard BST. Again, traverse up from the point of deletion to the root, updating heights and performing rotations as needed.

All operations (search, insert, delete) in an AVL tree have a time complexity of $O(\log N)$ , providing consistent high performance regardless of data insertion order.

4. Heaps: Priority Queues

A heap is a specialized tree-based data structure that satisfies the heap property. Unlike BSTs, a heap does not maintain elements in fully sorted order across the entire tree, but rather ensures a specific ordering between parent and child nodes. Heaps are commonly used to implement priority queues.

A heap must fulfill two main properties:

Shape Property: It must be a complete binary tree. This means all levels are fully filled, except possibly the last level, which is filled from left to right.
Heap Property:
- Min-Heap: For every node $x$ , the value of $x$ is less than or equal to the values of its children. The minimum element is always at the root.
- Max-Heap: For every node $x$ , the value of $x$ is greater than or equal to the values of its children. The maximum element is always at the root.

We will focus on Min-Heaps for examples.

text

      (Example of a Min-Heap)
 
         1
        / \
       2   4
      / \ / \
     5  11 7  8
    /
   12

4.1 Heap Operations

The core operations for heaps are insertion and extraction of the root element (min for a Min-Heap, max for a Max-Heap). Both operations involve maintaining the heap property.

Insertion into a Min-Heap:
1. Add the new item to the last available position in the complete tree (to maintain the shape property).
2. Perform a "heapify-up" (or "bubble-up") operation: Compare the new item with its parent. If the new item is smaller, swap it with its parent. Repeat this process until the item is at the root or is greater than or equal to its parent.
Extract Min (from a Min-Heap):
1. The minimum item is always at the root. Store this value to return it.
2. Replace the root node with the item from the last available position in the complete tree.
3. Remove the last position (the old last item is now at the root).
4. Perform a "heapify-down" (or "bubble-down") operation: Compare the new root with its children. If it is larger than either child, swap it with the smaller of its children. Repeat this process until the item is a leaf or is smaller than or equal to both its children.

Time Complexity: Both insertion and extraction operations take $O(\log N)$ time, where $N$ is the number of elements in the heap, due to the height of the tree.

4.2 Array Representation of Heaps

Since a heap is a complete binary tree, it can be efficiently represented using an array or std::vector (in C++). This avoids the need for explicit pointers for children, saving memory.

For a node at index $i$ :

Its parent is at index $\lfloor (i-1)/2 \rfloor$ .
Its left child is at index $2i+1$ .
Its right child is at index $2i+2$ .

The root is at index 0.

text

      (Heap as a tree)         (Heap as an array)
         1                     [1, 2, 4, 5, 11, 7, 8]
        / \                     0  1  2  3  4   5  6 (indices)
       2   4
      / \ / \
     5  11 7  8
 
Example: Node at index 1 (value 2)
Parent: (1-1)/2 = 0 (value 1)
Left child: 2*1+1 = 3 (value 5)
Right child: 2*1+2 = 4 (value 11)

4.3 C++ Implementation Example (Min-Heap)

cpp

#include <iostream>
#include <vector>
#include <algorithm> // For std::swap
 
class MinHeap {
private:
    std::vector<int> heap;
 
    // Helper function to get parent index
    int getParentIndex(int i) {
        return (i - 1) / 2;
    }
 
    // Helper function to get left child index
    int getLeftChildIndex(int i) {
        return 2 * i + 1;
    }
 
    // Helper function to get right child index
    int getRightChildIndex(int i) {
        return 2 * i

Summary

Binary Search Trees (BSTs) organize data such that values in the left subtree are smaller than the root, and values in the right subtree are larger, enabling $O(\log N)$ average-case performance for search, insert, and delete.
AVL Trees are self-balancing BSTs that maintain a balance factor (height difference between subtrees) of at most 1 for every node. They use rotations (Left, Right, Left-Right, Right-Left) to restore balance after insertions or deletions, guaranteeing $O(\log N)$ worst-case performance.
Heaps are complete binary trees that satisfy the heap property: for a Min-Heap, each parent is less than or equal to its children, ensuring the minimum element is at the root.
Heaps are efficiently implemented using arrays due to their complete binary tree structure.
Heap operations like insertion and extraction involve "heapify-up" or "heapify-down" to restore the heap property, both taking $O(\log N)$ time.

Assessed progress

Advanced Tree Structures: BSTs, AVL, and Heaps

Advanced Tree Structures: BSTs, AVL, and Heaps

1. Binary Trees: The Foundation

1.1 Binary Tree Traversal

2. Binary Search Trees (BSTs)

2.1 Operations on BSTs

3. AVL Trees: Self-Balancing BSTs

3.1 Balance Factor

3.2 Rotations

3.3 Operations in AVL Trees

4. Heaps: Priority Queues

4.1 Heap Operations

4.2 Array Representation of Heaps

4.3 C++ Implementation Example (Min-Heap)

Summary

Key Concepts

Binary Search Tree (BST)

AVL Tree

Balance Factor

Heap

Heapify

Quick Check

Advanced Data Structures

Advanced Data Structures