What to hand in

algo with alpha, tree and shape, passing go test ./..., plus a report.

1. Three structures, one library

n = 1,000 / 10,000 / 100,000, looking up every title:

n	linear (L1)	hash (L10)	tree, shuffled	tree, -sorted

Comparisons per lookup.

Leave one cell empty — the tree with -sorted at n = 100,000. Instead of a number, write how many comparisons it would take and how long that would run, extrapolated from your n = 10,000 measurement. Explain why you did not run it.

2. When the tree pays for itself

The tree loses on every lookup and wins on every ordered query.

Say a program performs S exact-key lookups and R range queries. Measure what one range query costs a hash table (it has to sort everything or scan everything) and what it costs the tree.

Find the R : S ratio at which the tree starts paying for itself. State your assumptions.

3. Height as a diagnostic

In step 7 the degenerate tree was correct — no error appeared anywhere.

Write func (t *TreeIndex) Balance() float64, returning Height() divided by log2(Len()).

What value would you consider normal? Suspicious? A failure? Justify it with the numbers from steps 5 and 7, not with intuition.

Then answer: where should this be checked in a running program — in a test, on every insertion, or never?

4. The worst case you were not shown

Step 7 showed -sorted and -reverse. Both give height n.

Invent a third insertion order that also gives height n but is neither ascending nor descending. (Hint: a tree degenerates when every new key lands on an edge — but the edge is allowed to change sides.)

Generate it, run it through Height(), and show the result.

5. Exactly what lesson 12 has to fix

One paragraph, in your own words, without using the phrase "balanced tree":

• what precisely breaks when a tree degenerates;
• why none of step 8's four attempts fixes it;
• and what promise a structure would have to make for the problem to be gone.

Your paragraph should be lesson 12's requirements list. When you start it, check whether you were right.