transit: medžio čia nėra

Ankstesnėse pamokose šioje vietoje būdavo transit — Vilniaus viešojo transporto maršrutų serveris, iš kurio traukdavome tikrus skaičius.

Šioje pamokoje jo nėra, nes transit neturi nė vieno medžio. Patikrinta: peržiūrėti visi repozitorijos tipai — nėra nei BST, nei AVL, nei raudonai-juodo medžio, nėra laukų left/right. Vieninteliai medžio pavidalo tipai yra byteNode ir runeNode, o tai prefiksų medžiai iš dešimtos pamokos: jie šakojasi pagal raidę, o ne pagal palyginimą, ir tvarkytos aibės nelaiko.

Taip ir pasakome, o ne ieškome, prie ko prisikabinti.

Bet įdomu, KĄ jis naudoja vietoj to

transit reikia lygiai to, dėl ko šioje pamokoje statėme medį: rasti pirmą elementą, ne mažesnį už duotą. „Koks artimiausias išvykimas po 8:15?"

Jo atsakymas — surikiuotas masyvas ir dvejetainė paieška, o ne medis:

func (b *BinaryDepartureIndex) NextDeparture(stopID string, afterSec int32) (int32, bool) {
	times := b.d.byStop[stopID]
	i := lowerBound(times, afterSec)
	if i == len(times) {
		return 0, false
	}
	return times[i], true
}

Tai šeštos pamokos lowerBound — tas pats, kurį rašei ten.

Kodėl jam to užtenka, o tau ne

Skirtumas vienas, ir jis lemiamas.

Departures sukuriamas vieną kartą LoadDepartures metu: duomenys nuskaitomi iš duomenų bazės, kiekvieno stotelės masyvas surikiuojamas ir daugiau niekada nekeičiamas. Laukas byStop yra neeksportuotas ir nė vienas metodas į jį nerašo.

Kai taip yra, surikiuotas masyvas laimi visais atžvilgiais:

	surikiuotas masyvas	BST
paieška	O(log n), tobula pusiausvyra veltui	O(log n) su blogesne konstanta
tvarkinga išvestis	jau tvarkinga	apėjimas
rėžis	du dvejetainiai ieškojimai + pjūvis	apkarpytas apėjimas
atmintis	be rodyklių, gretimai (cache)	+2 rodyklės mazgui, išbarstyta
įterpimas	O(n) — visa uodega slenka	O(log n)

Paskutinė eilutė ir yra viskas. Medis moka už tai, kad į jį galima įterpinėti po to, kai jis pastatytas. Jei tavo duomenys sukraunami vieną kartą ir toliau tik skaitomi, ta kaina mokama už nieką — imk masyvą.

Tavo biblioteka nėra tokia: Put gali būti iškviesta bet kada. Todėl medis.

Ir todėl septintas žingsnis yra tikras: būtent dėl to, kad forma priklauso nuo įterpimo tvarkos, ją galima sugadinti.