Discrete Math › Section C · Graph theory › Topic C.11

Trees in computing

Open a file, run a database query, type into a search box or play a chess program, and a tree is doing the work. This topic tours the trees inside everyday software and shows how the shape of a tree decides how fast it is, and even how fast any method can be.

Why software loves trees

The topic on trees showed that a binary tree of height \(h\) holds at most \(2^{h+1} - 1\) vertices, so \(n\) items can sit in a tree only about \(\log_2 n\) levels deep. Any operation that walks from the root to one vertex then costs only about \(\log_2 n\) steps: around 20 for a million items, around 30 for a billion. Here we see how computers keep trees short, and meet trees shaped for particular jobs.

Keeping search trees balanced

A binary search tree is fast only if it stays short. Insert the keys 1, 2, 3, 4, 5, 6, 7 in that order and each new key becomes the right child of the previous one: the tree is a single chain of height 6, and searching it is no better than scanning a list. Insert the same keys in the order 4, 2, 6, 1, 3, 5, 7 instead and you get a perfectly balanced tree of height 2. Self-balancing designs such as AVL and red-black trees rearrange vertices after each change so that the height stays proportional to \(\log n\), whatever order the data arrive in.

Heaps

A binary min-heap is a binary tree with two rules. Its shape is complete: every level is full except possibly the last, which is filled from the left. And it is heap-ordered: every parent is no larger than its children, so the smallest item is at the root. A complete tree fits neatly in an array with no gaps: store it level by level from index 0, and the children of index \(i\) sit at \(2i + 1\) and \(2i + 2\), with the parent of index \(i\) at \(\lfloor (i-1)/2 \rfloor\).

Worked example: inserting and removing

Start with the min-heap stored as [2, 5, 3, 9, 6, 8]. 1. Insert 1: place it at the next free position, index 6, whose parent is index 2, holding 3. 2. Since 1 is smaller, swap: [2, 5, 1, 9, 6, 8, 3]. 3. Now its parent is index 0, holding 2; swap again: [1, 5, 2, 9, 6, 8, 3]. 4. Remove the minimum: take out the root, 1, and move the last item, 3, to the root: [3, 5, 2, 9, 6, 8]. 5. Sift down: 3's children are 5 and 2; swap with the smaller, 2, giving [2, 5, 3, 9, 6, 8]. 3's only child is now 8, which is larger, so stop. Each operation climbs or descends at most the height.

Priority queues and heapsort

A priority queue repeatedly hands out the most urgent item, the smallest key in a min-heap. With a heap, inserting and removing the minimum each take \(O(\log n)\) time. Operating systems use them to schedule tasks, and Dijkstra's and Prim's algorithms use them to find the next vertex quickly. Heapsort builds a heap, then removes the root repeatedly to output the items in order. It takes \(O(n \log n)\) time even in the worst case and needs almost no extra memory.

Tries and expression trees

A trie stores words letter by letter along paths from the root, so words with a common start share a branch. The words car, cart, cat and dog need only 8 vertices below the root: c, ca, car, cart, cat, d, do and dog. Looking up a word takes time proportional to its length, and every word starting with "ca" sits in the subtree below the vertex ca, which suits autocomplete. An expression tree stores a formula: \((3 + 4) \times 5\) has \(\times\) at the root, with a subtree for \(3 + 4\) on the left and 5 on the right. Its postorder traversal, 3 4 + 5 \(\times\), is the order in which a stack-based calculator evaluates it.

Worked example: Huffman coding

Huffman coding builds a compression tree from symbol frequencies. A 12-letter message uses A 6 times, B 3, C 2 and D 1. 1. Repeatedly merge the two least frequent items into one vertex weighted by their sum: D and C make 3; that 3 and B make 6; that 6 and A make 12, the root. 2. Label each pair of branches 0 and 1; a symbol's code is its path from the root, for example A = 0, B = 10, C = 110, D = 111. 3. No code is the start of another, so the bits decode without separators. 4. Total: \(6 \cdot 1 + 3 \cdot 2 + 2 \cdot 3 + 1 \cdot 3 = 21\) bits, against 24 for a fixed 2-bit code.

