Balanced Trees (AVL) — Programuoki

Code

The test checks a property, not an output

Three files: the harness, the tests, and three new commands.

command	what it does
`algo balance`	step 1's table: BST and AVL, two insertion orders
`algo rotate`	the price — build comparisons, time, and rotation count
`algo reload`	the answer to lesson 11's first drill

The tests check a property, not an output

That distinction matters enough to say out loud.

Every earlier lesson's tests checked an output: is it sorted, was the key found, were there fewer than so many comparisons. A test like that can in principle be passed by an algorithm other than the one asked for.

TestHeightStaysBoundedOnSortedInput checks the shape:

bound := 1.4405*math.Log2(float64(n)+2) - 0.3277
if float64(avl.Height()) > bound {
	t.Errorf("n=%d: height %d exceeds the AVL bound %.1f", n, avl.Height(), bound)
}

The input is strictly ascending — the same one that destroyed lesson 11's tree.

Lesson 11's BST returns every key correctly here. Keys() is sorted. Get never errs. And still:

n=  1000: height 1000 exceeds the AVL bound 14.0  (71x over)
n= 10000: height 10000 exceeds the AVL bound 18.8  (532x over)

532×. Correct answers do not come close to being enough here. Only the shape passes.

test	what it requires
`TestAVLStoresAndFinds`	finds everything stored, misses what was not
`TestRotationsPreserveTheOrdering`	the BST invariant and a balance of −1..1 during the build, not only at the end
`TestHeightStaysBoundedOnSortedInput`	height and comparisons stay under the AVL bound
`TestHeightStaysBoundedOnEveryAdversarialOrder`	the same for ascending, descending and zigzag
`TestRotationsAreAmortizedConstant`	rotations per insert do not grow with `n`

The second one checks every 97th insertion, not at the end. A wrong rotation often corrupts the tree temporarily and later insertions happen to "repair" it; a check only at the end lets that through.

The fourth takes the third worst-case order from lesson 11's homework — the zigzag, which also produced height n.

avlbench.go CREATE

Create this file in ./

package main

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

	"algo/metrics"
)

