Binary Trees & BST — Programuoki

Code

The harness and the tests

Three files in one step: the harness, the tests, and three new commands in main.go.

command	what it does
`algo alpha`	step 1's answer: the walk, `Min`/`Max`, a range
`algo tree`	the tree against lesson 10's hash index and lesson 1's linear scan
`algo shape`	the same library, two insertion orders

The tests (bst_test.go) check six things:

test	what it requires
`TestTreeStoresAndFinds`	finds everything stored, misses what was not
`TestTreeDuplicateKeysReplace`	an equal key replaces (as in lesson 10)
`TestKeysComeBackSorted`	`Keys()` IS sorted; `Min`/`Max` match the ends
`TestRangeReturnsOnlyTheBand`	a range returns only its band and visits fewer than all nodes
`TestShuffledInsertStaysLogarithmic`	random insertion keeps the depth logarithmic
`TestSortedInsertDegeneratesIntoAList`	sorted insertion gives `Height() == n`

The third one should look familiar. In lesson 10 the test demanded that Keys() was not sorted, because a hash index cannot promise order. Here it demands that it is. The same test with the sign reversed: two promises, two structures.

The last one is another defect-pinning test, like lesson 7's selection sort, lesson 8's quicksort and lesson 9's unstable pass. It requires sorted insertion to produce a tree of height exactly n.

If it ever starts failing, you have built something other than a plain BST. In lesson 12 you will do precisely that, on purpose; until then it protects step 7's demonstration.

treebench.go CREATE

Create this file in ./

package main

import (
	"flag"
	"fmt"
	"math"
	"time"

	"algo/metrics"
)

// cmdAlpha is lesson 10's closing question, answered.
//
// The hash index could not produce the library in order at any price. The tree
// produces it by being walked.
func cmdAlpha(args []string) error {
	fs := flag.NewFlagSet("alpha", flag.ContinueOnError)
	in := fs.String("in", "library.jsonl", "library file")
	n := fs.Int("n", 6, "how many titles to show")
	from := fs.String("from", "", "range query: lower bound")
	to := fs.String("to", "", "range query: upper bound")
	if err := fs.Parse(args); err != nil {
		return err
	}
	items, err := load(*in)
	if err != nil {
		return err
	}

	tree := NewTreeIndex()
	var build metrics.Counter
	for _, it := range items {
		tree.Put(it, &build)
	}

	t0 := time.Now()
	keys := tree.Keys()
	walk := time.Since(t0)

	fmt.Printf("the first %d titles, walked out of the tree:\n", *n)
	for i := 0; i < *n && i < len(keys); i++ {
		fmt.Printf("  %s\n", keys[i])
	}
	fmt.Printf("\n%d keys in order, 0 comparisons, %s\n", len(keys), walk.Round(time.Microsecond))

	lo, _ := tree.Min()
	hi, _ := tree.Max()
	fmt.Printf("min %q, max %q\n", lo, hi)

	if *from != "" || *to != "" {
		var rc metrics.Counter
		hits := tree.Range(*from, *to, &rc)
		fmt.Printf("\nrange [%s .. %s]: %d titles, %d nodes visited out of %d\n",
			*from, *to, len(hits), rc.N(), tree.Len())
		for i := 0; i < 4 && i < len(hits); i++ {
			fmt.Printf("  %s\n", hits[i])
		}
		if len(hits) > 4 {
			fmt.Printf("  ... and %d more\n", len(hits)-4)
		}
	}
	return nil
}