Worked example: no sort beats about n log n

Any sorting method that works by comparing pairs of items can be drawn as a binary decision tree: each vertex is a comparison, its two branches are the outcomes, and each leaf is a final ordering. 1. Every one of the \(n!\) possible orderings must reach its own leaf, so the tree has at least \(n!\) leaves. 2. A binary tree of height \(h\) has at most \(2^h\) leaves, so \(2^h \ge n!\), giving \(h \ge \log_2(n!)\). 3. For 3 items: \(3! = 6\) and \(\log_2 6 \approx 2.58\), so some input needs 3 comparisons. 4. For 10 items: \(\log_2(10!) \approx 21.8\), so at least 22. 5. In general \(\log_2(n!)\) is roughly \(n \log_2 n\), so no comparison sort can be faster than that in the worst case.

B-trees in databases

Reading from a disk is slow compared with memory, so databases want trees with very few levels. A B-tree is a search tree whose vertices are wide: each holds many sorted keys and has many children, sized to fill one block of storage. All its leaves sit at the same depth. With up to 1,000 children per vertex, three levels already reach a million leaf blocks, enough for about a billion keys, so one lookup reads only about three blocks. Database indexes and file systems use B-trees.

Worked example: a game tree

In a game tree, each vertex is a position and its children are the positions one move later. Minimax scores the leaves, then works upwards: on your turn take the maximum of the children's scores, on your opponent's turn take the minimum. Suppose you have moves A and B. After A, your opponent's replies lead to scores 3 and 5; after B, to 2 and 9. 1. The opponent minimises: A is worth 3 and B is worth 2. 2. You maximise: choose A, worth 3. 3. Pruning: once B's first reply shows 2, below the 3 already guaranteed by A, B cannot be better, so the 9 need not be examined. This shortcut is alpha-beta pruning.

Common mistakes to avoid

First, assuming every binary search tree is balanced; sorted input turns a plain one into a chain with \(O(n)\) searches. Second, confusing a heap with a search tree: a heap does not keep left children smaller than right ones, so it cannot find an arbitrary key quickly. Third, reading the \(n \log_2 n\) lower bound as a limit on all sorting; it covers comparison sorts only, and digit-based methods can beat it. Fourth, forgetting that heap array positions start at 0 in the \(2i + 1\) rule.

Key takeaways

Short trees make fast software, because operations follow one root-to-leaf path. Balanced search trees keep height near \(\log n\), while sorted input can ruin an unbalanced one. Heaps keep the minimum at the root, fit in an array, and give \(O(\log n)\) priority-queue operations and \(O(n \log n)\) heapsort. Tries share prefixes, expression trees evaluate in postorder, Huffman trees give common symbols short codes, and B-trees keep huge indexes a few levels deep. Decision trees prove that comparison sorting needs about \(n \log_2 n\) comparisons, and game trees are searched with minimax and pruning.

Flashcards

Flashcard

About log₂ n

The least height of a binary tree holding n items

About 20 levels for a million.

Test your understanding

Question 1 of 5

A heap is stored in an array starting at index 0. At which indices are the children of the item at index 4?

Question 2 of 5

The value 1 is inserted into the min-heap [2, 5, 3, 9, 6, 8]. What is the array afterwards?

Question 3 of 5

What is the smallest number of comparisons that any comparison-based sort must use, in the worst case, to sort 4 items?

Question 4 of 5

You choose among moves A, B and C; your opponent then replies. The final scores are: after A, 4 or 7; after B, 6 or 8; after C, 1 or 9. Your opponent minimises and you maximise. What is your move worth?

Question 5 of 5

The keys 10, 20, 30, 40, 50 are inserted, in that order, into an empty plain binary search tree. What is its height?

← Previous topicNext topic →