Advanced Data Structures

A Complete Visual Guide

─────────────────────────────────────
Trees • Heaps • Strings • Randomized • Spatial • Miscellaneous

Simple explanations, illustrations, prerequisites & complexity analysis

Unit 1: Advanced Trees and Applications
Trees are one of the most important data structures in computing. Before diving into the advanced tree
types, let's understand the fundamental building blocks that all these trees rely on.

📚 PREREQUISITES — What you need to know first

Node: A single unit of data in a tree. Contains a value and pointers to children.
Root: The topmost node of a tree — the starting point.
Parent / Child: A node that points to another is the parent; the pointed-to node is the child.
Leaf: A node with no children — the end points of a tree.
Height: The longest path from root to a leaf node.
BST (Binary Search Tree): A tree where left child < parent < right child. Enables fast
searching.
Inorder Traversal: Visit Left subtree → Root → Right subtree. In a BST this gives sorted
order.
Balancing: Keeping a tree's height small (close to log n) so operations stay fast.

1.1 Threaded Binary Tree

Imagine you have a regular binary tree and you want to traverse it. Normally, traversal requires a stack
or recursion to "remember" where to go next. A Threaded Binary Tree is a clever trick that avoids this
extra memory by reusing the NULL pointers that leaf nodes and half-leaf nodes already have.

The Big Idea: Instead of leaving NULL pointers empty, point them to the next node in inorder sequence.
These special pointers are called "threads" and they let you traverse the tree without any stack or
recursion — just follow the threads!

💡 Simple Analogy
Think of a maze where dead ends (NULL pointers) are instead connected back to the
corridor you came from. Instead of backtracking, you can just follow the hidden corridor
forward.

How It Looks
4 ← Root
/ \
2 6
/ \ / \
1 3 5 7 ← All leaves

Inorder sequence: 1 → 2 → 3 → 4 → 5 → 6 → 7

Threaded connections (right threads shown with →→):

 Node 1: right NULL →→ Node 2 (its inorder successor)
