AVL insertion & deletion
Insert 10, 5, 7 to trigger a left-right double rotation, then insert 3 and delete 10 to trigger a deletion rebalance.
1. Insert 10 into the empty tree. One node, balance factor 0.
Data Structures & Algorithms
DSA III: self-balancing trees and divide-and-conquer algorithms.
Self-balancing trees keep search logarithmic no matter the insertion order, and divide-and-conquer breaks sorting into smaller subproblems that combine efficiently. These notes turn my Georgia Tech DSA III material into demos you can step through.
A Module 0 refresher on Java generics, Big-O, and the balance invariant that ties the course together.
AVL trees: balance factors and the four rotations that restore O(log n) height.
(2,4) trees: multi-way nodes that grow by splitting and shrink by fusing.
Iterative sorts: bubble, insertion, selection, and cocktail shaker, compared by stability and adaptivity.
Divide-and-conquer sorts: merge, quicksort, LSD radix, and quickselect, plus the comparison lower bound.
#
learning map
-
Module 8 · AVL
AVL Trees
A self-balancing BST that stores each node's balance factor and rotates when its magnitude passes one, so the tree height stays logarithmic no matter the insertion order.
-
Module 9 · (2,4)
(2,4) Trees
A multi-way search tree whose nodes hold one to three keys and two to four children. It grows by splitting overflowing nodes and shrinks by borrowing or merging, keeping every leaf at the same depth.
-
Module 10 · Iterative sorts
Iterative Sorts
Bubble, insertion, selection, and cocktail-shaker sorts: quadratic comparison sorts separated by stability, adaptivity, in-place behavior, and how many comparisons versus swaps they make.
-
Module 11 · Divide & conquer
Divide & Conquer Sorts
Merge sort, randomized in-place quicksort with Hoare partition, non-comparison LSD radix sort, and quickselect for order statistics, all framed by the Ω(n log n) comparison lower bound.
#
visual lab
1/8
(2,4) tree: split & fusion
Insert 40 into a full node to force a split, then remove keys to watch a transfer and a fusion.
1. Start with a full root [10, 20, 30]. A (2,4) node holds up to three keys.
Bubble sort, pass by pass
Bubble sort compares adjacent pairs and swaps out-of-order ones; the last-swap check stops once a pass makes no swaps.
1. Bubble sort compares adjacent pairs and swaps them when out of order. Start: [5, 1, 4, 2, 8].
Merge sort: divide & conquer
Split the array down to single elements, then merge the sorted pieces back together.
1. Merge sort splits the array in half, sorts each half, then merges. Start: [5, 1, 4, 2].
#
concept notes
The balance factor
Every AVL node stores height(left) − height(right). Keeping that in {−1, 0, 1} forces Θ(log n) height, so search, insert, and delete stay O(log n) regardless of insertion order.
Module 8 · AVL
One rotation on insert, many on delete
A single insertion unbalances at most one ancestor, fixed by one rotation. A deletion can shorten a subtree and cascade, so you may rotate at several nodes on the way back to the root.
Module 8 · AVL
Grow by splitting, shrink by fusing
A (2,4) tree never rotates. An overflowing node splits and promotes its middle key; an underflowing node borrows from a sibling (transfer) or merges (fusion). Height changes only at the root.
Module 9 · (2,4) Trees
Stability and adaptivity
Sorts differ by more than Big-O. Stability preserves the order of equal keys; adaptivity means near-sorted input runs faster. Insertion sort has both; selection sort has neither but minimizes swaps.
Module 10 · Iterative Sorts
The comparison lower bound
Any sort that only compares keys needs Ω(n log n) comparisons in the worst case, because its decision tree needs n! leaves. Merge and quicksort meet the bound; radix sort sidesteps it by not comparing.
Module 11 · Divide & Conquer
Partition, then recurse
Divide-and-conquer splits a problem, solves the parts, and combines. Merge sort splits evenly and merges; quicksort partitions around a pivot; quickselect recurses into just one partition for a linear-expected-time order statistic.
Module 11 · Divide & Conquer
#
test yourself
Module 8 · AVL
AVL Trees
What is the AVL balance factor, and when does a rotation trigger?
Balance factor = height(left) − height(right). A node is fine at −1, 0, or 1; once the magnitude reaches 2 after an insert or delete, a rotation is required.
How many rotations can an insertion versus a deletion need?
An insertion needs at most one rotation at the lowest imbalanced node. A deletion can cascade up to O(log n) rotations, because each rebalance can shorten a subtree and unbalance an ancestor.
How do you tell the four rotation cases apart?
Left-heavy (BF +2): left child leaning left is LL (single right rotation), leaning right is LR (double). Right-heavy (BF −2): right child leaning right is RR (single left rotation), leaning left is RL (double).
What is height(null) by convention, and why does it matter?
height(null) = −1, so a leaf has height 0 and height(node) = 1 + max(child heights). It keeps balance-factor arithmetic consistent.
After a rotation, what do you recompute first?
Heights and balance factors of the rotated nodes, bottom-up: the demoted node first, then the promoted new subtree root, whose height depends on it.
Module 9 · (2,4)
(2,4) Trees
How does a (2,4) tree stay balanced without rotations?
Every leaf sits at the same depth. Overflow splits a 4-node and promotes its middle key upward, so height only ever grows at the root.
Transfer versus fusion on deletion: what is the difference?
When a node underflows, transfer borrows a key from an adjacent sibling through the parent if that sibling can spare one; otherwise fusion merges the node, a parent key, and the sibling into one.
Why is a (2,4) tree equivalent to a red-black tree?
Each (2,4) node maps to a small red-black cluster, and split/fuse correspond to red-black recolorings and rotations, so both give the same O(log n) guarantees.
Module 10 · Iterative sorts
Iterative Sorts
Which iterative sorts are stable?
Bubble, insertion, and cocktail shaker are stable. Selection sort is not, because a long-distance swap can reorder equal keys.
Which iterative sort is adaptive, and what does that mean?
Insertion sort is adaptive: nearly-sorted input approaches O(n) because few shifts are needed. Selection sort always scans the full unsorted region.
Why would you pick selection sort despite its O(n²) time?
It makes at most O(n) swaps, the fewest of the quadratic sorts, which matters when a write is far more expensive than a comparison.
Module 11 · Divide & conquer
Divide & Conquer Sorts
Why is O(n log n) a lower bound for comparison sorts?
A comparison sort is a decision tree with n! leaves, and a binary tree with n! leaves has height at least log₂(n!) = Ω(n log n).
Merge sort versus quicksort: stability and space?
Merge sort is stable and out-of-place (O(n) extra). Quicksort is in-place (O(log n) stack) but unstable; a randomized pivot gives expected O(n log n).
How does LSD radix sort beat the comparison lower bound?
It never compares keys. It distributes by digit into buckets, least-significant digit first, in O(k·n) for k digits, so Ω(n log n) does not apply.
What does quickselect do, and how fast is it?
It finds the kth smallest element in O(n) expected time by partitioning like quicksort but recursing into only the side that holds k.