What is computational complexity?

What it is: a measure of how much effort an algorithm needs — how much it costs to run.

Why we use it: many algorithms can solve the same problem. We want to pick the cheapest one.

The two costs:

• Time — how long it takes. This is the most significant one for us.
• Space — how much memory it uses.

Why not just time it in seconds?

Because real time is unfair. It depends on things that have nothing to do with the algorithm:

• The machine — the same program runs faster on a home PC than on the lab PCs.
• The language — a compiled C++ program is much faster than the same program in Basic.

So to compare in real time, everything would have to run on the same machine. Instead, we use logical units: we describe the relationship between

• n = the size of the data (the file), and
• t = the time taken to process it.

Time / size relationships

Linear: t = c·n

Time grows at the same rate as the data. If the data doubles, the time doubles too.

Tiny example: if 10 items take 10 steps, then 20 items take 20 steps.

Logarithmic: t = log₂ n

Doubling the data adds just one time unit. This is very fast.

Tiny example: log₂ 8 = 3 steps. Double the data to 16 → log₂ 16 = 4 steps. Twice the data, only +1 step.

Asymptotic complexity

What it is: real cost formulas are messy. We only care what happens when n gets large. So we drop every term that stops mattering. What is left is the asymptotic complexity.

The slide example:

F(n) = n² + 100n + log₁₀n + 1000

Look at the pattern: for small n the constant 1000 is the biggest part (90.8%!). But as n grows, n² takes over — at n = 100,000 it is 99.9% of the whole value. So for large n, only n² matters:

F(n) ≈ n²  →  O(n²)

Big O, Big Ω, Big Θ

Three symbols for describing growth. They simplify complexity equations:

• Big O (Big Oh) — an upper bound. "It grows no faster than this." The one we use most.
• Big Ω (Big Omega) — a lower bound. "It grows at least this fast."
• Big Θ (Big Theta) — a tight bound. Upper and lower at the same time: "it grows exactly like this."

How to simplify

• Drop constant factors: O(2n) → O(n). O(½n²) → O(n²).
• Drop smaller terms: O(n² + 100n + 1000) → O(n²).

Example code — spot the complexity

Each block below is a growth rate you must recognize on sight.

Arrays — the simplest structure

What it is: a collection of elements sitting next to each other in memory. Each element has an index (a number key).

Why it's fast: finding an element is just math. If an int array starts at memory address 1000, and each int is 4 bytes:

address of a[i] = 1000 + 4 · i

Tiny example: a[5] lives at 1000 + 4·5 = 1020. One calculation → O(1) access. No searching.

Three ways to index

• Zero-based — first element is a[0]. This is C++.
• One-based — first element is a[1].
• N-based — start anywhere, even letters: Country[th] = "Thailand".

Dimensions & memory order

A single dimension array has 1 index: a[4]. A multidimensional array has more: a[2][3].

A 2D array is still stored in one flat row of memory. There are two orders:

Static vs dynamic arrays

• Static: memory given at COMPILATION TIME. Size is fixed forever. int a[10];
• Dynamic: memory given at RUN TIME. Size can be chosen while running. int* a = new int[10];

Dynamic memory must be given back: delete [] a;

A jagged array is an array of arrays where each row has a different size:

Array performance, benefits, limits

Benefits: good locality of reference (temporal + spatial → data caching works well), compact (low memory), and random access.

The limit: elements are locked in place, evenly spaced. Inserting inside means shifting other data. The fix for that → a linked structure.

Singly linked lists

What it is: a chain of nodes. Each node holds some data (info) and a pointer to the next node. A pointer head points to the first node. The last node points to NULL (0) to say "I am the end."

Why: no fixed size, and inserting/removing does not shift anything — we just re-aim pointers.

Building a small list by hand:

Insertion: head_insert & tail_insert

Two basic choices, also called push_front() and push_back().

head_insert — new node becomes the first node

1. Make the new node: Node* tmp = new Node(x);
2. Point it at the old first node: tmp->next = head;
3. Move head to it: head = tmp;

