Insert n distinct keys in random order (all n! orders equally likely) into an ordinary, unbalanced binary search tree. How good is the resulting tree? We measure it by its internal path length \(C(T)\): the total cost of searching every key once, where the cost of a search is the number of nodes on its search path. The first tab shows how to count \(C(T)\) — and why counting it the other way round gives the recurrence for its expectation \(C_n\). The second tab samples many random trees and shows the whole distribution.
compareTo line is one node on the search path — and one tick on that node's tally.S E A R C H E X A M P L E
as in algs4's tinyST.txt, or 77 12 85 11 57. If all keys are numbers they are
compared as numbers, otherwise as strings. A repeated key is a put of an existing key: it
overwrites the value and leaves the shape unchanged. Lines starting with # are ignored.
At most 40 distinct keys.
n 7, seed 42, samples 30 (random trees to draw
right away), measure C (or h, leaves, leftmost),
show auto (or trees, frequencies), scale normalized (or raw), range full (or typical), y log (or linear).
Normalized means \(C(T)/(n\lg n)\), \(h(T)/\lg n\), leaves\(/n\) and leftmost depth\(/\lg n\).
Any other line is a permutation of 1 … n, inserted as a sample of its own — so a lecture
example can be fixed exactly (try listing all 24 permutations of 4). Lines starting with #
are ignored. The same seed always produces the same sequence of trees.