// cmdTree measures the tree against the hash index of lesson 10 and against
// the linear scan of lesson 1 — same library, same questions.
func cmdTree(args []string) error {
	fs := flag.NewFlagSet("tree", flag.ContinueOnError)
	in := fs.String("in", "library.jsonl", "library file")
	if err := fs.Parse(args); err != nil {
		return err
	}
	items, err := load(*in)
	if err != nil {
		return err
	}

	tree := NewTreeIndex()
	var tb metrics.Counter
	t0 := time.Now()
	for _, it := range items {
		tree.Put(it, &tb)
	}
	treeBuild := time.Since(t0)

	idx := NewHashIndex(16)
	var hb metrics.Counter
	t0 = time.Now()
	for _, it := range items {
		idx.Put(it, &hb)
	}
	hashBuild := time.Since(t0)

	var tl, hl, ll metrics.Counter
	t0 = time.Now()
	for _, it := range items {
		tree.Get(it.Title, &tl)
	}
	treeLook := time.Since(t0)
	t0 = time.Now()
	for _, it := range items {
		idx.Get(it.Title, &hl)
	}
	hashLook := time.Since(t0)
	t0 = time.Now()
	for _, it := range items {
		LinearFind(items, it.Title, &ll)
	}
	linLook := time.Since(t0)

	n := float64(tree.Len())
	fmt.Printf("n = %d distinct titles\n\n", tree.Len())
	fmt.Printf("  tree height      %d   (log2 n = %.1f)\n", tree.Height(), math.Log2(n))
	fmt.Printf("  in order?        %v\n\n", isSortedStrings(tree.Keys()))

	fmt.Printf("  %-16s %14s %14s %12s\n", "", "cmps/lookup", "build cmps", "lookup time")
	fmt.Printf("  %-16s %14.3f %14d %12s\n", "tree", float64(tl.N())/n, tb.N(), treeLook.Round(time.Microsecond))
	fmt.Printf("  %-16s %14.3f %14d %12s\n", "hash (lesson 10)", float64(hl.N())/n, hb.N(), hashLook.Round(time.Microsecond))
	fmt.Printf("  %-16s %14.1f %14d %12s\n", "linear (lesson 1)", float64(ll.N())/n, 0, linLook.Round(time.Millisecond))
	fmt.Printf("\n  build time: tree %s, hash %s\n", treeBuild.Round(time.Microsecond), hashBuild.Round(time.Microsecond))

	// What each one can hand back in order, and what that costs.
	fmt.Printf("\n  keys in sorted order: tree yes (walk), hash no (must sort all %d)\n", tree.Len())
	return nil
}

func isSortedStrings(s []string) bool {
	for i := 1; i < len(s); i++ {
		if s[i-1] > s[i] {
			return false
		}
	}
	return true
}

// cmdShape is the degeneration: the same library, inserted in two orders.
func cmdShape(args []string) error {
	fs := flag.NewFlagSet("shape", flag.ContinueOnError)
	shuf := fs.String("shuffled", "library.jsonl", "library in random order")
	sorted := fs.String("sorted", "sorted.jsonl", "the same library, pre-sorted")
	if err := fs.Parse(args); err != nil {
		return err
	}
	a, err := load(*shuf)
	if err != nil {
		return err
	}
	b, err := load(*sorted)
	if err != nil {
		return err
	}

	fmt.Printf("%-12s %8s %8s %10s %14s %12s\n",
		"insert order", "n", "height", "log2 n", "cmps/lookup", "lookup time")
	for _, tc := range []struct {
		name  string
		items []Item
	}{{"shuffled", a}, {"-sorted", b}} {
		tree := NewTreeIndex()
		var c metrics.Counter
		for _, it := range tc.items {
			tree.Put(it, &c)
		}
		var l metrics.Counter
		t0 := time.Now()
		for _, it := range tc.items {
			tree.Get(it.Title, &l)
		}
		el := time.Since(t0)
		n := float64(tree.Len())
		fmt.Printf("%-12s %8d %8d %10.1f %14.1f %12s\n",
			tc.name, tree.Len(), tree.Height(), math.Log2(n), float64(l.N())/n, el.Round(time.Microsecond))
	}
	// Lesson 1's linear scan over the same library, for scale. The degenerate
	// tree should be compared against the thing it was supposed to replace.
	var ll metrics.Counter
	t0 := time.Now()
	for _, it := range a {
		LinearFind(a, it.Title, &ll)
	}
	el := time.Since(t0)
	fmt.Printf("%-12s %8d %8s %10s %14.1f %12s\n",
		"linear (L1)", len(a), "-", "-", float64(ll.N())/float64(len(a)), el.Round(time.Microsecond))

	fmt.Println("\nboth trees hold the same keys and both answer correctly.")
	return nil
}

bst_test.go CREATE

Create this file in ./

package main

import (
	"fmt"
	"math"
	"sort"
	"testing"

	"algo/metrics"
)