tail_insert — new node becomes the last node

Keep a second pointer tail aimed at the last node. Then: make the node, set tail->next = tmp;, move tail = tmp;. Same idea as head_insert, just at the other end.

Inserting in the middle: walk to the spot first, then re-aim two pointers. Compare with an array: no shifting needed!

Deletion — where the traps live

Delete from the head

Trap: if you run delete head; first, you lose your only way into the list! The safe 3 steps:

1. Node* tmp = head; — remember the old first node.
2. head = head->next; — move head to the 2nd node.
3. delete tmp; — now it is safe to free the old node.

Delete from the tail

Problem: the tail's predecessor (the node before it) must become the new tail, but a singly linked list has no backwards pointers. So we must walk from the start to find the second-to-last node:

Always check the special cases

• Empty list — deleting from it would crash. Test isEmpty() first.
• One-node list — after deleting, both head and tail must become NULL.

Efficiency

• Best case: deleteHead() = O(1).
• Worst case: deleteTail() = O(n) (walk the whole list).
• Average: between 1 and n → n/2 → O(n). Search (isInList()) is the same: best O(1), worst and average O(n).

Doubly linked lists

What: each node has two pointers — next and prev. You can walk both directions.

Why: the whole point is the tail. tail = tail->prev; finds the predecessor instantly, so deleting the tail becomes O(1) — no walking.

The cost: insertion and deletion must fix more pointers (easy to get wrong), and each node needs extra memory. Same special cases: empty list, one-node list.

Circular linked lists & circular arrays

Circular linked list: the last node points back to the first — no NULL, no real start or end. Just one current pointer into the ring.

Why: perfect for taking fair turns:

• Processors sharing one resource — each gets its turn as current moves around.
• A multiplayer board game (poker) — current tracks whose turn it is.

Circular array (ring buffer): the same turn-taking idea with an array. It is stored as a normal array plus two variables: the index of the first and last element. When we reach the end of the array, we wrap around and reuse the free cells at the start.

Arrays vs linked lists — who wins?

Both store linear data. Neither is "better" — it depends on the job.

Sparse tables — the CMU grades story

What it is: a table that is mostly empty. Storing it as a full 2D array wastes huge space.

The slide example: store a grade for every CMU student in every course.

• ~25,000 students × ~1,000 courses × 1 byte per grade = 25,000,000 bytes.
• But students take about 7 courses each: 25,000 × 7 = 175,000 bytes of real data.
• 175,000 ÷ 25,000,000 = 0.007 → 99.3% of the table is empty!

Fix 1: two arrays

ClassesTaken (classes for each student) and StudentsInClasses (students in each class). Assuming max 8 classes each and max 200 students per class, 3 bytes per entry: 600,000 + 600,000 = 1,200,000 bytes — under 5% of the original.

But: what if a student takes more than 8 classes? Or a class has more than 200 students? Fixed limits are guesses.

Fix 2: linked lists

Use two arrays of linked lists (one list per student, one per class). No limits to guess, and even more space saved.

Example code — a working singly linked list

Stacks — LIFO

What it is: a linear structure you can only touch at one end — the top. New data goes on the top. Data also comes off the top.

Picture it: a stack of trays in the canteen. You take the tray that was put there last. That rule is called LIFO — Last In, First Out.

The 5 key operations

• clear() — empty the stack.
• isEmpty() — is it empty?
• push(el) — put el on the top.
• pop() — take the top element off (and give it back).
• topEl() — look at the top element without removing it.

Stack use: matching delimiters

A compiler must check that ( ), [ ], { }, /* */ are matched correctly. The rule:

• See an opener → push it.
• See a closer → pop; it must match. (Pop from empty = error.)
• At the end, the stack must be empty.

Case A (from the slide) — success: while(m<(n[8] + o)) {p=7; /*initialise p*/ r=6;}

Case B — error: a = b + ( c − d ) * ( e − f )) — the final ) arrives when the stack is already empty. Nothing to pop → error.

