Kodas

bst.go — karkasas

Sukurk bst.go. Kaip įprasta nuo septintos pamokos — paketas, tipai, parašai ir sutartys komentaruose; kūnai tavo.

Ką verta pasižymėti:

Put su jau esamu raktu PAKEIČIA įrašą. Lygiai kaip dešimtoje pamokoje: abi struktūros duoda tą patį pažadą apie raktus ir skiriasi tuo, ką dar žada.
Naujas mazgas visada tampa lapu. Nieko nepertvarkyk. Tai ne supaprastinimas ir ne laikinas sprendimas — forma, kurią duoda įterpimo tvarka, yra septinto žingsnio tema. Jei „pataisysi", nebeliks ko matuoti.
Kiekvienas raktų palyginimas eina per c.Hit(). Tas skaičius yra nueitas gylis.
Range privalo praleisti pomedžius, kuriuose atsakymo būti negali. Testas tikrina, kad aplankytų mazgų būtų gerokai mažiau nei visų — apėjimas su filtru pabaigoje neužskaitomas.
Height skaičiuoja mazgus, ne briaunas. Tuščias medis — 0, vienas mazgas — 1. Septinto žingsnio lentelė remiasi šiuo apibrėžimu.

Rekursija čia natūrali: Keys, Range ir Height aprašomi per patys save, kaip penktos pamokos apėjimai. Get, Put, Min ir Max yra paprasti ciklai — rekursija jiems nieko neduoda.

Spąstai

Put turi keisti rodyklę mazge, o ne jos kopiją.

cur := t.root          // kopija: prijungęs mazgą prie cur, prie medžio jo neprijungsi
cur := &t.root         // rodyklė į rodyklę: `*cur = &node{...}` keičia patį medį

Tai klasikinė šios užduoties klaida ir ji nepasireiškia iš karto: Put neišmeta klaidos, Len didėja, o Get neranda nieko. Antras variantas — arba rekursinis insert, grąžinantis naują pomedį — abu teisingi.

bst.go SUKURTI

Sukurk šį failą kataloge ./

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") }