func TestTreeStoresAndFinds(t *testing.T) {
	items := shuffledLib(1000)
	tree := NewTreeIndex()
	var c metrics.Counter
	for _, it := range items {
		tree.Put(it, &c)
	}
	if tree.Len() != 1000 {
		t.Fatalf("stored %d, want 1000", tree.Len())
	}
	for _, it := range items {
		got, ok := tree.Get(it.Title, &c)
		if !ok || got.ID != it.ID {
			t.Fatalf("Get(%q): ok=%v id=%d, want id=%d", it.Title, ok, got.ID, it.ID)
		}
	}
	if _, ok := tree.Get("nėra tokio pavadinimo", &c); ok {
		t.Error("found a title that was never stored")
	}
}

// An equal key replaces, exactly as in lesson 10's hash index. The two
// structures make the same promise about keys; they differ in what else they
// promise.
func TestTreeDuplicateKeysReplace(t *testing.T) {
	tree := NewTreeIndex()
	var c metrics.Counter
	tree.Put(Item{ID: 1, Title: "same"}, &c)
	tree.Put(Item{ID: 2, Title: "same"}, &c)
	if tree.Len() != 1 {
		t.Errorf("stored %d entries for one key, want 1", tree.Len())
	}
	if got, _ := tree.Get("same", &c); got.ID != 2 {
		t.Errorf("got ID %d, want 2 — the last Put should win", got.ID)
	}
}

// THE MIRROR OF LESSON 10. There the test demanded that Keys() was NOT sorted,
// because a hash index cannot promise order. Here it demands that it IS —
// and that no sorting happened to achieve it.
func TestKeysComeBackSorted(t *testing.T) {
	items := shuffledLib(500)
	tree := NewTreeIndex()
	var c metrics.Counter
	for _, it := range items {
		tree.Put(it, &c)
	}
	keys := tree.Keys()
	if len(keys) != 500 {
		t.Fatalf("got %d keys, want 500", len(keys))
	}
	if !sort.StringsAreSorted(keys) {
		t.Fatal("Keys() came back out of order — the in-order walk is wrong")
	}
	want := append([]string(nil), keys...)
	sort.Strings(want)
	for i := range keys {
		if keys[i] != want[i] {
			t.Fatalf("key %d = %q, want %q", i, keys[i], want[i])
		}
	}
	lo, _ := tree.Min()
	hi, _ := tree.Max()
	if lo != keys[0] || hi != keys[len(keys)-1] {
		t.Errorf("Min/Max = %q/%q, want %q/%q", lo, hi, keys[0], keys[len(keys)-1])
	}
}

func TestRangeReturnsOnlyTheBand(t *testing.T) {
	tree := NewTreeIndex()
	var c metrics.Counter
	for i := 0; i < 1000; i++ {
		tree.Put(Item{ID: i, Title: fmt.Sprintf("t%04d", i)}, &c)
	}
	var rc metrics.Counter
	got := tree.Range("t0100", "t0109", &rc)
	if len(got) != 10 {
		t.Fatalf("range returned %d titles, want 10: %v", len(got), got)
	}
	if got[0] != "t0100" || got[9] != "t0109" {
		t.Errorf("range = %v", got)
	}
	// A hash index would have to look at all 1000. The tree must not.
	if rc.N() >= 1000 {
		t.Errorf("visited %d nodes for a 10-key range — the walk is not pruning", rc.N())
	}
}

// On randomly-ordered input the depth must stay logarithmic.
func TestShuffledInsertStaysLogarithmic(t *testing.T) {
	const n = 20000
	items := shuffledLib(n)
	tree := NewTreeIndex()
	var c metrics.Counter
	for _, it := range items {
		tree.Put(it, &c)
	}
	// A randomly-built BST has expected height about 4.3*ln(n); 6*log2(n) is a
	// generous ceiling that a correct implementation clears easily.
	if limit := int(6 * math.Log2(n)); tree.Height() > limit {
		t.Errorf("height %d at n=%d, want <= %d", tree.Height(), n, limit)
	}
	var l metrics.Counter
	for _, it := range items {
		tree.Get(it.Title, &l)
	}
	if per := float64(l.N()) / n; per > 3*math.Log2(n) {
		t.Errorf("%.1f comparisons per lookup, want on the order of log2 n = %.1f", per, math.Log2(n))
	}
}

