Balanced Trees (AVL) — Programuoki

Code

avl.go — the skeleton

Create avl.go. The usual skeleton; the bodies are yours.

Most of this file is lesson 11's code carried across unchanged — Get, Keys, Range, Min, Max are identical with *node replaced by *avlNode. Rotations change the shape, not the meaning. Copy them and do not feel like you are cheating: that is the observation that an AVL tree is a BST.

Genuinely new: five functions — height, balance, fix, the two rotations, and rebalance.

Worth noting:

height must be nil-safe. An absent subtree has height 0. Half of all AVL bugs are a missing nil check right here, and they show up as "sometimes unbalanced" rather than as a crash.
fix runs on two nodes after a rotation, and the order matters. The one that moved down first, then the one that moved up — the second one's height depends on the first.
An equal key does not rebalance. Put on an existing key only replaces the record; the shape did not change, so there is nothing to repair.
Rotations are not comparisons. c.Hit() fires only when two keys are compared. Count rotations there too and step 6 stops working — and step 6 is precisely about what the counter cannot see.
Height() is O(1) here — it returns root.h. In lesson 11 it had to walk the whole tree. That is a free dividend from the field you just added.

Insertion has to be recursive. Lesson 11's loop over &(*cur).left will not do: the repair happens on the way back up, and a loop has no way back up.

Gotcha

rebalance returns the new subtree root, and the caller has to take that value:

n.left = insert(n.left)   // correct — the subtree may have a new root
insert(n.left)            // wrong — a rotation happened and was thrown away

The second version compiles and reports no error. Len() climbs on every call, because the counter is incremented where the leaf is created — but the leaf itself is thrown away, so Get cannot find the key. Measured: the very first test fails with Get("00000"): ok=false.

A silent no-op that still increments the count is a nastier failure than a crash, and it is the reason the first thing avl_test.go checks is that every key stored can be found again.

avl.go CREATE

Create this file in ./

package main

import "algo/metrics"

// This file is YOURS to fill in. The algorithm is in step 2; avl_test.go decides
// whether you got it right — and it checks a PROPERTY, not an output. Producing
// the right keys is not enough here.
//
// Every comparison between two KEYS still goes through c.Hit(). Rotations are
// NOT comparisons and must not be counted as any — step 6 is about the fact that
// the counter cannot see them.

// avlNode is lesson 11's node with ONE extra field: its own height.
type avlNode struct {
	key   string
	item  Item
	left  *avlNode
	right *avlNode
	h     int // height of this subtree, in nodes; a leaf is 1
}

// AVLIndex is a self-balancing binary search tree.
//
// Same interface as lesson 11's TreeIndex — Put, Get, Len, Keys, Range, Min,
// Max, Height — because it is the same structure. What it adds is a GUARANTEE:
// after any sequence of insertions the height stays within
//
//	h <= 1.4405 * log2(n+2) - 0.3277
//
// DELETION IS DELIBERATELY OUT OF SCOPE. See step 7 — there is no Delete here,
// and that is a decision rather than an omission.
type AVLIndex struct {
	root      *avlNode
	n         int
	Rotations int // how many rebalances it took to keep that promise
}

func NewAVLIndex() *AVLIndex { panic("not implemented") }

func (t *AVLIndex) Len() int { panic("not implemented") }

// height is nil-safe: an absent subtree has height 0. Write this first — every
// other function below leans on it, and half the bugs in an AVL tree are a
// forgotten nil check here.
func height(n *avlNode) int { panic("not implemented") }

// balance is height(left) - height(right), and must be nil-safe too.
func balance(n *avlNode) int { panic("not implemented") }

// fix recomputes n.h from its children. Call it after anything that can change
// a subtree's shape.
func fix(n *avlNode) { panic("not implemented") }

// rotateRight lifts the left child above n and returns the new subtree root.
// Remember to fix() BOTH nodes, and in the right order: the one that moved down
// first, because the one moving up depends on it. Count the rotation.
func (t *AVLIndex) rotateRight(n *avlNode) *avlNode { panic("not implemented") }

// rotateLeft is the mirror image.
func (t *AVLIndex) rotateLeft(n *avlNode) *avlNode { panic("not implemented") }

// rebalance restores the invariant at n and returns the new subtree root. Four
// cases; step 2 has them.
func (t *AVLIndex) rebalance(n *avlNode) *avlNode { panic("not implemented") }

// Put stores an item under its Title, rebalancing on the way back up.
//
// An equal key REPLACES the record, exactly as in lessons 10 and 11 — and it
// must NOT rebalance, because nothing changed shape.
func (t *AVLIndex) Put(it Item, c *metrics.Counter) { panic("not implemented") }

// Get is lesson 11's lookup, unchanged. Balancing changes the shape, not the
// search — so this function is allowed to be a straight copy.
func (t *AVLIndex) Get(title string, c *metrics.Counter) (Item, bool) {
	panic("not implemented")
}

// Keys, Range, Min and Max are lesson 11's, with *node swapped for *avlNode.
// Copy them across; rotations do not change what any of them mean.
func (t *AVLIndex) Keys() []string { panic("not implemented") }

func (t *AVLIndex) Range(lo, hi string, c *metrics.Counter) []string {
	panic("not implemented")
}

func (t *AVLIndex) Min() (string, bool) { panic("not implemented") }
func (t *AVLIndex) Max() (string, bool) { panic("not implemented") }

// Height is the stored height of the root — O(1) here, where lesson 11 had to
// walk the whole tree for it.
func (t *AVLIndex) Height() int { panic("not implemented") }

// WorstBalance returns the largest |balance| anywhere in the tree. If your
// invariant holds it is at most 1, and the test checks precisely that — so this
// is the function that tells you whether you have actually built an AVL tree.
func (t *AVLIndex) WorstBalance() int { panic("not implemented") }