Implementing a stack: vector or linked list?

Both work. Here is the vector version from the slides:

The linked-list version is the same idea, but stores elements in a list<T> instead of a vector<T>.

Comparison (exam favourite)

• The linked list matches the stack more closely — no unused "capacity". In the vector version, capacity can be larger than the size.
• Push and pop are O(1) in both.
• But: pushing to a full vector forces it to allocate new memory and copy everything across — O(n) for that one push.

The STL stack (Standard Template Library)

Key members: empty(), pop(), push(el), size(), top().

Careful: STL pop() is void — it removes the top element but does not return it. Read it with top() first.

Queues — FIFO

What it is: a waiting line that uses both ends: data is added at one end and taken from the other. Like a queue in a bank. The rule is FIFO — First In, First Out.

The 5 key operations

• clear() — empty the queue.
• isEmpty() — is it empty?
• enqueue(el) — add el to the end of the line.
• dequeue() — take the first element out.
• firstEl() — look at the first element without removing it.

Why: simulating real queues — e.g. how many bank staff keep service good, or how many toll kiosks to open.

Queue in an array → the circular array

The problem: in a plain array, every dequeue frees a cell at the front — and that space is never used again. The queue slides down the array and runs out of room.

The fix: a circular array. It's really a normal one-dimensional array plus two index variables, first and last. When we hit the end of the array, we wrap around and reuse the free cells at the start. The "circle" is just how we picture it.

The extra work is in enqueue() / dequeue(): check if we are at the last cell, and make sure we never overwrite the first element.

Better queue: the doubly linked list

With a doubly linked list, adding at one end and removing at the other are both O(1) — we hold pointers to both ends and can step from them directly.

With a singly linked list, one of the two ends needs an O(n) walk to reach its neighbour. That's why doubly wins here.

The STL queue's key members: back(), empty(), front(), pop(), push(el), size().

Priority queues

Why: real queues are rarely fair. A police car reaches the toll — it goes first. In a priority queue, elements leave based on their priority and their current position, not just arrival order.

Ways to build one

Heaps — a first look

What it is: a kind of binary tree where:

• every node's value is greater than or equal to the values in its children, and
• the tree is perfectly balanced — the last-level leaves are pushed to the leftmost positions.

As a priority queue: the value = the priority, so the root is always the highest priority.

Enqueue (add)

1. Add the new element at the bottom of the heap, as a leaf.
2. Let it climb up: swap it with its parent while it has higher priority.

Dequeue (remove the best)

1. Remove the root — the highest priority.
2. Move the last node into the root's place.
3. Let it sink down: swap with its bigger child until it fits.

