Pratybos
Penkios užduotys.
1. Išsaugok ir atkurk medį
Nori medį įrašyti į failą ir vėliau atstatyti. Akivaizdus būdas: išsaugoti
Keys() ir įkeliant iškviesti Put kiekvienam raktui iš eilės.
Pastatyk 2 000 įrašų medį, įsimink jo aukštį, tada atkurk jį taip ir vėl išmatuok aukštį.
Tada pabandyk išankstinį (pre-order) apėjimą — „aš, kairė, dešinė" — ir atkurk iš jo.
original tree: height 37
reloaded from in-order: height 2000
reloaded from pre-order: height 37
Paaiškink abu skaičius. Kodėl išankstinis apėjimas atkuria lygiai tą pačią formą, o simetrinis — sunaikina?
Ir kas iš to seka apie tai, ką reiškia „išsaugoti medį"? Ką iš tikrųjų saugai — aibę ar struktūrą?
2. Delete
Pridėk func (t *TreeIndex) Delete(title string, c *metrics.Counter) bool.
Trys atvejai, ir tik trečiasis sunkus:
- šalinamas mazgas yra lapas → nukirsk;
- turi vieną vaiką → pakelk vaiką į jo vietą;
- turi du vaikus → pakeisk jį savo įpėdiniu (mažiausiu raktu dešiniajame pomedyje), tada pašalink įpėdinį iš jo senos vietos.
Ištrink 500 iš 1 000 ir patikrink tris dalykus: Len() yra 500, ištrintų
neberandi, o likusius randi — ir Keys() vis dar surikiuotas. Paskutinis
punktas ir yra tikrasis testas: neteisingas Delete dažniausiai palieka medį,
kuris randa, bet nebėra tvarkingas.
Klausimas pabaigai: kodėl būtent įpėdinis? Kodėl tinka ir pirmtakas (didžiausias kairiajame pomedyje), o bet kuris kitas mazgas — ne?
3. Ar apkarpymas tikras
Parašyk rangeNoPrune: pilnas apėjimas su filtru pabaigoje. Rezultatas tas
pats; svarbu, kiek mazgų aplankyta.
range t05000..t05009: 10 rastų — apkarpytas 28, pilnas 10000
range t02000..t02999: 1000 rastų — apkarpytas 1016, pilnas 10000
range t00000..t09999: 10000 rastų — apkarpytas 10000, pilnas 10000
Paaiškink paskutinę eilutę. Kodėl apkarpymas ten nieko nelaimi — ir kodėl tai ne trūkumas?
Tada užrašyk Range kainą per du dydžius: n ir rastų skaičių k. Kuris iš
jų iš tikrųjų lemia?
4. Pirmtakas, įpėdinis ir „kitos 20"
Realizuok Successor(title string) (string, bool) — mažiausią raktą, didesnį už
duotą.
Du atvejai: jei mazgas turi dešinįjį pomedį, atsakymas ten (mažiausias jame); jei ne — reikia lipti aukštyn, o tavo mazgai tėvo rodyklės neturi. Išspręsk tai nepridėdamas tėvo rodyklės (užuomina: įsimink paskutinį posūkį kairėn leidžiantis).
Tada padaryk „kitos 20 po šito" ir pamatuok, kiek mazgų kainuoja. Palygink su tuo, ką dešimtai pamokai reikėtų padaryti tam pačiam klausimui.
5. Kur medis pralaimi savo paties pomedžiui
Penktame žingsnyje medis atsiliko nuo maišos lentelės 12.8 karto, o šeštame
transit pasirinko surikiuotą masyvą.
Pamatuok trečią variantą: paimk Keys(), gauk surikiuotą pavadinimų masyvą ir
paieškai naudok šeštos pamokos BinarySearch.
Palygink visus tris prie n = 10 000: palyginimai vienam ieškojimui, laikas,
atmintis. Masyvas turėtų laimėti medžiui abiem rodikliais.
Vienu sakiniu atsakyk: jei surikiuotas masyvas laimi ir paieškoje, ir atmintyje, kodėl apskritai statei medį? (Atsakymas yra šeštame žingsnyje ir yra vienas žodis.)