Binary Trees & BST — Programuoki

Code

bst.go — the skeleton

Create bst.go. As since lesson 7 — package, types, signatures and contracts in the comments; the bodies are yours.

Worth noting:

Put with a key already present REPLACES the record. Exactly as in lesson 10: the two structures make the same promise about keys, and differ in what else they promise.
A new node always becomes a leaf. Do not rearrange anything. That is not a simplification or a placeholder — the shape that insertion order produces is what step 7 is about. "Fix" it and there is nothing left to measure.
Every key comparison goes through c.Hit(). That count is the depth you walked.
Range must skip subtrees that cannot contain an answer. The test checks that far fewer nodes were visited than exist — a full walk with a filter at the end does not count.
Height counts nodes, not edges. An empty tree is 0, a single node is 1. Step 7's table depends on that definition.

Recursion is natural here: Keys, Range and Height describe themselves in terms of themselves, like lesson 5's traversals. Get, Put, Min and Max are plain loops — recursion buys them nothing.

Gotcha

Put has to modify the pointer inside the node, not a copy of it.

cur := t.root          // a copy: attach a node to cur and the tree never sees it
cur := &t.root         // a pointer to the pointer: `*cur = &node{...}` changes the tree

This is the classic mistake in this exercise, and it does not announce itself: Put returns no error, Len goes up, and Get finds nothing. The second form — or a recursive insert that returns the new subtree — are both correct.

bst.go CREATE

Create this file in ./

package main

import "algo/metrics"

// This file is YOURS to fill in. The algorithm is in step 2; bst_test.go decides
// whether you got it right.
//
// Every comparison between two KEYS goes through c.Hit(). That count is the
// DEPTH you walked, and the depth is what "O(log n)" rests on — so it is the
// number step 7 is about.

// node is one node of the tree. Two pointers, where lesson 10's entry had one.
type node struct {
	key   string
	item  Item
	left  *node
	right *node
}

// TreeIndex is a binary search tree keyed on Title.
//
// The interface is deliberately the SAME SHAPE as lesson 10's HashIndex — Put,
// Get, Len, Keys — so the two are directly comparable. What differs is what the
// structure PROMISES, and what that promise costs.
type TreeIndex struct {
	root *node
	n    int
}

func NewTreeIndex() *TreeIndex { panic("not implemented") }

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

// Put stores an item under its Title.
//
// An equal key must REPLACE the existing record, exactly as in lesson 10 — the
// two structures make the same promise about keys.
//
// A new node is always added as a LEAF. Do not rearrange anything: the shape
// that insertion order produces is the subject of step 7.
func (t *TreeIndex) Put(it Item, c *metrics.Counter) {
	panic("not implemented")
}

// Get finds an item by Title, counting every key comparison. That count is the
// depth walked.
func (t *TreeIndex) Get(title string, c *metrics.Counter) (Item, bool) {
	panic("not implemented")
}

// Keys returns every stored Title IN SORTED ORDER, with no sorting done.
//
// This is the whole lesson. Lesson 10's Keys() came back in bucket order and its
// step 8 could not do better at any price; here the order falls out of the
// structure, because the tree never held the keys any other way.
func (t *TreeIndex) Keys() []string {
	panic("not implemented")
}

// Range returns every Title in [lo, hi], in order.
//
// It must NOT visit the whole tree: skip any subtree that cannot contain an
// answer. Count every node you do visit — the test checks that the pruning is
// real.
func (t *TreeIndex) Range(lo, hi string, c *metrics.Counter) []string {
	panic("not implemented")
}

// Min returns the smallest key: walk left until you cannot.
func (t *TreeIndex) Min() (string, bool) { panic("not implemented") }

// Max returns the largest key: walk right until you cannot.
func (t *TreeIndex) Max() (string, bool) { panic("not implemented") }

// Height is the length of the longest root-to-leaf path, in nodes. It is the
// WORST-CASE lookup cost, and step 7 is about how far it can drift from
// log2(n).
func (t *TreeIndex) Height() int { panic("not implemented") }