Each move follows one path up or down the tree — and the tree is short (that's the balance). Compare that with the O(n) linked-list searches above. Much more on heaps in Week 4.

Trees — the words you must know

Why trees: lists are one-dimensional. Much real data is a hierarchy: family trees, the grammar of a sentence, the taxonomy of organisms. Trees store hierarchies.

Picture an upside-down tree: root at the top, branches going down, leaves at the bottom. A tree is nodes connected by arcs.

• Root — the only node with no parent.
• Leaf — a node with no children.
• Path — for each node there is a unique path from the root to it. The length of the path = the number of arcs in it.
• Level of a node = path length + 1 (the root is level 1).
• Height of the tree = the highest path length (counted in arcs).

A tree can be empty. A tree can be one single node — then that node is both the root and a leaf.

Binary trees & Binary Search Trees

Binary tree: every node has at most 2 children (0, 1, or 2). Think of how If–Else splits into two paths.

Complete binary tree: every non-terminal (internal) node has 2 branches. Useful fact: if every nonterminal node has exactly 2 nonempty children, then

m = k + 1  (leaves m are one more than nonterminal nodes k)

Binary Search Tree (BST), also called an ordered binary tree, adds one rule. For each node holding value v:

• everything in its left subtree is less than v, and
• everything in its right subtree is greater than v.

Like the game "guess my number between 1 and 10" — each guess cuts the field in half.

A Binary Search Tree. Left of 5: all smaller. Right of 5: all bigger.

Implementing a binary tree

Why not an array? Deleting a node leaves empty cells, and inserting can push related nodes far apart. Inconvenient — so we use nodes and pointers.

Dr. Cosh's two-class design: BSTNode (one node: a key + left/right pointers) and BST (owns the root, does the work). BSTNode's members are public so the BST class can reach them.

Searching a BST

How it works: start at the root. Searching for el:

• el equals the node → found, stop.
• el is lower → follow the left pointer.
• el is higher → follow the right pointer.
• You reach NULL → el is not in the tree.

How fast?

• Worst case: O(n) — the tree is shaped like a linked list (every node one child).
• Average case: IPL ÷ n. IPL = Internal Path Length = the sum of the path lengths of all nodes. So the average depends on the tree's shape.
• Best shape: a complete tree. 10,000 nodes: worst shape needs up to 10,000 tests — balanced needs only 14, because the height is lg(10,001) ≈ 13.3 → 14.

Tree traversal — visiting every node once

What: visit each node exactly once. With n nodes there are n! possible orders — only a few are practical. Two families:

1 · Breadth-first — level by level

Top-down, left-to-right (or any of the 4 direction combos). Implemented with a queue: enqueue the root; then repeat: dequeue a node, visit it, enqueue its children.

2 · Depth-first — dive deep, then come back

Built from three moves: V = Visit the node, L = traverse the Left subtree, R = traverse the Right subtree.

(VRL, RVL, RLV also exist — the mirror versions.) In-order on a BST gives the values in sorted order — that's how you turn a BST into a sorted array.

These functions call themselves twice — Dr. Cosh calls this double recursion.

Traversal without recursion

Recursion quietly uses the runtime stack. Alternatives:

Iterative pre-order — bring your own stack

Push right before left, so the left child pops out first. Is it better? No — no double recursion, but it needs its own stack and up to 4 calls per loop. The real worry is space, not time (all traversals are O(n) time).

Threaded trees — hide the stack inside the tree

Add extra pointers (threads) to each node pointing to its predecessor / successor in the traversal. Either keep 4 pointers per node, or overload left/right to sometimes mean predecessor/successor — but then an extra data member must say which meaning is in use.

Morris's algorithm — reshape instead of remembering

Transform the tree while walking so no stack is needed: a tree with no left children is trivial to traverse (just go right). So LVR becomes VR.

Moved nodes keep their left pointers, so the original shape is restored. Time still depends on the loops (about 5–10% saving in tests on 5,000 random trees) — the clear win is space.

Insertion & Deletion

Insertion — find a dead end

Follow the search rule: bigger → right, smaller → left. When you hit an empty child spot, put the new node there. Simple — but over time this can make the tree very unbalanced.

Deletion — three cases, easy to hard

1. A leaf (no children): just delete it. Its parent points to NULL.
2. One child: delete it. The parent adopts the grandchild (points to the deleted node's child).
3. Two children: now it's interesting. Two strategies: merging or copying.

Deletion by Merging

Cutting out the node leaves 2 subtrees. Every value in the left subtree is lower than every value in the right subtree. So:

• The root of the left subtree replaces the deleted node.
• The rightmost node of the left subtree becomes the parent of the right subtree.

The tree may gain height (like here) or lose it — merging can produce a very unbalanced tree. Not inefficient, but not perfect.

Deletion by Copying

Key insight: the rightmost node of the left subtree is the deleted node's immediate predecessor (and the leftmost node of the right subtree is its successor). So:

• Copy the predecessor's (or successor's) value into the deleted node's spot.
• Then delete that node instead — it's always an easy case (0 or 1 child).

Height does not grow, but always using the predecessor makes the left side bushy — so we can alternate between predecessor and successor.

Balancing a tree

Why bother: 10,000 nodes. Linked-list shape → up to 10,000 tests to find something. Balanced → 14 tests. Same data!

Method 1: rebuild from a sorted array

Put all the data in a sorted array (an in-order traversal gives you that). Then: the middle element becomes the root; the middle of the left half becomes one child, the middle of the right half the other; recurse.

Weakness: needs extra space for the array, and all values must be in it first.

Rotation — the tool behind everything else

A child rotates around its parent (right rotation lifts the left child; left rotation lifts the right child). One thing to burn into memory:

🔑 The middle subtree switches parents.

When child Ch rotates up around parent Par, the subtree between them (Ch's inner child) lets go of Ch and becomes Par's child. Nothing else changes.

Method 2: the DSW algorithm (Day, Stout & Warren)

Devised by Day, improved by Stout and Warren. Two phases, built entirely from rotations:

1. Stretch: turn the tree into a backbone — a linked-list-like tree leaning right. (While a node has a left child, rotate that child up around it.)
2. Balance: rotate every other node around its parent, going down the right branch. Repeat until the tree is perfectly balanced.

DSW rebalances the whole tree in O(n). Good when you only balance once in a while (the cost is amortised) — e.g. after many insertions and deletions.

AVL trees — stay balanced as you go

Named after Adel'son-Vel'ski and Landis. Instead of rebalancing the whole tree now and then (DSW), an AVL tree checks balance on every insertion or deletion and fixes problems locally with rotations.

Every node has a balance factor:

Balance = Height(left subtree) − Height(right subtree)

It must stay at +1, 0, or −1. (Height of an empty subtree counts as −1.) If an insert pushes some node's balance to +2 or −2, we rotate. An AVL tree may not look as perfectly even as a DSW result — that's fine, only the balance factors matter.

The 4 out-of-balance situations → 4 rotations

Name the case by where the new key landed, relative to the unbalanced node:

LL — insert 2 (slide example)

RR — insert 8 (slide example)

LR — insert 3 (slide example, double rotation)

RL — insert 7 (slide example, double rotation)

The "further issue" — imbalance higher up

Insert 9 into the tree above: every node on the way stays legal except 5, higher up, which hits −2. Fix it at that node: 9 sits right-right relative to 5 → RR-style rotation (7 rotates up around 5).

Deletion can also unbalance an AVL tree — also fixed by rotations, but it's more time-consuming: every node between the deleted one and the root must be checked (and possibly rotated).

Self-adjusting trees & splay trees

The idea: balancing assumes every node is equally popular. But some nodes are searched much more often. If the popular ones sit near the top, searching gets faster — even in a tree that isn't perfectly balanced.

Simple strategies: single rotation (rotate the accessed node around its parent) or move to root.

Splay trees

A special self-organizing BST: every access reorganizes the tree so recently used elements are easy to reach. Insertion, deletion and search all run in O(log n) amortized time. Every operation ends with splaying — moving the accessed node up. Three cases:

1. Parent is the root: rotate the node around its parent. Done.
2. Homogeneous (node and parent are both left children, or both right children): rotate the parent around the grandparent first, then the node around the parent.
3. Heterogeneous (one left, one right): rotate the node around its parent first, then around the grandparent.

The verdict (exam-worthy): in theory, self-organizing trees compete well. In experiments, AVL almost always wins — and sometimes even plain BSTs do. Lesson: complexity analysis and amortized analysis aren't always the full story.

Heaps & Heapsort

(Max) heap: a binary tree where each node ≥ its children, perfectly balanced, last-level leaves leftmost. A min heap is the reverse — smallest on top.

As a priority queue (from Week 3): enqueue = add at the bottom, climb up. Dequeue = take the root, move the last node up top, let it sink down. Each is one short path — compare that with O(n) list searches.

Heapsort

Selection sort scans the whole remaining data to find the max each round — O(n²). A heap hands you the max for free (the root). So:

1. Turn the data into a heap.
2. Pop the root (the biggest) — move it to its final position.
3. Fix the heap with the remaining nodes. Repeat.

If the data lives in an array, no second array is needed — sort in place by swapping positions.

Expression trees & Polish notation

What is 2 − 3 * 4 + 5? It depends how you group it! Each grouping is a different expression tree (operators inside, numbers at the leaves):

Now traverse the correct (−5) tree in the three depth-first orders:

Notice: the in-order reading is the same for all three trees — that's exactly why infix needs parentheses, and prefix/postfix don't.

Why binary trees stop working

Last week we assumed everything was in RAM. Now suppose the data is too big and lives on a hard disk. Reaching a piece of disk memory costs:

seek time + rotation time + transfer time

Seek time is the killer. It depends on the disk head physically moving to the right position — mechanical, not electronic.

• Seek time is measured in milliseconds.
• CPU work is measured in microseconds — at least 1,000× faster.

A binary tree is the worst possible shape here: each node holds one key, so descending 5 levels can mean 5 separate disk seeks. It was spread across blocks with no thought for how the disk reads.

Multiway trees — fatter nodes, fewer levels

A multiway tree differs from a binary tree in a few key ways:

• Each node has m children.
• Each node has m−1 keys.
• The keys are in ascending order.
• The keys in the first i children are smaller than the i-th key.
• The keys in the last m−i children are larger than the i-th key.

A multiway tree. Count them: a node with k keys always has k+1 pointers.

This one still suffers from malaise — it is unbalanced, so finding 32 takes longer than finding 21. Fat nodes alone are not enough; we also need every leaf on the same level. That is what a B-tree adds.

B-Trees — one node = one disk block

The idea in one line: make each node exactly the size of a disk block, so one seek brings back as many keys as possible.

How many keys fit in a node depends on the size of each key and the size of the block, and block size depends on the system.

A B-Tree of order m has these properties:

• The root has at least 2 subtrees, unless it is a leaf.
• Each nonroot, nonleaf node holds k−1 keys and k pointers, where ⌈m/2⌉ ≤ k ≤ m.
• Each leaf holds k−1 keys, where ⌈m/2⌉ ≤ k ≤ m.
• All leaves are on the same level.

Nice consequence: the root — and maybe the whole first level — can be kept in RAM, so a search of a big tree may cost only one or two real disk accesses.

Implementing and searching

The node carries its keys and pointers inline, plus a count of how many keys are actually in use:

Searching is just a binary-tree search with a wider fan-out. Start at the root and pick the branch whose range contains the search value:

Within a node you scan the keys in RAM, which is free. Following a pointer is what costs a seek — so the wider the node, the cheaper the search.

Inserting — the tree grows upward

The challenge: in a B-tree all leaves must be on the same level. Not even a balanced binary tree demands that.

So the direction of construction flips. Binary trees are built top down — the root is placed and nodes divide around it. A B-tree is built bottom up — leaves are positioned and rearranged, and the root is decided last.

The algorithm:

• Search the tree to find the leaf the key belongs in.
• If there is room (fewer than m−1 keys already), just insert it. Done.
• Otherwise the node must split. Choose the median: lower keys form the left node, higher keys form the right node.
• The median moves up to the parent — which may itself now be full, so it may split too.
• Repeat upward until something has room, or the root is reached.

Worked example — insert 33, order 5

Order 5 means at most 4 keys per node. Watch the highlighted node.

1 — the target leaf already holds 4 keys. It is full.

2 — inserting 33 gives it 5 keys. Overflow.

3 — split at the median 32. Left keeps 25 30, right takes 33 35, and 32 moves up into the parent. The parent had room, so it stops here.

When the root itself is full

This is the only case where a B-tree gains height.

A full root receives a promoted median and overflows.

It splits in two and a new root is created above them. The tree is one level taller — and every leaf is still on the same level.

Deleting

Deletion asks two questions first:

• Is the key in a leaf? If so, will the leaf still be at least half full afterwards?
• Is it in an internal node? Then which value becomes the new separator?

Leaf nodes can simply be deleted, which may leave the leaf with too few keys. Then the tree must be rebalanced: pick a sibling leaf and redistribute the keys. If a neighbour has enough to share, the median becomes the new separator key and the rest are shared out. If that leaves the parent short of keys, the fix iterates upward toward the root.

Internal nodes cannot just be removed — they separate two subtrees. Promote one of:

• the largest value in the left subtree, or
• the smallest value in the right subtree.

Either choice reduces the problem to deleting from a leaf or from another internal node — both of which we have now defined. Same trick as deleting from a BST.

B*-Trees — delay the split

Every node is a block, and every block costs a seek. B*-Trees reduce accesses further by keeping nodes fuller:

• A B-tree must be at least half full.
• A B*-Tree must be two-thirds full.

How it achieves that: it delays splitting by splitting 2 nodes into 3, rather than 1 node into 2.

• Overflow first. If a leaf fills up but its sibling has room, the surplus overflows into the sibling instead of splitting.
• Split only when both are full. Then the two full nodes become three, each about two-thirds full.

A B**-Tree pushes the same idea again: required to be 75% full.

B+Trees — all data in the leaves

The problem being solved: in-order traversal. On a binary tree, in-order gives you the values in ascending order cheaply. On a B-tree it is awkward — leaves can be read a block at a time, but internal nodes give you only one value per visit, and you keep bouncing between levels.

The fix: in a B+Tree the internal nodes are pure index — signposts only.

• Values stored in index nodes are repeated in the leaves.
• All data lives in the leaves; indexes only point to the right leaf.
• Leaves are chained with forward pointers, so an in-order traversal reads leaves straight through and never touches an internal node.

A B+Tree. The index keys 20 and 30 reappear in the leaves — that is the giveaway.

Insert: when a leaf splits, the promoted value becomes both a value in the leaf and an index in the parent.
Delete: removing a value from a leaf does not require removing the matching index — it is still a perfectly good signpost. If a leaf gets too small it merges with a sibling and the indexes are updated.

Prefix B+Trees and Bit Trees — shrink the index

That last point is the doorway. If an index key does not have to be a stored value, it only has to separate them. So store the shortest thing that still separates.

Prefix B+Tree: the index holds only a prefix of the key — BF instead of BF90, like the guide word at the top of a dictionary page.

• Shorter prefix → more keys per index node.
• More keys → more children per node.
• More children → fewer levels → fewer seeks.

If every key in a region starts AB12XY…, storing "AB" at every level between the leaves and the root is pure waste. Keep only the distinguishing part.

Bit Tree: take it to the extreme. Store the D-bit — the single distinction bit, the first bit position where two values differ:

Especially valuable when the tree stores complicated objects: you never store the object in the index, only enough to steer the search to the right leaf.

Tries

Only a portion of the key is ever needed to search. But finding the right prefix is awkward, and maintaining prefixes is complicated.

A tree that navigates using parts of the key itself is called a "trie."

The name comes from retrieval. Instead of comparing whole keys at each node, you consume the key one piece at a time — one character, or one bit — and that piece chooses the branch. The path from the root spells the key.

Exam traps

• Keys vs pointers. A node with k keys has k+1 pointers. Order m means m pointers and m−1 keys — not m keys.
• "Order 5" is the pointer count. So a node holds at most 4 keys and splits on the 5th.
• Half full, not half empty. B-tree ≥ ½ · B*-Tree ≥ ⅔ · B**-Tree ≥ ¾.
• Splitting promotes the median, and the median goes up, not into either half.
• Height only grows at the root. Every other split is absorbed by a parent.
• B+ ≠ B. In a B+Tree every value is in a leaf and index values are repeated. In a plain B-tree a value appears exactly once, wherever it sits.
• Why any of this exists: seek time. If a question asks "why not just use an AVL tree", the answer is milliseconds vs microseconds.

What the worksheet asks (plain words)

Part 1: Start with an empty tree. Do these operations, in order, then draw the tree:

Insert 10, 5, 29, 4, 8, 28, 3, 6, 15 — then — Delete 3, Delete 28

Part 2: From that result, Delete 10 and draw the tree again.

The plan before drawing

• Insert rule: start at the root. Smaller → go left, bigger → go right. Insert at the first empty spot.
• Delete a leaf: just remove it.
• Delete a node with 1 child: the parent adopts the child.
• Delete a node with 2 children: deletion by copying — copy the successor (the leftmost node of the right subtree) into its place, then remove that node. (The method used in our class. Alternatives shown at the bottom.)

Step by step — the nine insertions

The two deletions → Answer to Part 1

Part 2 — Delete 10 (two children!)

10 has two children (5 and 29) → deletion by copying:

1. Find the successor = leftmost node of the right subtree. Go right to 29, then left as far as possible → 15.
2. Copy 15 into 10's place.
3. Delete the old 15 node — it's a leaf, easy. (29 now has no left child.)

Alternative methods (only if asked for them)

Full solution code

This program builds the worksheet tree, does the deletions, and prints the tree in-order after each part (in-order = sorted, an easy way to check yourself).

Practice — fill in the missing lines

Same code, but the exam-critical lines are gone. Type them, then hit Check.

What the worksheet asks (plain words)

You are given an AVL tree. Part 1: insert 18, keep it balanced, redraw. Part 2: then insert 15, then 14 (continuing from Part 1's result), redraw.

The given tree — balance factors shown beside each node (all legal: −1, 0, +1)

The plan before drawing

1. Insert like a normal BST (smaller left, bigger right).
2. Recompute balance factors up the path: Balance = Height(left) − Height(right).
3. If a node hits +2 or −2: find the lowest such node, name the case by where the new key landed relative to it (LL / RR / LR / RL), and rotate. Remember: the middle subtree switches parents.

Part 1 — Insert 18

Path: 18 > 10 → right · 18 > 13 → right · 18 > 17 → right → new right child of 17.

Which case? Relative to 13, the new key went into the Right subtree of the Right child (into 17's right side) → RR → one left rotation: 17 rotates up around 13.

Part 2 — Insert 15, then Insert 14

Insert 15 — no rotation needed

Path: 15 > 10 → right · 15 < 17 → left · 15 > 13 → right → new right child of 13. Check the factors — everyone stays legal:

Insert 14 — RL case!

Path: 14 > 10 → right · 14 < 17 → left · 14 > 13 → right · 14 < 15 → left → new left child of 15.

Which case? Relative to 13: the key went to the Right child (15), then into its Left subtree → RL → double rotation: first rotate 14 right around 15, then rotate 14 left around 13. 14 ends up as the parent of both.

Solution code — rotations you can run

The exam wants drawings, but these little functions ARE the drawings, in code. Note the "middle subtree" line in each rotation.

Practice — fill in the missing lines

Short forms ↔ long forms

The growth ladder & key formulas

Slowest-growing (best) → fastest-growing (worst)

Formulas to write without thinking

• Array address: address(a[i]) = base + elementSize · i — e.g. base 1000, 4-byte ints: a[i] at 1000 + 4i.
• Complete binary tree: m = k + 1 (leaves = nonterminal nodes + 1).
• Path length = arcs from root · Level = path length + 1 · Height = longest path length. Empty subtree height = −1.
• Balance = Height(left) − Height(right) ∈ {−1, 0, +1}; at ±2 → rotate at the lowest bad node.
• Average BST search = IPL ÷ n. Balanced tree of 10,000 nodes: height = lg(10,001) ≈ 13.3 → 14 tests.
• Sparse table (CMU): 25,000 × 1,000 = 25 MB table, only 0.7% used → 99.3% empty; two arrays < 5%; linked lists even less.

Arrays & linked lists — every operation, every cost

Array

Singly linked list

Doubly linked list

Stacks, queues & priority queues — every function

Stack (LIFO)

Queue (FIFO)

Priority queue — 4 ways to build it

Trees — every operation, every cost

🔑 One line to rule all rotations: the middle subtree switches parents.