// cmdBalance is lesson 11's `shape` run again, with the balanced tree beside
// the plain one. Same libraries, same two insertion orders, one extra structure.
func cmdBalance(args []string) error {
	fs := flag.NewFlagSet("balance", 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("%-10s %-10s %8s %8s %10s %14s %12s\n",
		"structure", "insert", "n", "height", "log2 n", "cmps/lookup", "lookup time")
	for _, tc := range []struct {
		name  string
		items []Item
	}{{"shuffled", a}, {"-sorted", b}} {
		bst := NewTreeIndex()
		var c metrics.Counter
		for _, it := range tc.items {
			bst.Put(it, &c)
		}
		var l metrics.Counter
		t0 := time.Now()
		for _, it := range tc.items {
			bst.Get(it.Title, &l)
		}
		el := time.Since(t0)
		n := float64(bst.Len())
		fmt.Printf("%-10s %-10s %8d %8d %10.1f %14.1f %12s\n",
			"BST (11)", tc.name, bst.Len(), bst.Height(), math.Log2(n), float64(l.N())/n, el.Round(time.Microsecond))
	}
	for _, tc := range []struct {
		name  string
		items []Item
	}{{"shuffled", a}, {"-sorted", b}} {
		avl := NewAVLIndex()
		var c metrics.Counter
		for _, it := range tc.items {
			avl.Put(it, &c)
		}
		var l metrics.Counter
		t0 := time.Now()
		for _, it := range tc.items {
			avl.Get(it.Title, &l)
		}
		el := time.Since(t0)
		n := float64(avl.Len())
		fmt.Printf("%-10s %-10s %8d %8d %10.1f %14.1f %12s\n",
			"AVL (12)", tc.name, avl.Len(), avl.Height(), math.Log2(n), float64(l.N())/n, el.Round(time.Microsecond))
	}
	return nil
}

// cmdRotate is the price: what balancing costs on input the plain BST already
// handled perfectly well.
func cmdRotate(args []string) error {
	fs := flag.NewFlagSet("rotate", 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
	}

	bst := NewTreeIndex()
	var bc metrics.Counter
	t0 := time.Now()
	for _, it := range items {
		bst.Put(it, &bc)
	}
	bBuild := time.Since(t0)

	avl := NewAVLIndex()
	var ac metrics.Counter
	t0 = time.Now()
	for _, it := range items {
		avl.Put(it, &ac)
	}
	aBuild := time.Since(t0)

	n := float64(len(items))
	fmt.Printf("n = %d, inserted in the order given\n\n", len(items))
	fmt.Printf("  %-10s %14s %12s %12s %10s\n", "", "build cmps", "build time", "rotations", "height")
	fmt.Printf("  %-10s %14d %12s %12s %10d\n", "BST (11)", bc.N(), bBuild.Round(time.Microsecond), "-", bst.Height())
	fmt.Printf("  %-10s %14d %12s %12d %10d\n", "AVL (12)", ac.N(), aBuild.Round(time.Microsecond), avl.Rotations, avl.Height())
	fmt.Printf("\n  rotations per insert: %.3f\n", float64(avl.Rotations)/n)
	fmt.Printf("  worst |balance| anywhere in the AVL tree: %d\n", avl.WorstBalance())

	var bl, al metrics.Counter
	for _, it := range items {
		bst.Get(it.Title, &bl)
		avl.Get(it.Title, &al)
	}
	fmt.Printf("\n  lookups: BST %.3f cmps, AVL %.3f cmps\n", float64(bl.N())/n, float64(al.N())/n)
	return nil
}

// cmdReload answers lesson 11's drill 1: is the naive save-and-reload safe now?
func cmdReload(args []string) error {
	fs := flag.NewFlagSet("reload", 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
	}
	var c metrics.Counter

	bst := NewTreeIndex()
	avl := NewAVLIndex()
	for _, it := range items {
		bst.Put(it, &c)
		avl.Put(it, &c)
	}
	fmt.Printf("original:              BST height %5d, AVL height %5d\n", bst.Height(), avl.Height())

	// Save with Keys() — sorted — and reload by re-inserting, as the drill did.
	bst2 := NewTreeIndex()
	for _, k := range bst.Keys() {
		bst2.Put(Item{Title: k}, &c)
	}
	avl2 := NewAVLIndex()
	for _, k := range avl.Keys() {
		avl2.Put(Item{Title: k}, &c)
	}
	fmt.Printf("reloaded from Keys():  BST height %5d, AVL height %5d\n", bst2.Height(), avl2.Height())
	fmt.Printf("\nAVL rotations during that reload: %d (%.3f per insert)\n",
		avl2.Rotations, float64(avl2.Rotations)/float64(avl2.Len()))
	return nil
}

avl_test.go CREATE

Create this file in ./

package main

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

	"algo/metrics"
)

// avlBound is the proven AVL height limit: h <= 1.4405 * log2(n+2) - 0.3277.
// Every test below checks against this rather than against a number someone
// eyeballed, because the point of this lesson is that the bound is a GUARANTEE.
func avlBound(n int) float64 {
	return 1.4405*math.Log2(float64(n)+2) - 0.3277
}