Node 3: right NULL →→ Node 4 (its inorder successor)
Node 5: right NULL →→ Node 6 (its inorder successor)
Node 7: right NULL →→ NULL (no successor; it's last)

Types of Threading
▸ Right-threaded: Only NULL right pointers are threaded (most common).
▸ Left-threaded: Only NULL left pointers are threaded.
▸ Fully-threaded: Both left and right NULL pointers are threaded.

How to Tell Thread from Real Link

Each node needs a flag: rightThread = true means the right pointer is a thread, not a real child.
Without this flag, you'd get into infinite loops.

Time & Space Complexity

Operation Time Complexity Space Complexity
Inorder Traversal O(n) O(1) ← no stack!
Search O(n) O(1)
Insert O(n) O(1)
Delete O(n) O(1)
Extra Space (threads) — O(n) nodes, but uses
existing NULL slots

⭐ Key advantage: Inorder traversal in O(1) space instead of O(h) stack space (where h = height of tree).

1.2 AVL Tree

Named after its inventors Adelson-Velsky and Landis (1962), the AVL Tree is a self-balancing Binary
Search Tree. It guarantees that the tree never becomes lopsided — keeping all operations fast even in
worst-case scenarios.

The Problem it solves: If you insert sorted data (1, 2, 3, 4, 5...) into a regular BST, it becomes a straight
line — like a linked list — and search becomes O(n). AVL trees fix this automatically.

The Balance Factor

Every node stores a Balance Factor (BF) = height(left subtree) − height(right subtree)

📏 Balance Factor Rules

BF = -1, 0, or +1 → Tree is balanced ✓
 BF = -2 or +2 → Tree is UNBALANCED — need to fix it with rotations ✗

The Four Rotation Cases

When balance breaks, AVL fixes it with rotations — rearranging nodes while keeping BST ordering
intact:

CASE 1 — Left-Left (LL): Right Rotation

Before: After right rotation:
C B
/ / \
B → A C
/
A

CASE 2 — Right-Right (RR): Left Rotation

Before: After left rotation:
A B
\ / \
B → A C
\
C

CASE 3 — Left-Right (LR): Left rotate child, then Right rotate root
Before: Step 1: Step 2:
C C B
/ / / \
A → B → A C
\ /
B A

CASE 4 — Right-Left (RL): Right rotate child, then Left rotate root
(Mirror of LR case)

Time & Space Complexity

Operation Time Complexity Space Complexity
Search O(log n) O(log n) recursion
stack
Insert O(log n) O(log n)
Delete O(log n) O(log n)
Rotation (fix) O(1) O(1)
Space (whole tree) — O(n)

⭐ Height of AVL tree is always ≤ 1.44 × log₂(n) — guaranteed!

1.3 Red-Black Tree

A Red-Black Tree is another self-balancing BST, but instead of tracking exact heights, it uses a simple
colouring rule (red or black) on each node to keep the tree approximately balanced. It's used in many
real-world systems including Java's TreeMap, C++ std::map, and Linux kernel schedulers.

🎨 The 5 Red-Black Rules (must ALL hold at all times)

Rule 1: Every node is either RED or BLACK.
Rule 2: The ROOT is always BLACK.
Rule 3: Every LEAF (NULL node) is BLACK.
Rule 4: If a node is RED, both its children must be BLACK. (No two reds in a row!)
Rule 5: All paths from any node to its NULL leaves have the SAME number of BLACK
nodes.

What These Rules Guarantee

Rule 5 ensures the tree is never wildly unbalanced. The longest possible path (alternating red-black) is
at most 2× the shortest path. This gives a height of at most 2 × log₂(n+1) — much better than a
degenerate BST's O(n).

Example Red-Black Tree (B=Black, R=Red):

13(B)
/ \
8(R) 17(R)
/ \ / \
1(B) 11(B) 15(B) 25(B)
\ / \
6(R) 22(R) 27(R)

Every path from root to NULL has exactly 3 black nodes ✓

Fixing Violations: Recoloring & Rotations

▸ Recoloring: When a red-red conflict occurs and the uncle is also red — just recolour parent
and uncle to black, grandparent to red.
▸ Rotation + Recolour: When uncle is black — perform rotation (LL/RR/LR/RL like AVL) and
recolour.

AVL vs Red-Black — When to use which?

Aspect AVL Tree Red-Black Tree
Balance Stricter (exact height) Looser (colour rule)
Search Speed Slightly faster Slightly slower
Insert/Delete More rotations Fewer rotations
Best for Read-heavy workloads Write-heavy workloads
Time & Space Complexity
Operation Time Complexity Space Complexity
Search O(log n) O(n)
Insert O(log n) O(n)
Delete O(log n) O(n)
Rebalancing after insert O(log n) O(1) amortized

1.4 Heap Tree

A Heap is a Complete Binary Tree (all levels filled except possibly the last, which fills left to right) that
satisfies the Heap Property:

📐 Heap Property
Max-Heap: Every parent is ≥ its children. The largest element is always at the root.
Min-Heap: Every parent is ≤ its children. The smallest element is always at the root.

The Array Trick — No Pointers Needed!

Because it's a complete binary tree, a heap can be stored in a plain array without any pointers. This
makes it very memory-efficient:

Max-Heap as a tree: As an array:

Index: 0 1 2 3 4 5 6
90 Value:[90,80,70,40,30,60,10]
/ \
80 70 For any node at index i:
/ \ / \ • Left child → index 2i+1
40 30 60 10 • Right child → index 2i+2
• Parent → index (i-1)/2

Key Operations
▸ Insert (Heapify-Up): Add at end → compare with parent → swap if violated → repeat until
fixed. Like a bubble floating up.
▸ Extract-Max/Min (Heapify-Down): Remove root → put last element at root → compare with
children → swap with largest/smallest child → repeat until fixed.
▸ Build Heap (Heapify): Convert any array to a heap in O(n) — smarter than inserting one by
one.

💡 Real-world uses of Heaps

• Priority queues (process scheduling, Dijkstra's algorithm)
 • Heap Sort — sort an array in O(n log n)
• Finding the k-th largest/smallest element quickly
• Median maintenance (use two heaps)

Time & Space Complexity

Operation Time Complexity Space Complexity
Build Heap O(n) O(n)
Insert O(log n) O(n)
Extract Max/Min O(log n) O(n)
Peek (find max/min) O(1) O(n)
Heap Sort O(n log n) O(1) in-place

1.5 Huffman Tree

Huffman Tree is used for lossless data compression — the same idea behind ZIP files and JPEG
images. It encodes frequent characters with shorter bit strings and rare characters with longer ones,
saving space overall.

💡 Simple Analogy
Morse code uses "." for the letter E (most common in English) and longer codes for rare
letters like Z. Huffman coding does the same idea, but optimally computed by a computer.

How to Build a Huffman Tree — Step by Step

▸ Step 1: Count frequency of each character in your text.
▸ Step 2: Create a leaf node for each character, weighted by frequency.
▸ Step 3: Put all nodes in a Min-Heap (priority queue).
▸ Step 4: Repeatedly: extract the 2 nodes with LOWEST frequency, create a new parent node
(frequency = sum of the two), insert back into heap.
▸ Step 5: When only 1 node remains, that's your Huffman Tree root.
▸ Step 6: Assign 0 to every left edge, 1 to every right edge. Each character's code is its path from
root to leaf.

Text: "ABRACADABRA"
Frequencies: A=5, B=2, R=2, C=1, D=1

Step 1: Min-heap: [C:1, D:1, B:2, R:2, A:5]

Step 2: Merge C:1 + D:1 → CD:2

Min-heap: [B:2, R:2, CD:2, A:5]

Step 3: Merge B:2 + R:2 → BR:4

 Min-heap: [CD:2, A:5, BR:4]

Step 4: Merge CD:2 + BR:4 → CDBR:6

Min-heap: [A:5, CDBR:6]

Step 5: Merge A:5 + CDBR:6 → Root:11

Final codes: A=0, C=100, D=101, B=110, R=111

Original: 11 chars × 3 bits = 33 bits
Compressed: 5×1 + 1×3 + 1×3 + 2×3 + 2×3 = 23 bits → 30% savings!

Time & Space Complexity

Operation Time Complexity Space Complexity
Build Tree (n chars) O(n log n) O(n)
Encode a message O(m) where m=msg O(n) for codes table
length
Decode a message O(m) O(n) tree stored

1.6 B-Tree
A B-Tree is a self-balancing search tree designed for disk storage. Unlike binary trees (1 key, 2
children per node), a B-Tree of order m can have up to m children and m-1 keys per node. This means
fewer disk reads, making it perfect for databases (like MySQL, PostgreSQL) and file systems (like
NTFS, ext4).

💡 Why B-Trees?
Disk reads are ~100,000× slower than RAM reads. A B-Tree of order 1000 with a million
keys needs only 2 disk reads vs 20 for a regular BST. Fewer levels = fewer disk reads =
faster databases!

B-Tree of Order m — Rules

▸ Every node has at most m children and m-1 keys
▸ Every non-root node has at least ⌈m/2⌉ − 1 keys (nodes stay at least half full)
▸ All leaves are at the same depth — perfectly balanced!
▸ Keys in each node are sorted; children fill the gaps between keys

B-Tree of order 3 (max 2 keys, max 3 children per node):

[20 | 40]
/ | \
[10|15] [25|30] [45|50]

Search for 25:

1. At root: 25 > 20 and 25 < 40 → go to middle child
 2. At [25|30]: found 25! ✓

Insert 27:
1. Navigate to leaf [25|30]
2. Leaf is full (2 keys)! → SPLIT: promote 27 to parent
[25] and [30] become separate nodes

Splitting is how B-Trees grow upward, keeping all leaves at same level.

Time & Space Complexity

Operation Time Complexity Space Complexity
Search O(log n) O(n)
Insert O(log n) O(n)
Delete O(log n) O(n)
Height O(log_m n) —

1.7 B+ Tree
A B+ Tree is an enhanced version of B-Tree used in almost every modern database (MySQL InnoDB,
PostgreSQL). The key difference: all actual data is stored only in leaf nodes. Internal nodes just store
copies of keys as guides for searching. Leaves are linked together in a linked list, enabling super-fast
range queries.

B+ Tree Structure:

Internal nodes: [30 | 60] ← keys only, no data

/ | \
[10|20] [40|50] [70|80] ← keys only
/ | \ / | \ / | \

Leaf nodes: [10]→[20]→[30]→[40]→[50]→[60]→[70]→[80]

Data Data Data Data Data Data Data Data
↑ All leaves linked as a sorted linked list!

Range query "Find all between 20 and 60":

1. Search for 20 (reach leaf with 20)
2. Walk the linked list forward: 20→30→40→50→60 ✓
No need to traverse the whole tree!

B-Tree vs B+ Tree
Feature B-Tree B+ Tree
Data storage In all nodes Only in leaves
Range queries Requires traversal Fast — follow linked list
Internal node size Larger (has data) Smaller (keys only)
 Fan-out Lower Higher (more keys fit)
Best for Single lookups Range queries, DBs

Time & Space Complexity

Operation Time Complexity Space Complexity
Search O(log n) O(n)
Insert O(log n) O(n)
Delete O(log n) O(n)
Range Query (k results) O(log n + k) O(n)

1.8 Splay Tree

A Splay Tree is a self-adjusting BST with a unique strategy: whenever you access a node (search,
insert, or delete), it gets "splayed" — moved to the ROOT. Recently accessed elements stay near
the top, making repeated accesses very fast.

💡 Simple Analogy
It's like a browser's recently visited list — the websites you open most often bubble to the
top. Splay trees exploit temporal locality: if you just looked up "salary", you'll probably look it
up again soon.

Splaying Operations
▸ Zig: Node is child of root → simple rotation.
▸ Zig-Zig: Node and parent are both left (or both right) children → rotate parent first, then node.
▸ Zig-Zag: Node is left child, parent is right (or vice versa) → rotate node twice.

Before splaying node 1: After splaying 1 to root:

5 1
/ \ \
3 6 → 3
/ \ / \
1 4 2 5
\ / \
2 4 6

Node 1 is now at root — next access to 1 is O(1)!

Time & Space Complexity

Operation Time Complexity Space Complexity
 Search (amortized) O(log n) O(n)
Insert (amortized) O(log n) O(n)
Delete (amortized) O(log n) O(n)
Worst case single op O(n) O(n)
m operations O(m log n) O(n)

⭐ No balance information stored — simpler than AVL/RB. Best when access patterns are skewed (some
elements accessed much more than others).
Unit 2: Priority Queues and Heaps
A Priority Queue is an abstract data type where each element has a priority, and elements with higher
priority are served before lower-priority ones. The structures in this unit implement priority queues in
increasingly sophisticated ways.

📚 PREREQUISITES
Priority Queue: Like a hospital triage — critical patients are treated first regardless of arrival
order.
Binary Heap: Already covered in Unit 1 — a complete binary tree with heap property. This is
the simplest priority queue.
Amortized Analysis: Averaging cost over many operations. If 99 operations are O(1) and 1
is O(n), amortized cost per operation is still O(1).
Potential Function: A mathematical tool to measure "stored work" in a data structure, used
in amortized analysis.

2.1 Double-Ended Priority Queue (DEPQ)

A regular priority queue lets you access either the minimum OR the maximum. A Double-Ended Priority
Queue (DEPQ) supports access to BOTH the minimum and maximum efficiently.

💡 When do you need a DEPQ?

Imagine a hospital that prioritizes both the most critical (maximum priority) AND the least
critical for discharge (minimum priority). A DEPQ handles both ends.

Implementation Approaches
▸ Dual Heap: Maintain both a Min-Heap and Max-Heap simultaneously, with cross-pointers
between them.
▸ Interval Heap: Each node stores (min, max) pair. Even-index positions track minimums, odd-
index positions track maximums.
▸ Min-Max Heap: Alternate heap property by level — even levels are min-levels, odd levels are
max-levels.

Min-Max Heap Illustration

Min-Max Heap (levels alternate min/max):

Level 0 (MIN): 2 ← smallest element

/ \
Level 1 (MAX): 12 10 ← two largest elements
/ \
Level 2 (MIN): 6 8 ← local minimums

Find-Min: O(1) → root (2)

 Find-Max: O(1) → max of root's children (12)

Time & Space Complexity

Operation Time Complexity Space Complexity
Find-Min O(1) O(n)
Find-Max O(1) O(n)
Insert O(log n) O(n)
Delete-Min O(log n) O(n)
Delete-Max O(log n) O(n)

2.2 Leftist Trees

A Leftist Tree is a heap-ordered binary tree with a bias: it's intentionally "left-heavy". Every right path
is as short as possible, concentrating all "depth" on the left side. This makes merging two heaps very
efficient — something binary heaps are terrible at.

The s-value (Right-Spine Length)

Each node stores s(x) = length of the rightmost path to a NULL. The leftist property: s(left child) ≥
s(right child) for every node. This means the right spine is always short.

Leftist Tree (numbers in brackets = s-value):

2 [3]
/ \
4 [2] 6 [1] ← left s-val ≥ right s-val ✓
/ \ \
8[1] 12[1] 10[1]
/
15[1]

Right spine: 2 → 6 → 10 → NULL (only 3 steps!)

Right spine length ≤ log₂(n+1)

Merging Two Leftist Trees

▸ Step 1: If either tree is empty, return the other.
▸ Step 2: Make the smaller root the new root (heap property).
▸ Step 3: Recursively merge the right subtree of new root with the other tree.
▸ Step 4: If s(left) < s(right) after merge, swap left and right children.

Time & Space Complexity

 Operation Time Complexity Space Complexity
Merge O(log n) O(n)
Insert (merge with singleton) O(log n) O(n)
Delete-Min O(log n) O(n)
Find-Min O(1) O(n)

2.3 Binomial Heaps

A Binomial Heap is a collection of Binomial Trees that together represent a number in binary. A
Binomial Tree B_k has exactly 2^k nodes and is defined recursively:

B_0: [A] (1 node = 2^0)

B_1: [A] (2 nodes = 2^1)

/
[B]

B_2: [A] (4 nodes = 2^2)

/ \
[B] [C]
/
[D]

B_3: Root with B_2, B_1, B_0 as children (8 nodes = 2^3)

A Binomial Heap with n=13 elements = B_3 + B_2 + B_0

(because 13 = 8 + 4 + 1 = 1101 in binary)

Key Insight
Just as binary addition works digit by digit, merging two Binomial Heaps works exactly like binary
addition — combining trees of same rank, carrying over. This makes merge O(log n).

Time & Space Complexity

Operation Time Complexity Space Complexity
Find-Min O(log n) O(n)
Insert (amortized) O(1) O(n)
Delete-Min O(log n) O(n)
Merge O(log n) O(n)
Decrease-Key O(log n) O(n)

2.4 Fibonacci Heaps

The Fibonacci Heap is the most efficient heap known for many operations. Named after the Fibonacci
sequence because trees in it can have sizes resembling Fibonacci numbers. It's the theoretical backbone
of Dijkstra's shortest path and Prim's MST in their optimal forms.

💡 The Key Trick — Lazy Consolidation

Fibonacci Heaps delay cleanup ("consolidation") until absolutely necessary. Insert and
decrease-key are incredibly fast because they barely do any work — they just dump tasks
for later. When delete-min finally runs, it does the cleanup.

Structure
▸ A collection of heap-ordered trees (not necessarily binomial) linked in a circular doubly-linked
list.
▸ Min-pointer always points to the minimum element — O(1) access.
▸ Trees can be any shape; consolidation brings order when needed.

Time & Space Complexity (Amortized)

Operation Time Complexity Space Complexity
Find-Min O(1) O(n)
Insert O(1) amortized O(n)
Merge O(1) amortized O(n)
Decrease-Key O(1) amortized O(n)
Delete-Min O(log n) amortized O(n)
Delete O(log n) amortized O(n)

⭐ This is why Dijkstra's with Fibonacci Heaps is O((V + E) log V) — the best known.

2.5 Skew Heaps

A Skew Heap is a self-adjusting Leftist Tree — it's simpler because it doesn't track s-values. Instead,
it always swaps left and right children during merge. This unconditional swap keeps the tree
approximately balanced over time.

💡 Skew vs Leftist
Leftist Trees check if a swap is needed; Skew Heaps always swap. The result is simpler
code and similar performance — just slightly less predictable per operation but same
amortized bounds.

Merge Operation (Skew Heaps)

▸ Step 1: If either is empty, return the other.
 ▸ Step 2: Make the smaller root the new root.
▸ Step 3: Set new root's left child = result of recursively merging old left child with the other tree.
▸ Step 4: ALWAYS swap left and right children of new root.

Time & Space Complexity

Operation Time Complexity Space Complexity
Merge (amortized) O(log n) O(n)
Insert (amortized) O(log n) O(n)
Delete-Min (amortized) O(log n) O(n)
Find-Min O(1) O(n)

2.6 Pairing Heaps

Pairing Heaps are the simplest yet most practically efficient heaps. They outperform Fibonacci Heaps
in practice despite having the same theoretical bounds (for most operations). The structure is just a heap-
ordered tree with children in a linked list.

Operations
▸ Merge: Compare roots → smaller root becomes new root → other tree becomes leftmost child.
Incredibly simple!
▸ Insert: Create singleton → merge with existing heap. O(1).
▸ Delete-Min: Remove root → pair up children from left to right → merge pairs right to left. This
"two-pass pairing" is where the name comes from.

Delete-Min from pairing heap:

[1] Remove 1 (minimum)

/ | \ Children: 3, 5, 7, 9
3 5 7 9

Two-pass pairing:
Pass 1 (left to right): pair [3,5] → [3] with 5 as child
pair [7,9] → [7] with 9 as child
Pass 2 (right to left): merge [7,9] with [3,5] → [3] is root

Result: New heap rooted at 3 ✓

Time & Space Complexity

Operation Time Complexity Space Complexity
Find-Min O(1) O(n)
Insert O(1) amortized O(n)
Merge O(1) amortized O(n)
Decrease-Key O(log log n) O(n)
conjectured
Delete-Min O(log n) amortized O(n)
Unit 3: Data Structures for Strings
String data structures are specialized for storing and searching text efficiently. They power everything
from search engines to bioinformatics to autocomplete features.

📚 PREREQUISITES
String: A sequence of characters, e.g., "banana". Length usually denoted as n.
Substring: "ana" is a substring of "banana" — a contiguous part of the string.
Suffix: A suffix of "banana" is any string starting at position i to end: "banana", "anana",
"nana", "ana", "na", "a".
Prefix: String starting from the beginning up to some point.
Pattern matching: Given text T and pattern P, find where P appears in T.

3.1 String Searching Preliminaries

The naive approach to searching for pattern P (length m) in text T (length n) is to try every position —
giving O(nm) time. Smarter algorithms preprocess the pattern to skip unnecessary comparisons.

Key Algorithms Overview

▸ KMP (Knuth-Morris-Pratt): Preprocess pattern to build a "failure function" — when mismatch
occurs, skip back by known amount. O(n+m) time.
▸ Boyer-Moore: Search from right end of pattern. Use "bad character" and "good suffix"
heuristics. Often faster than KMP in practice.
▸ Rabin-Karp: Hash the pattern; slide hash over text. Pattern found when hashes match. O(n+m)
average.

Time & Space Complexity

Operation Time Complexity Space Complexity
Naive Search O(nm) O(1)
KMP O(n + m) O(m)
Boyer-Moore O(n/m) best, O(nm) O(m + σ)
worst
Rabin-Karp O(n + m) average O(1)

σ = alphabet size (e.g., 26 for English, 256 for ASCII)

3.2 DAWG (Directed Acyclic Word Graph)

A DAWG (also called CDFA — Complete Directed Factor Automaton) is the smallest automaton that
recognizes all substrings of a given string. It's like a compressed version of all substrings, sharing
common suffixes.

💡 Simple Analogy
A DAWG is like a subway map where trains going to the same destination share the same
track — it merges duplicated suffix paths into shared nodes.

String: "abbc"

All substrings: "", "a", "b", "bb", "bbc", "bc", "c",

"ab", "abb", "abbc"

DAWG nodes represent sets of ending positions.

Edges labelled with characters.

Start → a → (ab state) → b → (abb state) → b → (abbb state)

↓ ↘ ↓ ↓
b (b state) ←────────── (bb state) → c → End
↓ ↓
(bc) → c → End
↑
(c state) → End

DAWG has O(n) nodes and O(n) edges — optimal!

Time & Space Complexity

Operation Time Complexity Space Complexity
Build DAWG O(n × σ) O(n)
Search substring P O(|P|) O(n)
Number of nodes ≤ 2n - 1 —
Number of edges ≤ 3n - 4 —

3.3 Position Heaps

A Position Heap is a BST-like structure built on positions in a string. Each node represents a position
i in the text and stores the longest proper extension — a compact way to support suffix searching with
heap-like properties.

Position heaps occupy a middle ground between suffix trees (powerful but complex) and suffix arrays
(simpler but slower for some queries). They support pattern matching in O(|P|² + occ) time where occ is
the number of occurrences.

Time & Space Complexity

 Operation Time Complexity Space Complexity
Build O(n²) worst case O(n)
Pattern search O(|P|² + occ) O(n)
Space — O(n)

3.4 Tries and Compressed Tries

A Trie (Prefix Tree) is a tree where each edge represents a character. A path from root to any node
spells a string. It's ideal for autocomplete, spell checking, and IP routing

Trie for words: "cat", "cap", "car", "card", "care", "bat"

(root)
/ \
c b
| |
a a
/|\ |
t p r t * ← * marks end of word
* * \
d e
* *

Search "care": root→c→a→r→e = found ✓

Search "can" : root→c→a→n = not found ✗

Compressed Trie (Patricia Trie / Radix Tree)

Regular tries waste space on single-child nodes. A Compressed Trie merges chains of single-child
nodes into single edges labelled with substrings:

Regular Trie: Compressed Trie:

r→o→a→d r→"oad"→*
r→o→b→o→t r→"o"→[a→"d", b→"ot"]

Regular trie: O(total chars) nodes

Compressed trie: O(n) nodes where n = number of strings

Time & Space Complexity

Operation Trie Compressed Trie Note
Search O(|P|) O(|P|) P = pattern length
Insert O(|S|) O(|S|) S = string length
Space O(n × σ) O(n) n = total strings
3.5 Suffix Trees and Suffix Arrays
Suffix Trees
A Suffix Tree is a compressed trie of all suffixes of a string. It's the Swiss Army knife of string algorithms
— once built, it answers almost any string query in linear time.

String: "banana$" ($ = sentinel, unique end character)

All suffixes: banana$, anana$, nana$, ana$, na$, a$, $

Suffix Tree (compressed, showing edge labels):

(root)
/ / \ \ \
$ "a" "b" "na" "n"
| | | |
(leaf) "na" "nana$" "ana$"
/ \
"na$" "$"
| |
(leaf) (leaf)

Each leaf = one suffix. Internal nodes = repeated substrings.

Depth of internal node = length of longest common prefix of suffixes
below it.

🔥 What Suffix Trees Can Solve in O(n) or O(m) Time

• Find pattern P in text T: O(|P|) after O(n) build time
• Longest repeated substring
• Longest common substring of two strings
• Count occurrences of P: O(|P| + occ)
• Find all palindromes

Suffix Arrays
A Suffix Array is a sorted array of all suffix starting positions. It's more memory-efficient than suffix
trees (just integers!) and almost as powerful when paired with an LCP (Longest Common Prefix) array

String: "banana" (positions: b=0, a=1, n=2, a=3, n=4, a=5)

Suffixes sorted alphabetically:

Suffix Array SA: [5, 3, 1, 0, 4, 2]
SA[0]=5 → "a"
SA[1]=3 → "ana"
SA[2]=1 → "anana"
SA[3]=0 → "banana"
SA[4]=4 → "na"
SA[5]=2 → "nana"
 LCP Array: [-, 1, 3, 0, 0, 2]
LCP[i] = longest common prefix of SA[i-1] and SA[i]
LCP[2]=3 because "ana" and "anana" share "ana" (length 3)

Pattern search "ana": binary search on SA → O(|P| log n)

Time & Space Complexity

Operation Suffix Tree Suffix Array

Build O(n) O(n log n) or O(n)

Pattern search O(|P| + occ) O(|P| log n)
Space O(n × σ) O(n)

3.6 Dictionaries Allowing Errors in Queries

Sometimes users make typos ("speling" instead of "spelling"). These data structures handle
approximate matching — finding strings within a given edit distance of the query.

📚 Edit Distance (Levenshtein Distance)

The minimum number of single-character operations (insert, delete, substitute) to transform
one string into another.
"kitten" → "sitting" requires 3 operations → edit distance = 3

Approaches
▸ BK-Tree (Burkhard-Keller Tree): A tree where edge weights are edit distances. Searches
prune branches where distance can't possibly be within threshold. O(log n) average for queries
with small error tolerance.
▸ Trie + DFA: Convert the query into a Levenshtein automaton (a finite automaton accepting all
strings within distance k of query). Walk the trie with this automaton — prune impossible
branches.
▸ Spell-Correction using n-grams: Index strings by character n-grams; query returns candidates
sharing many n-grams with query.

Time & Space Complexity (BK-Tree)

Operation Time Complexity Space Complexity
Build O(n log n) O(n)
Query (error ≤ k) O(n^(k/d)) avg O(n)
Query (exact, k=0) O(log n) O(n)

d = average branching degree, k = error threshold. In practice, for k=1 or k=2, BK-trees are very fast.
Unit 4: Randomized Data Structures
Randomized data structures use random choices (coin flips, dice rolls) to achieve good expected
performance without needing complex deterministic balancing rules. They are often simpler to
implement than their deterministic counterparts.

📚 PREREQUISITES — Probability Basics

Expected Value: The average outcome over many random trials. E[X] = sum of x × P(X=x).
With High Probability (w.h.p.): An event that occurs with probability ≥ 1 - 1/n^c for some
constant c > 0.
Geometric Distribution: If P(success) = p, expected number of trials until success = 1/p.
Independence: Two events A and B are independent if P(A and B) = P(A) × P(B).
Las Vegas algorithm: Always correct, random in running time (e.g., Skip Lists).
Monte Carlo algorithm: Correct with high probability, fixed running time.

4.1 Preliminaries: Randomized Algorithms

The power of randomization lies in breaking adversarial worst cases. A deterministic algorithm has a
fixed worst-case input; a randomized algorithm randomizes its behaviour so no fixed input is always bad.

💡 Why Use Randomization?

QuickSort always takes O(n²) on sorted input if you always pick the first element as pivot.
But if you pick a RANDOM pivot, sorted input is no longer a worst case — the expected time
is O(n log n) for any input!

Key Probability Facts for Analysis

▸ Union Bound: P(A or B) ≤ P(A) + P(B). Used to bound the probability that anything bad
happens.
▸ Markov's Inequality: P(X ≥ t) ≤ E[X]/t. If expected value is small, large values are rare.
▸ Linearity of Expectation: E[X+Y] = E[X] + E[Y] — even if X and Y are not independent!

4.2 Skip Lists

A Skip List is a layered linked list where higher layers act as "express lanes" skipping over many
elements. It's a probabilistic alternative to balanced trees — simpler to implement, same expected
performance.

💡 Simple Analogy
 Imagine a city with multiple subway lines. Line 1 stops at every block. Line 2 stops every 4
blocks. Line 4 stops every 16 blocks. To reach block 100 quickly, take Line 4 most of the
way, then transfer to Line 2, then Line 1. Skip Lists work the same way!

Structure
Skip List for: 1, 3, 5, 7, 9, 11, 13

Level 3: -∞ ────────────────────────────── 9 ──── +∞

Level 2: -∞ ─────────── 5 ─────────────── 9 ──── +∞
Level 1: -∞ ─── 3 ───── 5 ───── 7 ────── 9 ─ 11 +∞
Level 0: -∞ 1 ─ 3 ─ 5 ─ 5 ─ 7 ─ 9 ─ 11 ─ 13 ─ +∞ (base list)

Search for 7:
Level 3: -∞ → 9 (too big!) drop down
Level 2: -∞ → 5 → 9 (too big!) drop down
Level 1: 5 → 7 → found! ✓

Only 4 comparisons instead of scanning all 7 elements.

Structural Properties
▸ Each element: Is in Level 0 (base list) with probability 1.
▸ Promotion: Each element is promoted to the next level with probability p (usually ½).
▸ Expected height: O(log n) levels.
▸ Expected nodes per level: Level i has expected n × p^i nodes.

Space Complexity Analysis

Total expected nodes across all levels: n × (1 + p + p² + ...) = n/(1-p). For p=½, this is 2n — O(n) expected
space. Maximum height is O(log n) with high probability.

Time & Space Complexity

Operation Time Complexity Space Complexity
Search (expected) O(log n) O(n) expected
Insert (expected) O(log n) O(n) expected
Delete (expected) O(log n) O(n) expected
Space (expected) — O(n)
Space (worst case) — O(n log n)

4.3 Treap — A Randomized BST

A Treap is a tree + heap hybrid. Each node has two keys:
▸ BST key: Determines left/right ordering (the actual data you're storing).
 ▸ Priority: Assigned randomly when inserted. Determines parent/child ordering (heap property).

The random priorities ensure the tree stays balanced without any explicit rebalancing — it self-
balances probabilistically!

Treap with (key, priority) pairs:

(E, 90) ← highest priority = root

/ \
(B, 70) (H, 80)
/ \ \
(A,30) (D,50) (J, 40)
/ \
(C, 20) (K, 10)

BST property holds for keys: A<B<C<D<E<H<J<K ✓

Max-Heap property holds for priorities: each parent > children ✓

Why Does Randomization Keep It Balanced?

A random permutation of keys, inserted into a BST, gives expected height O(log n). The Treap achieves
the same distribution by assigning random priorities and maintaining heap order — equivalent to inserting
keys in random priority order!

Rotations for Insert/Delete

▸ Insert: Insert as in BST → assign random priority → use rotations to bubble up until heap
property holds.
▸ Delete: Decrease node's priority to -∞ → rotate it down until it becomes a leaf → remove it.

Time & Space Complexity

Operation Time Complexity Space Complexity
Search (expected) O(log n) O(n)
Insert (expected) O(log n) O(n)
Delete (expected) O(log n) O(n)
Height (expected) O(log n) —
Height (w.h.p.) O(log n) —

⭐ Treaps are simpler to implement than AVL or Red-Black trees — just one type of balancing operation
(rotation) triggered by random priorities.
Unit 5: Multidimensional Spatial Data Structures
Standard data structures (arrays, trees, hash tables) work on one-dimensional data. Spatial data
structures handle multi-dimensional data — points, rectangles, regions in 2D, 3D, or higher dimensional
space. They power GPS navigation, game engines, computer graphics, and GIS systems.

📚 PREREQUISITES
Point: A location in space, e.g., (x, y) in 2D or (x, y, z) in 3D.
Bounding Box: The smallest rectangle enclosing a set of points.
Range Query: Find all points within a given region (e.g., rectangle or circle).
Nearest Neighbor: Find the point closest to a given query point.
Spatial Partitioning: Dividing space into regions to organize data.

5.1 Introduction to Spatial Data

The fundamental challenge: standard BSTs compare one dimension at a time. For 2D data, you need to
compare both x and y simultaneously. Spatial data structures cleverly alternate or combine
dimensional comparisons.

Three Types of Spatial Data

▸ Point Data: Individual points in space. E.g., GPS coordinates, star positions.
▸ Region Data: Areas or volumes. E.g., country boundaries, weather zones.
▸ Rectangle Data: Axis-aligned rectangles. E.g., screen windows, bounding boxes of objects.

Common Query Types

▸ Point Query: "Is point P in the dataset?"
▸ Range Query: "Find all points inside rectangle R."
▸ Nearest-Neighbor Query: "Find the closest point to query point Q."
▸ Intersection Query: "Which rectangles overlap with R?"

5.2 Point Data

For point data, we need structures that can answer "which points fall in this region?" efficiently without
scanning every point.

K-D Tree (K-Dimensional Tree)

A K-D Tree is a binary tree where each node splits space along one axis. Levels alternate between axes:

2D K-D Tree for points: (3,1),(5,4),(2,3),(7,2),(4,7),(8,5)

 Level 0 (split by x=5): Left has x<5, Right has x≥5

(5,4) ← split x=5

/ \
(2,3) (7,2) ← split y=3 split y=2
/ \ / \
(3,1) (4,7)(8,5) nil

Range query "find points in box [1..6] × [0..4]":

At (5,4): 5 ≤ 6 so check both sides
At (2,3): 3 ≤ 4 → explore; (2,3) in box ✓
At (3,1): (3,1) in box ✓
At (4,7): 7 > 4 → prune right subtree ✗
At (7,2): 7 > 6 → prune entire subtree ✗

Found: (2,3), (3,1) without checking (8,5) — saved work!

Time & Space Complexity (K-D Tree)

Operation Time Complexity Space Complexity
Build O(n log n) O(n)
Nearest Neighbor O(√n) average, O(n) O(log n) stack
worst
Range Query (r results) O(√n + r) in 2D O(log n)
Insert O(log n) average O(n)

5.3 Region Data and Rectangle Data

For regions and rectangles, we need structures that can efficiently find all rectangles overlapping a
query point or region

R-Tree (Rectangle Tree)

An R-Tree groups nearby rectangles into Minimum Bounding Rectangles (MBRs) hierarchically — like
a B-Tree but for spatial data:

R-Tree structure:

Root MBR: [covers all data]

/ \
MBR₁ [covers group 1] MBR₂ [covers group 2]
/ \ / \
Rect₁ Rect₂ Rect₃ Rect₄ Rect₅

Query "find all rectangles overlapping point P":

1. Check if P in Root MBR → yes, continue
2. Check if P in MBR₁ → yes; check if P in MBR₂ → no, prune!
 3. Check Rect₁, Rect₂, Rect₃ individually

Pruning entire branches saves huge amounts of work!

Time & Space Complexity (R-Tree)

Operation Time Complexity Space Complexity
Search (best case) O(log n) O(n)
Search (worst case) O(n) O(n)
Insert O(log n) O(n)
Delete O(log n) O(n)

5.4 Quad Trees and Octrees

Quad Tree for Point Data
A Quad Tree divides 2D space into four quadrants (NW, NE, SW, SE) recursively until each region
contains at most one point. It's the simplest 2D spatial index.

💡 Simple Analogy
It's like folding a map in half vertically and horizontally — each fold creates 4 sections. If a
section has too many cities, fold it again. Keep folding until each section has at most 1 city.

Inserting points: A(1,7), B(5,8), C(3,5), D(7,3), E(2,2)

Space: [0..8] × [0..8]

After first split (midpoint = 4,4):

NW quadrant [0..4]×[4..8]: A(1,7), B(5,8)... wait B is in NE
NW: A(1,7), C(3,5)
NE: B(5,8)
SW: E(2,2)
SE: D(7,3)

NW has 2 points → split NW again:

[Link] [0..2]×[6..8]: A(1,7)
[Link] [2..4]×[4..6]: C(3,5)

Quad Tree:
[root: 0..8]
/ | | \
NW NE SW SE
/ \ | | |
A C B E D

Octree
An Octree is the 3D version of a Quad Tree — it divides 3D space into 8 octants (up/down × left/right ×
front/back). Used in 3D graphics, collision detection, and 3D game engines.

Octree division (8 children per node):

+--------+--------+
/| Top /| Top /|
/ | Left / | Right/ |
+--------+--------+ |
| | | | | |
| Bot | Bot | |
| Left | Right | /
|/ |/ |/
+--------+--------+

Each cube splits into 8 sub-cubes when it has > threshold points.

Time & Space Complexity (Quad Tree)

Operation Time Complexity Space Complexity
Insert O(log(1/ε)) for O(n)
resolution ε
Point Query O(log(1/ε)) O(n)
Range Query O(√n + r) in 2D O(n)
Depth (n points, min sep d) O(log(1/d)) —

⭐ Quad trees work best when points are uniformly distributed. Highly clustered data creates deep,
unbalanced quad trees.
Unit 6: Miscellaneous Data Structures
This unit covers advanced and specialized data structures used in modern large-scale systems, including
Google's BigTable, space-efficient data representations, and persistent data structures that preserve
history.

📚 PREREQUISITES
Bit Vector: An array of bits (0s and 1s). Very compact — stores n values using n/8 bytes.
Rank query: rank(i) = number of 1s in the first i bits.
Select query: select(j) = position of the j-th 1 bit.
Entropy: A measure of information content / compressibility. Low entropy = lots of repetition
= compresses well.
Persistence: A data structure is persistent if it preserves all previous versions after updates.
Path copying: When updating a persistent structure, copy only the nodes on the path from
root to changed node.

6.1 Google's Bigtable

Bigtable is Google's distributed, scalable storage system for structured data, designed to handle
petabytes of data across thousands of servers. It powers Google Search, Maps, Gmail, and YouTube.

💡 Simple Analogy
Imagine a giant spreadsheet with billions of rows and millions of columns. But you can't have
all combinations — most cells are empty. And the spreadsheet automatically distributes itself
across thousands of computers, reorganizing as needed.

Key Concepts
▸ Table: A sparse, distributed, persistent, multi-dimensional sorted map.
▸ Row key: Arbitrary byte string (up to 64KB). Rows sorted lexicographically by row key.
▸ Column key: Format "family:qualifier". Column families defined at schema time; qualifiers can
be anything.
▸ Timestamp: Each cell can have multiple timestamped versions of data.

Bigtable data model:

Row Key | Column Family: col | Timestamp | Value

──────────────┼─────────────────────┼───────────┼──────────
[Link] | content:html | t9 | "<html>..."
[Link] | content:html | t5 | "<html>..." (old
version)
[Link] | anchor:[Link] | t9 | "CNN"
[Link] | anchor:[Link] | t8 | "[Link]"
[Link]| content:html | t7 | "<html>..."
 Row keys reversed domain names ([Link]) → related pages cluster
together!

Access: (row, column_family, qualifier, timestamp) → value

Architecture
▸ Tablets: Table split into row ranges called tablets (~100-200MB each). Each tablet served by
one tablet server.
▸ Tablet Server: Manages ~10-1000 tablets. Handles read/write requests.
▸ Master Server: Assigns tablets to tablet servers, load balancing, garbage collection.
▸ GFS (Google File System): Underlying storage. Tablet servers store SSTables (sorted string
tables) on GFS.
▸ Chubby: Distributed lock service for coordination.

Time & Space Complexity

Operation Time Complexity Space Complexity
Point read (by row key) O(1) avg after Distributed
tablet location
Range scan O(k) for k rows Distributed
Write (single row) O(1) amortized Distributed
Scaling Linear with servers Petabytes total

6.2 Succinct Representation of Data Structures

A succinct data structure uses space as close as possible to the information-theoretic minimum
(i.e., the entropy lower bound) while still supporting fast queries — unlike compressed structures that
must decompress before querying.

📐 Information-Theoretic Lower Bound

A binary string of length n requires at most n bits. A set of k items from n requires
⌈log₂(C(n,k))⌉ bits minimum. A succinct structure uses this minimum + O(lower order) bits.

6.2.1 Bit Vectors

A bit vector B[0..n-1] supports two fundamental operations used by almost all succinct structures:
▸ rank₁(i): Count of 1s in B[0..i]. ("How many 1s up to position i?")
▸ select₁(j): Position of the j-th 1. ("Where is the j-th set bit?")

Bit vector B: 0 1 1 0 1 0 0 1 1 0
Index: 0 1 2 3 4 5 6 7 8 9
 rank₁(4) = 3 (bits B[0..4] = 0,1,1,0,1 → three 1s)
rank₁(7) = 4 (bits B[0..7] → four 1s)

select₁(1) = 1 (first 1 is at index 1)

select₁(3) = 4 (third 1 is at index 4)
select₁(4) = 7 (fourth 1 is at index 7)

Efficient Implementation with Precomputed Tables

Naive rank takes O(n); with a two-level precomputed index we get O(1) rank and O(log n) select:
▸ Divide B into blocks of size log²(n).
▸ Store cumulative rank at start of each block.
▸ Within each block, divide into subblocks of size ½ log(n).
▸ Store rank from block start to each subblock start.
▸ Use a lookup table for within-subblock rank (table has at most log(n) rows).

Time & Space Complexity (Bit Vector with Rank/Select)

Operation Time Complexity Space Complexity
rank(i) O(1) n + O(n log log n /
log n) bits
select(j) O(log n) Same as above
Space overhead — O(n log log n / log
n) extra bits

6.3 Succinct Dictionaries

A succinct dictionary stores a set S of k elements from universe [0..n-1] using ⌈log₂(C(n,k))⌉ bits —
exactly the information-theoretic optimum — while supporting membership queries (is x in S?) in O(1).

Approaches
▸ Bloom Filters: Use multiple hash functions to set bits in a bit array. Fast but has false positives
(never false negatives). Space: O(n) bits. Query: O(k) for k hash functions.
▸ Perfect Hashing: No collisions! Two-level hashing scheme with O(n) space and O(1) worst-
case lookup.
▸ FKS Hashing (Fredman-Komlós-Szemerédi): Static perfect hashing achieving O(1) worst-
case with O(n) space.

Bloom Filter Example:

Set: {"apple", "banana", "cherry"}

Bit array size m=16, hash functions h1, h2, h3
 Insert "apple": h1("apple")=3, h2("apple")=7, h3("apple")=12
Bit array: 0 0 0 1 0 0 0 1 0 0 0 0 1 0 0 0

Insert "banana": h1("banana")=5, h2("banana")=7, h3("banana")=14

Bit array: 0 0 0 1 0 1 0 1 0 0 0 0 1 0 1 0

Query "apple": check bits 3,7,12 → all 1 → "probably in set" ✓

Query "grape": check bits (say) 3,8,14 → bit 8 is 0 → "definitely NOT in
set" ✓
Query "mango": check bits 3,7,14 → all 1 → "probably in set" ← FALSE
POSITIVE!

Time & Space Complexity

Operation Time Complexity Space Complexity
Bloom Filter query O(k) hash functions O(m) bits
Bloom Filter false positive ≈ (1-e^(-kn/m))^k —
rate
Perfect Hashing query O(1) worst case O(n)
Succinct Dictionary query O(1) ≈ log C(n,k) bits

6.4 Succinct Tree Representations

Binary trees with n nodes have C(2n, n)/(n+1) ≈ 4^n / n^(3/2) possible shapes, requiring 2n − O(log n)
bits to represent optimally. Succinct tree representations use exactly ~2n bits while supporting all
standard operations.

LOUDS (Level-Order Unary Degree Sequence)

LOUDS represents a tree by writing each node's degree in unary, level by level:
▸ For each node: Write degree-d as d ones followed by a 0. Example: degree 3 → "1110",
degree 0 (leaf) → "0".
▸ Process nodes in BFS (level) order.

Tree: 1 LOUDS construction:

/ | \ Node 1 (root, degree 3): 1110
2 3 4 Node 2 (degree 2): 110
/ \ Node 3 (degree 0, leaf): 0
5 6 Node 4 (degree 0, leaf): 0
Node 5 (degree 0, leaf): 0
Node 6 (degree 0, leaf): 0

LOUDS string: 10 1110 110 0 0 0 0

↑ ↑ ↑ ↑ ↑ ↑ ↑
virtual root 1 2 3 4 5 6

Navigate with rank/select on this bit string — O(1) per navigation step!
Time & Space Complexity
Operation Time Complexity Space Complexity
Space (n-node tree) 2n + o(n) bits —
Parent query O(1) O(n) bits
i-th child query O(1) O(n) bits
Subtree size O(1) O(n) bits

6.5 Persistent Data Structures

A persistent data structure preserves all previous versions when modified. You can always go back in
time and query any past state.

💡 Real-world examples
Git version control is a persistent data structure — every commit is a snapshot, and you can
checkout any past version. Functional programming languages like Haskell and Clojure rely
on persistent data structures for immutability.

Types of Persistence
▸ Partial Persistence: All versions can be read, but only the latest can be modified. Like reading
but not editing old books.
▸ Full Persistence: Any version can be read AND modified, creating new branches. Like a Git
tree.
▸ Confluent Persistence: Two versions can be merged into one. Git merge!

Path Copying (Making Any BST Persistent)

When you update a node in a BST, instead of modifying it, copy every node on the path from root to
that node. The new root points to the new copies; old root still points to old nodes — both versions
coexist!

Original BST (version 1): After inserting 4 (version 2):

5 (v1 root) 5 (v2 root, new copy)

/ \ / \
3 7 (new)3* 7 (shared!)
/ / \
1 1 4 (new)

v1 root → 5(old) → 3(old) → 1 (still accessible!)

v2 root → 5(new) → 3(new) → 1 (1 is shared!)
\→ 4 (new)

Only O(log n) new nodes created per update!

Time & Space Complexity
Operation Time Complexity Space Complexity
Query any version O(log n) per query O(1) per version
pointer
Update (path copying) O(log n) O(log n) new nodes
per update
Space after m updates — O(n + m log n)
Fat Nodes (alt. approach) O(log m) per query O(n + m) total

⭐ Persistent BSTs with path copying: O(log n) time and O(log n) extra space per update — close to
optimal!
Quick Reference: All Data Structures at a Glance
Data Structure Time Complexity Space Best Use Case
Threaded Binary O(n) traverse O(1) stack Stack-free traversal
Tree space
AVL Tree O(log n) all ops O(n) Read-heavy workloads
Red-Black Tree O(log n) all ops O(n) Write-heavy workloads
Heap (Binary) O(log n) ins/del, O(1) peek O(n) Priority queues
Huffman Tree O(n log n) build O(n) Data compression
B-Tree O(log n) all ops O(n) Disk storage, databases
B+ Tree O(log n) + O(k) range O(n) Database indexing
Splay Tree O(log n) amortized O(n) Cache-friendly access
DEPQ (Min-Max O(log n) ins/del, O(1) find O(n) Two-ended priority
Heap)
Leftist Tree O(log n) merge O(n) Mergeable heaps
Binomial Heap O(log n) merge/del, O(1) ins O(n) Frequent merges
amort
Fibonacci Heap O(1) amort ins/decrease, O(log O(n) Dijkstra / Prim optimal
n) del
Skew Heap O(log n) amortized O(n) Simple mergeable heap
Pairing Heap O(1) amort ins, O(log n) del O(n) Practical Fibonacci
alt.
Trie O(|P|) search/insert O(n × σ) Autocomplete, prefix
search
Compressed Trie O(|P|) search/insert O(n) Memory-efficient trie
Suffix Tree O(n) build, O(|P|) search O(n × σ) All substring queries
Suffix Array O(n log n) build, O(|P| log n) O(n) Space-efficient suffix
search
DAWG O(n) build, O(|P|) search O(n) Substring recognition
BK-Tree O(n^(k/d)) query O(n) Fuzzy string search
Skip List O(log n) expected O(n) expected Simple probabilistic
BST
Treap O(log n) expected O(n) Randomized BST
K-D Tree O(log n) insert, O(√n) range O(n) 2D/3D point queries
Quad Tree O(log(1/ε)) insert O(n) 2D spatial partitioning
R-Tree O(log n) avg search O(n) Rectangle/region
queries
Bigtable O(1) point read Petabytes Distributed storage
Bit Vector O(1) rank, O(log n) select n + o(n) bits Succinct foundation
(rank/select)
Bloom Filter O(k) O(m) bits Approximate membership
Persistent BST O(log n) all ops O(n + m log n) Version history