// THE DEFECT, ASSERTED SO IT STAYS VISIBLE — the same shape as lesson 7's
// selection sort, lesson 8's quicksort and lesson 9's unstable pass.
//
// Sorted insert order degenerates the tree into a linked list. There is no fix
// for this in lesson 11; the fix is lesson 12. If this test ever starts
// failing, you have built something other than a plain BST.
func TestSortedInsertDegeneratesIntoAList(t *testing.T) {
	const n = 2000
	tree := NewTreeIndex()
	var c metrics.Counter
	for i := 0; i < n; i++ { // already in order
		tree.Put(Item{ID: i, Title: fmt.Sprintf("t%05d", i)}, &c)
	}
	if tree.Height() != n {
		t.Fatalf("height %d at n=%d, want exactly %d — a sorted insert must "+
			"produce one long right spine", tree.Height(), n, n)
	}
	var l metrics.Counter
	for i := 0; i < n; i++ {
		tree.Get(fmt.Sprintf("t%05d", i), &l)
	}
	// (n+1)/2 — bit for bit what lesson 1's linear scan costs.
	if want := float64(n+1) / 2; math.Abs(float64(l.N())/n-want) > 0.001 {
		t.Errorf("%.1f comparisons per lookup, want %.1f — the linear scan's number",
			float64(l.N())/n, want)
	}
	// It is still CORRECT, and still in order. That is what makes it insidious.
	if !sort.StringsAreSorted(tree.Keys()) {
		t.Error("the degenerate tree stopped returning keys in order")
	}
}

main.go MODIFY 9 lines changed

Edit this file in ./

package main

import (
	"fmt"
	"os"
)

func usage() {
	fmt.Fprint(os.Stderr, `algo — your library workbench

  algo gen  [-n N] [-seed S] [-o FILE] [-sorted|-reverse|-shuffled] [-dup-rate R]
  algo find -title TITLE [-in FILE]
  algo load [-in FILE]
  algo stats -growth [-n N]
  algo playlist -from I -to J [-in FILE]
  algo history [-n N] [-in FILE]
  algo queue [-n N]
  algo walk [-depth D] [-branch B] [-per P]
  algo depth -n N [-iterative]
  algo sweep [-scattered]
  algo std [-n N]
  algo sort [-algo A] [-order O] [-in FILE]
  algo dc [-order O] [-in FILE]
  algo stable [-n N]
  algo count [-in FILE]
  algo radix [-in FILE]
  algo index [-in FILE] [-nogrow] [-buckets N]
  algo ordered [-in FILE] [-n N]
  algo alpha [-in FILE] [-n N] [-from A -to B]
  algo tree [-in FILE]
  algo shape [-shuffled FILE] [-sorted FILE]
`)
}

func main() {
	if len(os.Args) < 2 {
		usage()
		os.Exit(2)
	}
	var err error
	switch os.Args[1] {
	case "gen":
		err = cmdGen(os.Args[2:])
	case "find":
		err = cmdFind(os.Args[2:])
	case "load":
		err = cmdLoad(os.Args[2:])
	case "stats":
		err = cmdStats(os.Args[2:])
	case "playlist":
		err = cmdPlaylist(os.Args[2:])
	case "history":
		err = cmdHistory(os.Args[2:])
	case "queue":
		err = cmdQueue(os.Args[2:])
	case "walk":
		err = cmdWalk(os.Args[2:])
	case "depth":
		err = cmdDepth(os.Args[2:])
	case "sweep":
		err = cmdSweep(os.Args[2:])
	case "std":
		err = cmdStd(os.Args[2:])
	case "sort":
		err = cmdSort(os.Args[2:])
	case "dc":
		err = cmdDC(os.Args[2:])
	case "stable":
		err = cmdStable(os.Args[2:])
	case "count":
		err = cmdCount(os.Args[2:])
	case "radix":
		err = cmdRadix(os.Args[2:])
	case "index":
		err = cmdIndex(os.Args[2:])
	case "ordered":
		err = cmdOrdered(os.Args[2:])
	case "alpha":
		err = cmdAlpha(os.Args[2:])
	case "tree":
		err = cmdTree(os.Args[2:])
	case "shape":
		err = cmdShape(os.Args[2:])
	default:
		usage()
		os.Exit(2)
	}
	if err != nil {
		fmt.Fprintln(os.Stderr, "algo:", err)
		os.Exit(1)
	}
}