Data Structures & Algorithms for Problem Solving(MCS103)
Module-1
Search Trees: Two Models of Search Trees. General Properties and Transformations. Height
of a Search Tree. Basic Find, Insert, and Delete. Returning from Leaf to Root. Dealing with
Non unique Keys. Queries for the Keys in an Interval. Building Optimal Search Trees.
Converting Trees into Lists. Removing a Tree. Balanced Search Trees: Height-Balanced
Trees. Weight-Balanced Trees. (a, b)- And B-Trees. Red-Black Trees and Trees of Almost
Optimal Height. Top-Down Rebalancing for Red-Black Trees.
Search Trees: Two Models, General Properties, and
Transformations ([Link] Level)
1. Introduction
A search tree is a tree-based data structure used to store and retrieve ordered data efficiently.
It supports dynamic set operations such as:
Search(x)
Insert(x)
Delete(x)
Min/Max
Predecessor/Successor
Search trees are fundamental in database indexing, compiler design, memory management,
and file systems.
2. Two Models of Search Trees
Search trees can be broadly classified into two conceptual models:
Model 1: Binary Search Tree (BST) Model
A Binary Search Tree (BST) is a binary tree where:
For every node v:
All keys in the left subtree < key(v)
All keys in the right subtree > key(v)
Example:
A standard BST as introduced by:
Introduction to Algorithms (Cormen, Leiserson, Rivest, Stein)
Operations and Time Complexity
If height = h:
Operation Time Complexity
Search O(h)
Insert O(h)
Delete O(h)
Worst case (skewed tree): O(n)
Best case (balanced): O(log n)
Balanced BST Variants
To guarantee O(log n) height:
AVL tree
Red–Black tree
These maintain structural constraints using rotations.
Model 2: Multiway Search Tree Model (B-Tree Model)
In external memory or disk-based systems, binary branching is inefficient due to I/O cost.
Hence, we use multiway search trees.
B-Tree Model
A B-tree of order m:
Each node has between ⌈m/2⌉ and m children
Keys in node are sorted
All leaves are at the same depth (perfectly balanced)
Widely used in:
Database indexing
File systems
Variants include:
B-tree
B+ tree
Complexity (Disk Model)
If branching factor = m:
Height = O(logₘ n)
I/O cost = O(logₘ n)
Since m is large (100–1000), height is very small → efficient disk access.
3. General Properties of Search Trees
3.1 Ordering Property
All search trees maintain a sorted order property enabling binary search.
3.2 Height Property
Performance depends on height:
Unbalanced BST → height O(n)
Balanced trees → height O(log n)
3.3 Dynamic Set Operations
All search trees support:
Insert
Delete
Search
Range queries
3.4 Inorder Traversal Property
In BST:
Inorder traversal → Sorted sequence.
3.5 Structural Constraints
Structure Constraint
AVL Tree Height-balanced (balance factor −1,0,1)
Red-Black Tree Color + black-height rules
B-Tree Minimum/maximum children rules
4. Transformations in Search Trees
Transformations are operations that modify structure while preserving order property.
4.1 Tree Rotations (BST Model)
Used in AVL and Red-Black Trees.
Types:
Left Rotation
Right Rotation
Purpose:
Maintain height balance
Preserve BST ordering
Used in:
AVL tree
Red–Black tree
Time Complexity: O(1)
4.2 Rebalancing Transformations
AVL Rebalancing
Single rotation
Double rotation (LR, RL cases)
Red-Black Rebalancing
Recoloring
Rotations
Fix-up procedures after insertion/deletion
4.3 Split and Merge (B-Tree Model)
Split
When node overflows:
Divide into two nodes
Promote middle key
Merge
When node underflows:
Combine siblings
Redistribute keys
These maintain height balance automatically.
4.4 Transforming Unbalanced BST to Balanced BST
Methods:
1. Inorder traversal → Sorted array
2. Construct balanced BST from sorted array
Time Complexity: O(n)
4.5 Equivalence Transformations
Any BST can be transformed into another BST with the same keys using a sequence of
rotations.
This is fundamental in:
Splay trees
Amortized analysis
Related structure:
Splay tree
5. Comparison of Two Models
Feature BST Model B-Tree Model
Branching Binary Multiway
Feature BST Model B-Tree Model
Height O(log n) if balanced O(logₘ n)
Disk Efficiency Poor Excellent
Used In Memory structures Databases
Rebalancing Rotations Split/Merge
6. Theoretical Analysis
Height Bounds
AVL Tree: h ≤ 1.44 log₂(n)
Red-Black Tree: h ≤ 2 log₂(n)
B-Tree: h ≤ logₘ(n)
Space Complexity
All search trees require O(n) space.
7. Applications
1. Database Indexing → B+ Trees
2. Compiler Symbol Tables → Balanced BST
3. File Systems → B-Trees
4. Memory Allocation → Red-Black Trees
5. C++ STL map, set → Red-Black Tree
8. Conclusion
Search trees are fundamental dynamic data structures supporting efficient ordered operations.
Two primary models exist:
1. Binary Search Tree Model – Suitable for internal memory; requires balancing for
optimal performance.
2. Multiway Search Tree (B-Tree) Model – Designed for external memory; minimizes
disk I/O.
Transformations such as rotations, splits, and merges ensure structural balance and optimal
height, which directly determines efficiency.