Pratybos
Penkios užduotys.
1. Sulaužyk jį tiksliai vienoje vietoje
Trys sabotažai, po vieną eilutę kiekvienas. Padaryk juos paeiliui ir kaskart paleisk visą testų rinkinį.
A. Trečio žingsnio spąstai — nepasiimk rezultato:
n.left = insert(n.left) // teisingai
insert(n.left) // A
B. Išimk iš rebalance vieną atvejį — kairė-dešinė.
C. Po rotacijos iškviesk fix tik pakilusiam mazgui, ne abiem.
Štai kas nutinka:
A --- FAIL: TestAVLStoresAndFinds
Get("00000"): ok=false id=0, want id=1
B --- FAIL: TestRotationsPreserveTheOrdering
balance 2 after 98 inserts, want <= 1
C --- FAIL: TestRotationsPreserveTheOrdering
balance 14 after 98 inserts, want <= 1
--- FAIL: TestHeightStaysBoundedOnSortedInput
n=1000: height 170 exceeds the AVL bound 14.0
Paaiškink kiekvieną. Ypač B: kodėl jis pralaužia balansą, bet neperžengia aukščio ribos? Paleisk jį ir pasižiūrėk, koks aukštis gaunasi zigzago tvarkai — skaičius bus po riba, bet blogesnis nei teisingos versijos.
Ir tada svarbiausias klausimas: B randamas tik testo, kuris tikrina statymo metu. Kodėl patikrinimo pabaigoje neužtektų?
2. Kuri rotacija kada suveikia
Įsivesk keturis skaitiklius į rebalance — po vieną kiekvienam atvejui — ir
pastatyk medį keturiomis įterpimo tvarkomis.
order LL LR RR RL total
shuffled 1100 1191 1204 1118 6922
ascending 0 0 9986 0 9986
descending 9986 0 0 0 9986
zigzag 1880 3111 1865 3127 16221
Paaiškink kiekvieną eilutę:
- kodėl didėjančiai tvarkai dvigubos rotacijos neprireikia nė karto?
- kodėl mažėjanti yra tikslus veidrodis?
- kodėl zigzage vyrauja būtent dvigubos?
- ir kodėl zigzago
totalyra 16 221, o ne 9 986, nors mazgų tiek pat? (Suskaičiuok iš stulpelių — atsakymas ten.)
3. Rečiausias įmanomas AVL medis
Antrame žingsnyje riba buvo išvesta iš N(h) = 1 + N(h−1) + N(h−2). Patikrink,
ar ji tiksli.
Apskaičiuok N(h) ir įstatyk į ribos formulę:
h N(h) bound(N)
4 7 4.24
6 20 6.10
8 54 8.04
10 143 10.01
12 376 12.01
Riba prilimpa prie h. Vadinasi, konstanta 1.4405 nėra iš oro paimta —
ji yra log₂(φ) atvirkštinė, kur φ yra auksinis pjūvis.
Parodyk, kad 1 / log2(1.618...) ≈ 1.4404. Paaiškink, kodėl būtent Fibonacci
seka atsiranda medyje, kuris apie Fibonacci nieko nežino.
4. Atlaisvink invariantą
Pakeisk sąlygą iš |balance| > 1 į |balance| > k ir pamatuok abi įvestis:
maišyta įvestis surikiuota įvestis
k height rotations k height rotations
1 16 6922 1 14 9986
2 17 3157 2 15 9985
3 19 1802 3 16 9984
5 22 682 5 18 9982
10 28 67 10 23 9977
Maišytoje įvestyje k = 2 perpus sumažina rotacijų, kainuodamas vieną lygį.
Atrodo kaip geras sandoris.
Surikiuotoje — rotacijų sutaupoma devynios iš 9 986, o aukštis auga.
Paaiškink, kodėl atlaisvinimas padeda ten, kur pagalbos nereikėjo, ir nepadeda
ten, kur dėl to viskas ir buvo daroma. Ir atsakyk: ar k = 2 yra gera mintis?
5. Kur šis medis vis dar pralaimi
Šeštame žingsnyje AVL laimėjo paiešką ir pralaimėjo įterpimą. Bet vienuoliktoje pamokoje buvo ir trečias dalyvis — surikiuotas masyvas su dvejetaine paieška.
Pamatuok visus tris prie n = 10 000, maišytoje įvestyje: pastatymas, paieška,
atmintis, ir kiek kainuoja vienas įterpimas į vidurį.
Tada įvardyk vienintelį stulpelį, kuriame AVL laimi masyvą — ir paaiškink, kodėl
to vieno stulpelio užtenka bibliotekos indeksui, bet neužtenka transit
išvykimų lentelei.