Namų darbas
Ką pateikti
algo su alpha, tree ir shape, praeinantis go test ./..., plius
ataskaita.
1. Trys struktūros, viena biblioteka
n = 1 000 / 10 000 / 100 000, ieškant kiekvieno pavadinimo:
| n | tiesinė (1 pam.) | maišos (10 pam.) | medis, maišytas | medis, -sorted |
|---|
Palyginimai vienam ieškojimui.
Vieno langelio neužpildyk — medžio prie -sorted, kai n = 100 000.
Vietoj skaičiaus parašyk, kiek palyginimų jis pareikalautų, ir kiek laiko tai
truktų pagal n = 10 000 matavimą. Paaiškink, kodėl to nepaleidai.
2. Kada medis atsiperka
Medis pralaimi maišos lentelei kiekvienoje paieškoje, bet laimi kiekvienoje tvarkingoje užklausoje.
Tarkim, programa atlieka S tikslaus rakto paieškų ir R rėžio užklausų.
Pamatuok, kiek maišos lentelei kainuoja viena rėžio užklausa (turi surikiuoti
viską arba peržiūrėti viską), ir kiek medžiui.
Nustatyk santykį R : S, ties kuriuo medis pradeda atsipirkti. Nurodyk savo
prielaidas.
3. Aukštis kaip diagnostika
Septintame žingsnyje išsigimęs medis buvo teisingas — jokia klaida nepasirodė.
Parašyk func (t *TreeIndex) Balance() float64, grąžinančią Height() padalytą
iš log2(Len()).
Kokią reikšmę laikytum normalia? Kokią — įtartina? Kokią — gedimu? Pagrįsk skaičiais iš penkto ir septinto žingsnių, ne nuojauta.
Tada atsakyk: kur šitą reikėtų tikrinti veikiančioje programoje — teste, ar kas kartą įterpiant, ar niekada?
4. Blogiausias atvejis, kurio pats nepaminėjai
Septintas žingsnis parodė -sorted ir -reverse. Abu duoda aukštį n.
Sugalvok trečią įterpimo tvarką, kuri irgi duoda aukštį n, bet nėra nei
didėjanti, nei mažėjanti. (Užuomina: medis išsigimsta, jei kiekvienas naujas
raktas patenka į kraštą — bet kraštas gali kaitalioti puses.)
Sugeneruok ją, paleisk pro Height() ir parodyk rezultatą.
5. Ką tiksliai turi pataisyti dvylikta pamoka
Vienas pastraipos ilgio atsakymas, savais žodžiais, be „subalansuoto medžio" sąvokos:
- kas tiksliai sugenda, kai medis išsigimsta;
- kodėl to nepataiso nė vienas iš keturių aštunto žingsnio bandymų;
- ir kokį pažadą turėtų duoti struktūra, kad problemos nebeliktų.
Tavo pastraipa turėtų būti dvyliktos pamokos reikalavimų sąrašas. Pradėdamas ją, patikrink, ar buvai teisus.