func TestAVLStoresAndFinds(t *testing.T) {
	items := shuffledLib(1000)
	avl := NewAVLIndex()
	var c metrics.Counter
	for _, it := range items {
		avl.Put(it, &c)
	}
	if avl.Len() != 1000 {
		t.Fatalf("stored %d, want 1000", avl.Len())
	}
	for _, it := range items {
		got, ok := avl.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 := avl.Get("nėra tokio pavadinimo", &c); ok {
		t.Error("found a title that was never stored")
	}
	if avl.Len() != 1000 {
		t.Errorf("Len drifted to %d during lookups", avl.Len())
	}
}

// scrambledKeys is a deterministic xorshift key set — no math/rand, identical
// every run.
//
// The keys are DELIBERATELY not sequential. An orderly generator like
// fmt.Sprintf("t%05d", (i*7919)%n) turns out to exercise only the two SINGLE
// rotations; a version of rebalance with the left-right case deleted passes a
// whole suite built on such keys. These scrambled keys drive all four cases, and
// that omission then shows up as a node with balance 2.
func scrambledKeys(n int) []string {
	out := make([]string, n)
	x := uint64(88172645463325252)
	for i := range out {
		x ^= x << 13
		x ^= x >> 7
		x ^= x << 17
		out[i] = fmt.Sprintf("k%016x", x)
	}
	return out
}

// Rotations rearrange the tree, so the thing lesson 11 was built for must
// survive every one of them.
func TestRotationsPreserveTheOrdering(t *testing.T) {
	keys := scrambledKeys(2000)
	avl := NewAVLIndex()
	var c metrics.Counter
	for i, k := range keys {
		avl.Put(Item{ID: i, Title: k}, &c)
		if i%97 == 0 { // check DURING the build, not only at the end
			if !sort.StringsAreSorted(avl.Keys()) {
				t.Fatalf("a rotation broke the BST invariant after %d inserts", i+1)
			}
			if b := avl.WorstBalance(); b > 1 {
				t.Fatalf("balance %d after %d inserts, want <= 1", b, i+1)
			}
		}
	}
	if b := avl.WorstBalance(); b > 1 {
		t.Fatalf("balance %d in the finished tree, want <= 1", b)
	}
	out := avl.Keys()
	lo, _ := avl.Min()
	hi, _ := avl.Max()
	if lo != out[0] || hi != out[len(out)-1] {
		t.Errorf("Min/Max = %q/%q, want %q/%q", lo, hi, out[0], out[len(out)-1])
	}
	if avl.Rotations == 0 {
		t.Error("no rotations happened at all — nothing was being balanced")
	}
}

// THE CONTRACT OF THIS LESSON, AND IT IS A PROPERTY RATHER THAN AN OUTPUT.
//
// The input is the one that destroyed lesson 11's tree: strictly ascending.
// A plain BST answers every query correctly here and still fails this test by
// two orders of magnitude — height 10000 against a bound of about 19.
//
// You cannot pass this by producing the right keys. Only the shape passes it.
func TestHeightStaysBoundedOnSortedInput(t *testing.T) {
	for _, n := range []int{1000, 10000, 100000} {
		avl := NewAVLIndex()
		var c metrics.Counter
		for i := 0; i < n; i++ { // strictly ascending
			avl.Put(Item{ID: i, Title: fmt.Sprintf("t%08d", i)}, &c)
		}
		bound := avlBound(n)
		if float64(avl.Height()) > bound {
			t.Errorf("n=%d: height %d exceeds the AVL bound %.1f", n, avl.Height(), bound)
		}
		if b := avl.WorstBalance(); b > 1 {
			t.Errorf("n=%d: some node has balance %d, want <= 1", n, b)
		}
		var l metrics.Counter
		for i := 0; i < n; i++ {
			avl.Get(fmt.Sprintf("t%08d", i), &l)
		}
		if per := float64(l.N()) / float64(n); per > bound {
			t.Errorf("n=%d: %.1f comparisons per lookup, bound is %.1f", n, per, bound)
		}
		t.Logf("n=%6d: height %2d, bound %.1f, %.3f cmps/lookup", n, avl.Height(), bound, float64(l.N())/float64(n))
	}
}

// The same bound under DESCENDING input, which is the mirror case, and under a
// zigzag that also killed the plain tree (homework 4 of lesson 11).
func TestHeightStaysBoundedOnEveryAdversarialOrder(t *testing.T) {
	const n = 20000
	keys := make([]string, n)
	for i := range keys {
		keys[i] = fmt.Sprintf("t%08d", i)
	}
	orders := map[string][]string{}
	orders["ascending"] = keys
	desc := make([]string, n)
	for i, k := range keys {
		desc[n-1-i] = k
	}
	orders["descending"] = desc
	zig := make([]string, 0, n)
	for lo, hi := 0, n-1; lo <= hi; lo++ {
		zig = append(zig, keys[lo])
		if lo < hi {
			zig = append(zig, keys[hi])
			hi--
		}
	}
	orders["zigzag"] = zig

	bound := avlBound(n)
	for name, order := range orders {
		avl := NewAVLIndex()
		var c metrics.Counter
		for _, k := range order {
			avl.Put(Item{Title: k}, &c)
		}
		if avl.Len() != n {
			t.Fatalf("%s: stored %d, want %d", name, avl.Len(), n)
		}
		if float64(avl.Height()) > bound {
			t.Errorf("%s: height %d exceeds the bound %.1f", name, avl.Height(), bound)
		}
		if !sort.StringsAreSorted(avl.Keys()) {
			t.Errorf("%s: the tree is not in order", name)
		}
		t.Logf("%-11s height %2d (bound %.1f), %.3f rotations per insert",
			name, avl.Height(), bound, float64(avl.Rotations)/float64(n))
	}
}

// REBALANCING MUST BE AMORTIZED CONSTANT. If it were not, the guarantee would be
// paid for with a cost that grows, and the whole trade would collapse.
//
// The ceiling is 2.0 rather than 1.0 because the zigzag order above needs ~1.62
// rotations per insert — the most expensive order measured. What matters is that
// the figure does not GROW with n.
func TestRotationsAreAmortizedConstant(t *testing.T) {
	for _, n := range []int{1000, 10000, 100000} {
		avl := NewAVLIndex()
		var c metrics.Counter
		for i := 0; i < n; i++ {
			avl.Put(Item{Title: fmt.Sprintf("t%08d", i)}, &c)
		}
		if per := float64(avl.Rotations) / float64(n); per > 2.0 {
			t.Errorf("n=%d: %.3f rotations per insert, want a small constant", n, per)
		}
	}
}

// THE PRICE, measured with the clock rather than the counter.
//
// The counter cannot see a rotation — rotations are not comparisons — so these
// benchmarks are the only place the cost of balancing is visible at all. Run
// them with:
//
//	go test -run XXX -bench 'Build|Lookup' -benchtime=20x -count=5
//
// They need s10k.jsonl (algo gen -n 10000 -seed 7 -o s10k.jsonl) and skip
// without it.
func benchItems(b *testing.B) []Item {
	items, err := load("s10k.jsonl")
	if err != nil {
		b.Skip(err)
	}
	return items
}

func BenchmarkBuildBST(b *testing.B) {
	items := benchItems(b)
	var c metrics.Counter
	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		t := NewTreeIndex()
		for _, it := range items {
			t.Put(it, &c)
		}
	}
}

