Kodas

avl.go — karkasas

Sukurk avl.go. Karkasas kaip įprasta; kūnai tavo.

Didesnė šio failo dalis yra vienuoliktos pamokos kodas, perkeltas be pakeitimų — Get, Keys, Range, Min, Max yra tie patys, tik *node pakeistas į *avlNode. Rotacijos keičia formą, ne reikšmę. Kopijuok juos ir nesijausk sukčiaudamas: tai ir yra pastebėjimas, kad AVL medis yra BST.

Tikrai naujo — penkios funkcijos: height, balance, fix, dvi rotacijos ir rebalance.

Ką verta pasižymėti:

height privalo būti saugi nil atžvilgiu. Nesamo pomedžio aukštis yra 0. Pusė visų AVL klaidų yra pamiršta nil patikra būtent čia, ir jos pasirodo kaip „kartais nesubalansuota", ne kaip griūtis.
fix po rotacijos kviečiamas dviem mazgams, ir tvarka svarbi. Pirma tam, kuris nusileido, paskui tam, kuris pakilo — antrojo aukštis priklauso nuo pirmojo.
Vienodas raktas nebalansuojamas. Put su esamu raktu tik pakeičia įrašą; medžio forma nepasikeitė, tad ir taisyti nėra ko.
Rotacijos nėra palyginimai. c.Hit() kviečiamas tik lyginant raktus. Jei suskaičiuosi ir rotacijas, šeštas žingsnis nustos veikti — o jis kaip tik apie tai, ko skaitiklis nemato.
Height() čia yra O(1) — grąžina root.h. Vienuoliktoje pamokoje tam reikėjo apeiti visą medį. Tai nemokamas priedas prie lauko, kurį jau pridėjai.

Įterpimas turi būti rekursinis. Vienuoliktos pamokos ciklas su &(*cur).left čia netinka: taisyti reikia grįžtant atgal, o ciklas kelio atgal neturi.

Spąstai

rebalance grąžina naują pomedžio šaknį, ir kviečiantysis privalo tą reikšmę pasiimti:

n.left = insert(n.left)   // teisingai — pomedis gali turėti naują šaknį
insert(n.left)            // klaida — rotacija įvyko ir buvo pamesta

Antrasis variantas kompiliuojasi ir jokios klaidos neparodo. Len() didėja kiekvienu kvietimu, nes skaitiklis didinamas ten, kur sukuriamas lapas — bet pats lapas išmetamas, tad Get rakto neberanda. Pamatuota: krenta pats pirmas testas — Get("00000"): ok=false.

Tylus nieko nedarymas, kuris dar ir didina skaitiklį, yra piktesnis gedimas nei griūtis. Todėl avl_test.go pirmiausia ir tikrina, ar kiekvienas įdėtas raktas randamas.

avl.go SUKURTI

Sukurk šį failą kataloge ./

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