Start learning →

Advanced structures

Four structures for harder problems: tries for words, union-find for groups, segment trees for ranges, and AVL trees that keep themselves balanced.

About 9 hours of study

Learning objectives

Lessons

  1. 1

    Tries: prefix trees Intermediate

    Store words letter by letter in a tree, so finding a word, or every word that starts with a prefix, costs only the length of the word.

  2. 2

    Disjoint sets (union-find) Intermediate

    Keep track of which items are in the same group, merging groups in almost constant time with union by size and path compression.

  3. 3

    Segment trees and Fenwick trees Advanced

    Answer range-sum questions and change single values in O(log n) each, where a plain array or prefix sums make one of the two slow.

  4. 4

    AVL trees: self-balancing search trees Advanced

    Keep a binary search tree's height close to log n by checking every node's balance after an insert and repairing it with rotations.

Module practice

Module quiz

1. What does the end flag of a trie node mean?
2. In union-find, what does find(x) return?
3. A trie stores 10,000 words. About how many steps does a search for a 6-letter word take?
4. A segment tree holds an array of 16 numbers. How many nodes does changing one number update?
5. Keys 30, 20 and 10 are inserted into an empty AVL tree, in that order. Which key is at the root afterwards?
6. Why does union by size keep the trees shallow?
7. An AVL node has balance factor +2, and the new key went to the right of its left child. What repairs it?
8. Why does a Fenwick tree use positions that start at 1?

‹ Choosing structures and finding bugsFinal assessment ›