func BenchmarkBuildAVL(b *testing.B) {
	items := benchItems(b)
	var c metrics.Counter
	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		t := NewAVLIndex()
		for _, it := range items {
			t.Put(it, &c)
		}
	}
}

func BenchmarkLookupBST(b *testing.B) {
	items := benchItems(b)
	var c metrics.Counter
	t := NewTreeIndex()
	for _, it := range items {
		t.Put(it, &c)
	}
	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		for _, it := range items {
			t.Get(it.Title, &c)
		}
	}
}

func BenchmarkLookupAVL(b *testing.B) {
	items := benchItems(b)
	var c metrics.Counter
	t := NewAVLIndex()
	for _, it := range items {
		t.Put(it, &c)
	}
	b.ResetTimer()
	for i := 0; i < b.N; i++ {
		for _, it := range items {
			t.Get(it.Title, &c)
		}
	}
}

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]
  algo balance [-shuffled FILE] [-sorted FILE]
  algo rotate [-in FILE]
  algo reload [-in 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:])
	case "balance":
		err = cmdBalance(os.Args[2:])
	case "rotate":
		err = cmdRotate(os.Args[2:])
	case "reload":
		err = cmdReload(os.Args[2:])
	default:
		usage()
		os.Exit(2)
	}
	if err != nil {
		fmt.Fprintln(os.Stderr, "algo:", err)
		os.Exit(1)
	}
}