Pamoka, kuri nesibaigia

Ši pamoka nesibaigia sprendimu. Baigiasi tuo, kad tiksliai žinai, kas sugedę.

Ko NEUŽTENKA

Keturi akivaizdūs pataisymai, ir kodėl kiekvienas per silpnas:

„Sumaišyk duomenis prieš įterpdamas." Sutvarko pastatymą ir nieko daugiau. Po to Put kviečiama iš programos, kai atsiranda naujas įrašas, ir tų kvietimų tvarkos nekontroliuoji. Vartotojas, dedantis knygas abėcėlės tvarka, atkuria tą pačią bėdą per savaitę.

„Perstatyk medį, kai jis per gilus." Kiekvienas perstatymas — O(n). Jei duomenys ateina surikiuoti, tai kartosis be paliovos, ir gausi struktūrą, kuri retkarčiais sustoja tam, kad išvengtų lėtumo, kurį ką tik sukėlė.

„Imk surikiuotą masyvą, kaip transit." Šeštas žingsnis parodė, kodėl tai gera mintis — ir kur ji lūžta. Įterpimas į masyvo vidurį yra O(n). Sandoris tik persikelia: iš „paieška gali išsigimti" į „įterpimas visada lėtas".

„Grįžk prie maišos lentelės." Tada nebeturi tvarkos, o dėl jos ši pamoka ir buvo. Pirmas žingsnis grįžta į pradinę padėtį.

Kas privalo būti tiesa

Surašyk, ko reikia, ir sąlygos susirikiuoja pačios:

1. medis privalo pats persitvarkyti įterpimo metu, ne po jo;
2. persitvarkymas privalo kainuoti ne daugiau nei paties įterpimo kelias — O(log n), ne O(n);
3. persitvarkius BST invariantas privalo išlikti — antrojo žingsnio sakinys, be išimčių;
4. ir po bet kokios įterpimų sekos aukštis privalo likti O(log n) — garantija, o ne viltis.

Ketvirtoji eilutė yra svarbiausia ir joje slypi visas skirtumas. Maišytos tvarkos medis ir dabar duoda apie 2.3 × log2 n. Tai ne blogai — bet tai sėkmė, o ne pažadas. Pastebėjai penktame žingsnyje: tas skaičius pamatuotas, nes niekas jo neužtikrina.

Vienuolikta pamoka pastatė struktūrą, kuri paprastai yra O(log n). Dvylikta pastato tokią, kuri yra O(log n) visada.

Tas skirtumas — tarp „paprastai" ir „visada" — ir yra visas AVL medis.

Ką turi dabar

Tvarkingą indeksą, atsakantį į šešis klausimus vietoj vieno, ir žinantį savo paties gylį.

Ir žinomą trūkumą, kurio testas neleis tyliai pamiršti: TestSortedInsertDegeneratesIntoAList reikalauja, kad Height() == n. Kol jis praeina, medis yra paprastas BST.

Dvyliktoje pamokoje tas testas turės nustoti praeidinėti — ir tai bus vienas iš nedaugelio kartų šiame kurse, kai testo sugriovimas bus tikslas.