Yasir Explains/Algorithms/M-way Trees, B-Trees & Amortized Analysis
Algorithms

M-way Trees, B-Trees & Amortized Analysis

Algorithms

M-way Trees, B-Trees & Amortized Analysis

Generalize search trees to many children per node, build self-balancing B-trees for disk-based indexing, and learn amortized analysis through dynamic arrays.

Topics

M-way Search Trees

B-Trees: Definition & Invariants

B-Tree Insertion & Node Splitting

B-Tree Deletion: Borrowing & Merging

Height, Disk I/O & Applications

Amortized vs. Worst-Case & the Aggregate Method

Accounting (Banker's) Method & Potential Functions

Dynamic Arrays & Vector Growth Strategies