Klausimas, kurio 10 pamoka neatsakė

Dešimta pamoka baigėsi klausimu, į kurį tavo indeksas neatsakė: pateik biblioteką abėcėlės tvarka. Kibirų tvarka nieko nereiškė, o abėcėlinį sąrašą teko gauti surikiavus visus 1 000 raktų.

Štai tas pats klausimas, užduotas medžiui:

$ algo gen -n 1000 -seed 3
$ algo alpha -n 6 -from Bam -to Bat
the first 6 titles, walked out of the tree:
  Bagogū Guže
  Bamežanė Pako
  Bamila
  Basėrūno
  Batalu
  Batėvovu Sūvi

1000 keys in order, 0 comparisons, 0s
min "Bagogū Guže", max "Žūčibužu Kėpo"

range [Bam .. Bat]: 3 titles, 11 nodes visited out of 1000
  Bamežanė Pako
  Bamila
  Basėrūno

Tie patys šeši pavadinimai. Ta pati biblioteka, tas pats sėklos numeris.

Bet dešimtoje pamokoje jie kainavo viso 1 000 raktų rikiavimą, o čia — 0 palyginimų. Ne mažiau; nė vieno.

Kodėl nulis

Nes nieko nereikėjo rikiuoti. Medis niekada nelaikė raktų kita tvarka.

Maišos lentelė tvarką sunaikino — tai buvo jos darbas, todėl grandinėlės ir liko trumpos. Medis tvarką laiko savo sandaroje: kiekvieno mazgo kairėje guli mažesni raktai, dešinėje — didesni. Perėjus medį „kairė, aš, dešinė" tvarka, raktai išeina didėjimo tvarka, nes kitokios tvarkos juose ir nebuvo.

Rikiavimo funkcija čia neiškviesta. Tik apeita struktūra.

Ir viskas, ko dešimta pamoka negalėjo

Prisimeni tą lentelę? Štai ji dar kartą, su antru stulpeliu:

klausimas	maišos lentelė	medis
ar yra „Bamila"?	1.3 palyginimo	~16 palyginimų
kokia pirma abėcėlėje?	tik surikiavus viską	Min() — ėjimas kairėn
kurios prasideda „Ba"?	tik peržiūrėjus viską	rėžio užklausa
kokios 20 eina po „Bamila"?	nėra tokios sąvokos	apėjimo tęsinys
kokia knyga prieš šitą?	nėra tokios sąvokos	pirmtakas medyje
aukščiausias įvertinimas?	tik peržiūrėjus viską	Max() — ėjimas dešinėn

Atkreipk dėmesį į rėžio užklausą aukščiau: 11 aplankytų mazgų iš 1 000. Medis neapėjo bibliotekos — jis nusileido iki srities ir praleido pomedžius, kuriuose atsakymo būti negalėjo.

Ir atkreipk dėmesį į pirmą eilutę. Medis pralaimi. 16 palyginimų prieš 1.3 — dvylika kartų daugiau tam vieninteliam klausimui, kurį maišos lentelė moka.

Tai ne pralaimėjimas ir ne pergalė. Tai antroji sandorio pusė, ir penktame žingsnyje sumokėsi už ją tiksliais skaičiais.

Spėk prieš skaitydamas toliau

Ir dar viena — ta, dėl kurios pamoka baigsis neužrišta.

Pirmoje pamokoje pasidarei vėliavėlę -sorted. Septintoje ji davė įterpimo rikiavimui geriausią atvejį. Aštuntoje quicksort'ui — blogiausią.

Ką ji padarys medžiui: palengvins darbą ar apsunkins?

Užsirašyk atsakymą. Septintame žingsnyje pamatuosi.