Šalinimo čia nėra — ir kiek tai kainuoja

avl.go neturi Delete. Tai sprendimas, ne spraga, ir verta pasakyti, kiek jis kainuoja.

Ką reikštų jį parašyti

Šalinimas iš AVL medžio yra vienuoliktos pamokos antroji pratybų užduotis (lapas / vienas vaikas / du vaikai su įpėdiniu), o po jos — rebalance grįžtant atgal. Realizuota ir pamatuota:

po 10 000 šalinimų iš 20 000: len 10000, aukštis 14 (riba 18.8), 4997 rotacijos

Veikia. Riba laikosi. Tvarka išlieka.

Kiek kodo:

	eilučių (be komentarų ir tuščių)
Put	21
Delete	40

Medžio keitimo kodas išauga nuo 21 iki 61 eilutės — maždaug trigubai.

Ir kiek naujo iš to sužinotum

Nieko.

Rotacijos yra tos pačios keturios. rebalance — ta pati funkcija, neliesta. Invariantas — tas pats. Riba — ta pati.

Nauja tik du dalykai, ir abu yra buhalterija, ne idėja:

• šalinant du vaikus turintį mazgą, taisyti reikia įpėdinio kelią, ne šalinamo mazgo;
• įterpiant pakanka vienos taisymo vietos — po jos aukščiai nustoja keistis; šalinant taisymas gali kilti iki pat šaknies.

Antrasis punktas yra vienintelis tikras skirtumas ir jis telpa į vieną sakinį. Už jį mokėti keturiasdešimt eilučių ir pusę pamokos — bloga mainų sąlyga.

Šios pamokos idėja yra invariantas, kuris apriboja aukštį, ir jį jau turi. Šalinimas tą pačią idėją pritaiko dar vienoje vietoje.

Todėl šalinimas yra kursinio darbo pasirinkimas, o ne pamokos žingsnis. Kas nori — turi viską, ko reikia: rotacijas, rebalance, ribą ir testą, kuris pasakys, ar pavyko.

Kur tokie medžiai iš tikrųjų gyvena

Trumpai, nes patikrinta, o ne spėta.

transit subalansuoto medžio neturi — vienuoliktoje pamokoje buvo peržiūrėti visi repozitorijos tipai ir medžio ten nėra jokio. Jam ir nereikia: jo indeksai statomi vieną kartą ir nebekeičiami, o tokiu atveju surikiuotas masyvas su dvejetaine paieška yra tobulai subalansuotas veltui.

Ir Go standartinėje bibliotekoje jo nėra. Visas container paketas yra:

container/heap    container/list    container/ring

Krūva, dvikryptis sąrašas ir žiedas. Jokio medžio. Go tvarkingą aibę siūlo kitaip — surikiuok griežinį ir naudok sort.Search, tą patį lowerBound, kurį rašei šeštoje pamokoje.

Tai nereiškia, kad subalansuoti medžiai nereikalingi. Tai reiškia, kad jie gyvena ten, kur duomenys nuolat keičiasi ir turi likti tvarkingi — duomenų bazių indeksuose, failų sistemose, branduolio planuoklėse. Tavo bibliotekos indeksas yra kaip tik toks: Put gali būti iškviesta bet kada.