• Part 1: Introduction to Search Trees
• Part 2: Binary Search Tree (BST) & Operations
• Part 3: Self-Balancing Trees (AVL Tree)
• Part 4: Disk-Optimized Multi-Way Trees (B-Tree)
• Part 5: Indexing Trees (B+ Tree)
• Part 6: Practice, MCQ Quiz & Summary

• Static Arrays: Allow binary search ($O(\log n)$) but insertion/deletion requires shifts ($O(n)$).
• Linked Lists: Fast insertion ($O(1)$) but searching is linear ($O(n)$).
• Search Trees: Combine structural flexibility of lists with the fast search of binary search ($O(\log n)$ for search, insert, and delete).

A Search Tree is a node-based binary or multi-way tree structure where:

• Nodes store comparable keys.
• Keys are kept in sorted relative positions.
• Every search path splits choices at each node.

For every node $X$ in the tree:

• All keys in the left subtree must be strictly smaller than $X$'s key:
  $\text{Key}(Y) < \text{Key}(X) \quad \forall Y \in \text{LeftSubtree}(X)$
• All keys in the right subtree must be strictly greater than $X$'s key:
  $\text{Key}(Z) > \text{Key}(X) \quad \forall Z \in \text{RightSubtree}(X)$

We will construct a BST from scratch using this sequence of inputs:

[50, 30, 70, 20, 40, 60, 80]

Each insertion requires starting at the root and recursively choosing left or right edges.

First value inserted into an empty tree becomes the root node.

• Compare 30 with root 50.
• Since $30 < 50$, branch left.
• Left pointer is NULL; insert node 30 here.

• Compare 70 with root 50.
• Since $70 > 50$, branch right.
• Right pointer is NULL; insert node 70 here.

• Compare 20 with 50 $\rightarrow$ smaller (go left).
• Compare 20 with 30 $\rightarrow$ smaller (go left).
• Left of 30 is NULL; insert here.

• Compare 40 with 50 $\rightarrow$ go left.
• Compare 40 with 30 $\rightarrow$ go right ($40 > 30$).
• Right of 30 is NULL; insert here.

• Compare 60 with 50 $\rightarrow$ go right.
• Compare 60 with 70 $\rightarrow$ go left ($60 < 70$).
• Left of 70 is NULL; insert here.

• Compare 80 with 50 $\rightarrow$ go right.
• Compare 80 with 70 $\rightarrow$ go right ($80 > 70$).
• Right of 70 is NULL; insert here.

• Compare 60 with root 50. Since $60 > 50$, search right.
• Compare 60 with 70. Since $60 < 70$, search left.
• Compare 60 with 60. Matches! Node found.

• Compare 65 with 50 $\rightarrow$ go right.
• Compare 65 with 70 $\rightarrow$ go left.
• Compare 65 with 60 $\rightarrow$ go right.
• Right child of 60 is NULL. Search failed.

Node 20 is a leaf. We can remove it directly without moving any other nodes.

Assume we deleted 20, now we delete 30. Node 30 has only one child (40).

Node 50 has two children. We cannot delete it directly.

Instead, replace its value with its Inorder Successor (smallest key in the right subtree) or Inorder Predecessor (largest key in the left subtree).

• Multilevel Indexing: Used in databases for quick access to records.
• Dynamic Sorting: Useful for maintaining a constantly changing sorted dataset efficiently.
• Virtual Memory Management: Used in Unix operating systems for managing virtual memory areas.

If we insert keys in sorted order: [10, 20, 30, 40], a standard BST becomes skewed.

• Height degrades from $\log n$ to $n$.
• Operations slow down to $O(n)$ linear time.
• We lose the logarithmic searching speed!

An AVL Tree maintains balance by computing the Balance Factor (BF) for every node.

Let's trace how heights propagate upwards:

• NULL children have Height = 0.
• Leaves have Height = 1.
• A node's Height = $1 + \max(h_L, h_R)$.

When is LL Rotation Needed?

• Balance Factor of node = +2
• Insertion occurs in the Left subtree of Left child
• Tree becomes left-heavy.

RightRotate(z)

1. y = z->left
2. T3 = y->right

3. y->right = z
4. z->left = T3

5. Update Height(z)
6. Update Height(y)

7. return y

When is RR Rotation Used?

• Root node has BF = -2
• Insertion occurs in the Right subtree of the Right child.
• Tree becomes Right Heavy.

LeftRotate(z)

1. y = z->right;
2. T2 = y->left;

3. y->left = z;
4. z->right = T2;

5. UpdateHeight(z);
6. UpdateHeight(y);

7. return y;

When is LR Rotation Used?

• Root node has BF = +2
• Left child has BF = -1
• Insertion occurs in the Right subtree of the Left child.
• The tree forms a Zig-Zag pattern.

LRRotate(z)

1. z->left = LeftRotate(z->left);

2. return RightRotate(z);

When is RL Rotation Used?

• Root node has BF = -2
• Right child has BF = +1
• Insertion occurs in the Left subtree of the Right child.
• The tree forms a Zig-Zag pattern.

RLRotate(z)

1. z->right = RightRotate(z->right);

2. return LeftRotate(z);

Insert: [10, 20, 30] into AVL.

• Insert 10, 20 $\rightarrow$ fine.
• Insert 30 $\rightarrow$ BF at 10 becomes -2.
• RR Rotation is triggered at node 10.

Why do binary search trees fail for large database tables containing millions of rows?

• Disk access is slow (mechanically reading blocks).
• A binary tree of height 20 requires up to 20 disk operations.
• We need a wider tree with a larger branching factor so that we can fetch more keys per disk load!

An M-Way Search Tree node contains:

• Up to $m-1$ keys sorted: $K_1 < K_2 < \dots < K_{m-1}$
• Up to $m$ child pointers: $P_1, P_2, \dots, P_m$

Subtree $P_i$ contains keys between $K_{i-1}$ and $K_i$.

To find a key $X$ in a node with $k$ keys ($K_1 \dots K_k$):

• Do a linear or binary search through the keys in the node.
• If $X == K_i$, search is successful.
• If $X < K_1$, follow pointer $P_1$.
• If $K_i < X < K_{i+1}$, follow pointer $P_{i+1}$.
• If $X > K_k$, follow pointer $P_{k+1}$.

A B-Tree of order $m$ satisfies:

• Every node has at most $m$ children (and $m-1$ keys).
• Every internal node (except root) has at least $\lceil m/2 \rceil$ children (and $\lceil m/2 \rceil - 1$ keys).
• The root has at least 2 children (unless it is a leaf).
• All leaves are at the exact same depth.
• Keys within a node are sorted.

Insert: [10, 20, 30] in a B-Tree of Order 4.

• An Order 4 B-Tree can hold a maximum of 3 keys per node.
• We start with an empty root node.
• We insert 10, then 20, then 30 into the root.
• Since the node has not exceeded 3 keys, no split occurs.

Insert: [40]

• Inserting 40 creates an overflow (4 keys: 10, 20, 30, 40).
• Action: Split the node at the median.
• The median key (20) is promoted to the parent.
• The node splits into two leaves.

Insert: [50, 60, 70]

• 50 and 60 go into the right child. It overflows and splits, promoting 40 to the root.
• Root becomes [20 | 40]. Right child becomes [50 | 60].
• Insert 70 into [50 | 60]. It overflows (50, 60, 70), promoting 60 to root.
• Root is now [20 | 40 | 60]. Node is full!
• Next insert (e.g. 80) will cause root overflow, promoting 40 to a NEW root, increasing tree height.

Deletion requires maintaining minimum keys (1 for Order 4 internal, 1 for leaves here).

• Scenario: Delete 30.
• Node [30] becomes empty (underflow).
• Action (Borrow): Look at left sibling [10]. (Only 1 key, can't borrow).
• Look at right sibling [50]. (Only 1 key, can't borrow).
• Wait, this requires merging. Let's assume right sibling had [50 | 55]. We would borrow 50!
• Pull parent key (40) down, push sibling key (50) up to parent.

What if siblings are also at minimum capacity?

• Scenario: Delete 30 (from previous tree). Siblings [10] and [50] have only 1 key.
• Action (Merge): Merge the empty node, the sibling [10], and the parent key 20 into a single node [10 | 20].
• Parent loses key 20. If parent underflows, apply rules recursively upwards.

Deleting a key that is not in a leaf.

• Just like BST, we cannot simply delete an internal key because it acts as a separator for subtrees.
• Action: Replace the key with its inorder predecessor (largest key in left subtree) or inorder successor (smallest in right subtree).
• Then, delete the predecessor/successor from the leaf!
• If the leaf underflows, use borrow or merge.

How does a B+ Tree differ from a B-Tree?

• Internal nodes only store index keys and child pointers (no actual data).
• Leaf nodes store all data records.
• Leaves are linked together via a singly or doubly linked list.

Insert: [10, 20, 30, 40] in B+ Tree (Order 4)

• 10, 20, 30 fit in the leaf root. Insert 40 causes overflow.
• Leaf Split Rule: Split at median (20 or 30). Let's pick 30.
• COPY UP: The median 30 is copied to the parent index node. It ALSO stays in the right leaf!
• Left leaf: [10, 20]. Right leaf: [30, 40]. Root (Index): [30].

What happens when an internal (index) node overflows?

• Just like a standard B-Tree!
• PUSH UP: The median key is moved to the parent and is removed from the current index node.

Deleting a key always happens at the leaf level.

• Scenario 1: Key is only in leaf. Delete it directly. Borrow/Merge if underflow.
• Scenario 2: Key is also an index (routing) key in an internal node.
• We can simply delete the key from the leaf and leave the index key alone! It's still a valid routing value.
• However, if we merge leaves, we might need to delete the index key to fix the parent underflow.

Query: Find all keys in range 15 to 35.

• Step 1: Use index to search for key 15 ($O(\log n)$). Reaches first leaf containing 20.
• Step 2: Follow leaf link pointers to get keys 20, 30, and 40. Stops when key exceeds 35 ($O(k)$).

Work on these problems during this workshop segment:

• Exercise 1: Construct a BST using keys: [15, 6, 18, 3, 7, 16, 20, 10].
• Exercise 2: Delete node 6 from your BST. Explain the case.
• Exercise 3: Insert 40, 50, 60 in AVL. Balance it.

• BSTs offer simple structures but risk degrading to $O(n)$ if unbalanced.
• AVL Trees fix this by strictly rebalancing (using LL/RR/LR/RL rotations) to maintain $O(\log n)$.
• B-Trees expand child capacity, optimizing layout for disk structures.
• B+ Trees link leaves together to enable fast sequential database range queries.