4.5 DRILL — Håndkjøring av heap og AVL

Full drill på sjanger E for de to sikreste håndkjøringsstrukturene: heap-innsetting/removeMin (indeks fra 0) og AVL-rotasjonstelling — mekanisk og feilfritt.

85 min

13 oppgaver

DRILLHåndkjøring av heapAVL

Din fremgang i kapitlet

0 / 13 oppgaver

Kapitlets plass i kurset

Bygger på

4.4Heap og prioritetskø

Brukes videre i

4.PPrøver til del 4: Trær: søketrær, balanserte trær og heap

Dette er drillkapitlet for håndkjøring — den sjangeren der det ikke finnes
noe å forstå, bare noe å beherske, og der svaret enten er helt riktig eller ikke.

- Sjanger E — håndkjøring av en datastruktur, altså at du utfører operasjonen
steg for steg på papiret og oppgir bare sluttilstanden.
- Min-heap har vært på 86 % av settene (6 av 7) i perioden boka bygger på,
og er den hyppigste håndkjøringskandidaten i hele faget.
- AVL-rotasjoner har vært på 43 % (3 av 7) — sjeldnere, men tyngre enn i
NTNUs TDT4120, der balanserte trær har mindre eksamensvekt. Her skal de
faktisk håndkjøres, ikke bare gjenkjennes.

Formatet du leverer er en del av oppgaven. For en min-heap er svaret hele
arrayet, kommaseparert, med indeks fra 0 — ikke treet. For et AVL-tre er svaret
antall enkle rotasjoner (en dobbelrotasjon teller som to), rotverdien til
slutt, og om resultatet er et gyldig AVL-tre. Leverer du noe annet, har du gjort
hele jobben og likevel mistet poeng.

Eksamen er hjelpemiddelfri: ingen bok, ingen maskin som kan kjøre operasjonen
for deg, og du skriver svaret rett inn i Inspera, som er UiOs digitale
eksamenssystem. Heap-indeksene og down-heap-regelen må derfor sitte i fingrene.

Prioritet: heap må sitte — høyeste prioritet. AVL ligger ett hakk under, men
er ofte det som skiller de øverste karakterene.

Slik er kapitlet lagt opp (85 min): oppskriften og et gjennomarbeidet
eksamenscase først (ca. 15 min), deretter tretten oppgaver i tre bolker —
innsetting i heap (ca. 20 min), RemoveMin og down-heap (ca. 25 min), og
AVL-rotasjoner med gyldighetsvurdering (ca. 25 min). Det summerer til 85 minutter.
Bolkene er uavhengige, så ta gjerne én per kveld. Etter hver bolk står en boks som
sier hva oppgavene testet. Begrepsbanken og repetisjonen helt til slutt kommer i
tillegg — de er repetisjonsstoff, ikke nytt stoff.

Forkunnskaper

Dette er en drill, ikke et nytt tema. Du skal ikke måtte bla for å komme i gang,
så her er de tre resultatene du bruker i hver eneste oppgave, ferdig oppfrisket.

Sist du var her — 1) heapen som array, indeks fra 0 (fra
kap. 4.4).

Rota ligger på indeks 0. For noden på indeks $i$ er forelderen
$\lfloor (i-1)/2 \rfloor$ (heltallsdivisjon, altså avrundet nedover), venstre
barn er $2i+1$ og høyre barn er $2i+2$ . Slik ligger de sju første indeksene:

                0
        1               2
    3       4       5       6

Noden på indeks 4 har forelder på indeks 1, fordi $\lfloor 3/2 \rfloor = 1$ , og
barn på indeks 9 og 10 — som bare finnes hvis heapen er stor nok. Legg merke til at
både indeks 3 og indeks 4 får forelder 1: heltallsdivisjonen kaster resten.

Sist du var her — 2) down-heap-regelen (fra kap. 4.4).

Når RemoveMin har flyttet det siste elementet opp til rota, synker elementet
nedover igjen. I hvert steg sammenlignes det med det minste av barna sine og
bytter plass med det hvis barnet er mindre. To detaljer avgjør poengene:

- barnet du bytter med skal være det minste, ikke det venstre;
- du må sjekke at barnet finnes før du leser det. Venstre barn finnes bare
hvis $2i+1$ er mindre enn antall elementer, og høyre barn kan mangle selv om
venstre finnes.

Sist du var her — 3) rotasjonstellingen i AVL (fra
kap. 4.3).

Et AVL-tre er høydebalansert: i hver node skiller høyden på venstre og høyre
subtre med høyst 1. Blir en node ubalansert etter en innsetting, rettes det med én
rebalansering — enkel rotasjon i tilfellene LL og RR, dobbelrotasjon i LR
og RL. En dobbelrotasjon er satt sammen av to enkle og teller derfor som to.
Én innsetting utløser høyst én rebalansering, aldri flere.

Trenger du grunnlaget bak: kap. 4.1 om binære søketrær,
kap. 4.3 om AVL og rød-svart-trær, og
kap. 4.4 om heap og prioritetskø. Kjøretidene bruker
$O$ -notasjonen fra kap. 1.1.

Notasjons- og pseudokodeliste

📜Løsningsoppskriften for håndkjøring av heap og AVL

To oppskrifter, én for hver struktur. Første steg er alltid å se hvilken av dem
du har foran deg.

Heap — Insert og RemoveMin.

1. Skriv indeksene over arrayet. Én linje med 0 1 2 3 4 … over verdiene.
Da kan du ikke miste tellingen, og forelder- og barnindeksene blir noe du
leser av i stedet for noe du husker.
2. Insert(H, x): legg x på første ledige indeks, altså indeks $n$ .
Sammenlign med forelderen på $\lfloor (i-1)/2 \rfloor$ . Er x mindre, bytt,
og gjenta fra den nye indeksen. Stopp når forelderen er mindre enn eller lik
x, eller når du står på indeks 0.
3. RemoveMin(H): ta vare på H[0], flytt det siste elementet opp til
rota og krymp arrayet med én plass. Sammenlign så med det minste barnet og
bytt hvis barnet er mindre. Gjenta fra den nye indeksen.
4. Sjekk at barnet finnes før du leser det. Venstre barn $2i+1$ finnes bare
hvis $2i+1$ er mindre enn $n$ ; finnes ikke venstre barn, er noden et blad og du
stopper. Finnes venstre, men ikke høyre, sammenligner du bare med venstre.
5. Lever bare arrayet, kommaseparert, med indeks fra 0.

AVL — innsetting med rotasjonstelling.

1. Sett inn som i et vanlig binært søketre: mindre til venstre, større til
høyre, ned til en ledig plass.
2. Gå oppover fra den nye noden og finn den første noden der
balansefaktoren er blitt $2$ eller $-2$ . Det er der rebalanseringen skjer.
3. Bestem tilfellet ut fra hvilken vei de to første stegene ned mot den nye
noden går: venstre–venstre (LL) og høyre–høyre (RR) gir enkel rotasjon;
venstre–høyre (LR) og høyre–venstre (RL) gir dobbel.
4. Legg til i telleren: enkel er $+1$ , dobbel er $+2$ , fordi dobbelrotasjonen
er to enkle utført etter hverandre. Fortsett så med neste innsetting.
5. Lever tre ting: totalt antall enkle rotasjoner, rotverdien til
slutt, og om treet er et gyldig AVL-tre.

De to kontrollene, noen sekunder hver, som fanger nesten alt:

- Heap: les arrayet ditt én gang til, og sjekk hvert forelder–barn-par mot
indeksformlene. Er H[0] det minste elementet, og er hver forelder mindre enn
eller lik begge barna? Er ikke det oppfylt, er svaret galt uansett hvor pen
sporingen din er.
- AVL: stemmer tellingen din med regnestykket «antall enkle rotasjoner pluss
to ganger antall dobbeltrotasjoner»? Og har du faktisk skrevet ned rotverdien?
Det er det oftest glemte delsvaret i hele sjangeren.

✏️Eksempel 1: Gjennomarbeidet eksamenscase med sensorkommentarer

(Eksamensnivå, sjanger E.) Et sett har denne oppgaven, verdt 6 poeng:

a) (2 p) Sett inn 7, 3, 9, 1 og 4 i denne rekkefølgen i en tom min-heap lagret
som array med indeks fra 0. Oppgi arrayet.

b) (2 p) Utfør deretter én RemoveMin på heapen fra a). Oppgi arrayet.

c) (2 p) Sett inn 20, 10, 30, 25 og 27 i denne rekkefølgen i et tomt AVL-tre.
Hvor mange enkle rotasjoner utføres totalt, hva er rotverdien til slutt, og er
resultatet et gyldig AVL-tre?

a) Innsettingene.

Steg	Sett inn	Array før sift-up	Bytter (indekser)	Array etter steget
1	7	`7`	ingen	`7`
2	3	`7, 3`	`1<->0`	`3, 7`
3	9	`3, 7, 9`	ingen	`3, 7, 9`
4	1	`3, 7, 9, 1`	`3<->1 ; 1<->0`	`1, 3, 9, 7`
5	4	`1, 3, 9, 7, 4`	ingen	`1, 3, 9, 7, 4`

Sluttilstand: 1, 3, 9, 7, 4

                1
               (0)
        3               9
       (1)             (2)
    7       4
   (3)     (4)

Legg merke til steg 4: 1-eren legges på indeks 3, bytter med forelderen på indeks
1, og bytter så én gang til med rota. To bytter, altså like mange som høyden på
det stedet den ble lagt inn.

Sensornotat, a) — 2 poeng. Typisk fordeling: 1 p for riktig sluttarray, 1 p
for at svaret faktisk er arrayet og ikke en tegning av treet.
Delvis riktig tilstand gir delvis uttelling. Har du riktig metode, men ett
element på feil plass, gir sporingen din som regel halv uttelling — forutsatt at
du har skrevet den ned. Det siste poenget henger på formatet: kommaseparert
array, indeks fra 0.

b) Én RemoveMin.
Operasjonen returnerer 1.

Delsteg	Handling	Array etter delsteget
1	ta vare på `H[0] = 1`; flytt siste element 4 til rot og krymp arrayet	`4, 3, 9, 7`
2	barna er `H[1] = 3` og `H[2] = 9`, minste er `H[1] = 3`; 4 er større enn 3, bytt	`3, 4, 9, 7`
3	kun venstre barn finnes: `H[3] = 7`; 4 er mindre enn 7, stopp	`3, 4, 9, 7`

Sluttilstand: 3, 4, 9, 7

                3
               (0)
        4               9
       (1)             (2)
    7
   (3)

Delsteg 3 er hele poenget med denne oppgaven. Etter delsteg 2 står 4-eren på

indeks 1. Barna til indeks 1 er indeks 3 og indeks 4. Arrayet har nå bare fire

elementer, altså indeks 0 til 3 — så høyre barn finnes ikke, og du

sammenligner bare med venstre. Leser du H[4] uansett, leser du utenfor arrayet.

Sensornotat, b) — 2 poeng. 1 p for riktig array, 1 p for at down-heap er
utført korrekt hele veien ned. Her ligger felle #3 i bokas feilregister:
down-heap uten å sjekke at barnet finnes. Sensorveiledningen — altså UiOs egen
retningslinje for hva som gir uttelling — har hatt et eksplisitt takpoeng på
denne: en besvarelse som leser et barn som ikke finnes, får ikke full pott selv
om sluttarrayet tilfeldigvis blir riktig.
Den andre halvdelen av samme felle er å bytte med venstre barn i stedet for
det minste. I delsteg 2 var venstre barn 3 og høyre 9, så her ville de to
reglene gitt samme svar — men det gjør de ikke alltid, og sensor ser hvilken du
brukte.

c) AVL-innsettingene.

Steg	Nøkkel	Ubalanse oppdaget i	Tilfelle	Rotasjon(er)	Enkle rot. i steget	Sum enkle rot.	Rot etter steget
1	20	ingen	–	ingen	0	0	20
2	10	ingen	–	ingen	0	0	20
3	30	ingen	–	ingen	0	0	20
4	25	ingen	–	ingen	0	0	20
5	27	30	LR	dobbelrotasjon om 30: først venstrerotasjon om 25, deretter høyrerotasjon om 30	2	2	20

Treet til slutt:

        20
   ____/ \__________
  10                27
               ____/ \____
              25          30

Svaret, i det formatet oppgaven ber om:
- Antall enkle rotasjoner: 2 (én dobbelrotasjon, som er to enkle).

- Rotverdi til slutt: 20.
- Gyldig AVL-tre: ja. Balansefaktorene er 20: $-1$ , 10: $0$ , 27: $0$ , 25: $0$ ,
30: $0$ — alle innenfor $-1$ til $1$ .

Sensornotat, c) — 2 poeng. 1 p for rotasjonstallet, 1 p for rotverdi og
gyldighet samlet.
Det ene svaret som koster flest poeng her, er «1 rotasjon». Det er riktig
hvis du teller rebalanseringer, men oppgaven spør etter enkle rotasjoner,
og en dobbelrotasjon er to. Les alltid hva som telles.
Merk også at rota ikke endret seg. Mange forventer at en rotasjon alltid gir
ny rot, men rebalanseringen skjedde nede i høyre subtre, om noden 30. Rotverdien
er et selvstendig delsvar nettopp fordi den ikke følger av rotasjonstallet.

Margnotat om delvis uttelling. Oppgaven er verdt 6 poeng fordelt på tre

uavhengige deler. Bommer du på heap-arrayet i a), kan du fortsatt få full pott på

b) hvis du utfører RemoveMin korrekt på din egen heap fra a) — sensor følger

sporingen din. Og c) er helt uavhengig av begge. La aldri en deloppgave stå

tom.

Bolk 1 — innsetting i min-heap (ca. 20 min)

Fire oppgaver på Insert og sift-up, fra sekvenser uten et eneste bytte til
sekvenser der hvert element må helt opp til rota. Bruk oppskriften hver gang, også
når oppgaven ser triviell ut — det er vanen du skal ha på eksamensdagen.

📝Oppgave 1

Eksamensnivå, sjanger E

Sett inn 6, 13, 4, 21, 9 og 2 i denne
rekkefølgen i en tom min-heap lagret som array med indeks fra 0.

a) Oppgi arrayet etter hver innsetting.
b) Oppgi sluttilstanden.
c) Hvilke innsettinger krevde ingen bytter i det hele tatt, og hvorfor?

📝Oppgave 2

Eksamensnivå, sjanger E

Sett inn 15, 10, 20, 8, 25, 5, 30 og 2 i denne
rekkefølgen i en tom min-heap (array, indeks fra 0).

a) Oppgi arrayet etter hver innsetting.
b) Oppgi sluttilstanden.
c) Hvor mange bytter kostet den siste innsettingen, og hva sier tallet om
høyden på heapen?

📝Oppgave 3

Eksamensnivå, sjanger E

Sett inn 40, 35, 30, 25, 20, 15 og 10 i denne
rekkefølgen i en tom min-heap (array, indeks fra 0).

a) Oppgi arrayet etter hver innsetting.
b) Oppgi sluttilstanden.
c) Hvert eneste element utløste minst ett bytte. Hvorfor, og hva ville skjedd
hvis sekvensen var snudd?

📝Oppgave 4

Eksamensnivå, sjanger E

En min-heap inneholder 2, 3, 7, 5, 4, 9, 8
(array, indeks fra 0). Sett inn 1.

a) Hvilken indeks legges 1-eren på, og hvilke indekser passerer den på vei
opp?
b) Oppgi arrayet etterpå.
c) Er det mulig å sette inn et element som havner lenger ned enn indeks 7 i
denne heapen? Begrunn.

De fire oppgavene rullerte hele Insert-mekanikken:

- Oppgave 1 testet grunntilfellet, der noen elementer sifter og andre blir
liggende, og at du ser hvorfor.
- Oppgave 2 testet den lengste mulige sift-up-veien i en heap med åtte
elementer, og at du bruker $\lfloor (i-1)/2 \rfloor$ og ikke en 1-indeksert
formel.
- Oppgave 3 testet verste tilfelle — en synkende sekvens der alt må til topps —
og at du ikke forventer at sluttarrayet er sortert.
- Oppgave 4 testet at plasseringen bestemmes av antall elementer, ikke av
verdien, og at et bytte flytter to elementer.

Klarte du 3 og 4 uten å nøle, sitter både indeksformlene og strukturkravet. Bommet
du, er kontrollen fra oppskriften verdt å gjøre til en vane: les arrayet ditt én
gang til og sjekk hvert forelder–barn-par.

Bolk 2 — `RemoveMin` og down-heap (ca. 25 min)

— naturlig pausepunkt —

Fire oppgaver på den operasjonen som gir flest tapte poeng i hele faget. Alle fire
handler om det samme spørsmålet: hvilket barn skal jeg sammenligne med, og finnes
det i det hele tatt?

📝Oppgave 5

Eksamensnivå, sjanger E

Min-heapen er 1, 3, 6, 5, 9, 8, 7 (array, indeks
fra 0). Utfør RemoveMin to ganger.

a) Oppgi arrayet etter første RemoveMin.
b) Oppgi arrayet etter andre RemoveMin.
c) Hvilke verdier returnerte de to operasjonene?

📝Oppgave 6

Eksamensnivå, sjanger E

Min-heapen er 2, 4, 3, 8, 6, 5, 7. Utfør
RemoveMin tre ganger, og oppgi arrayet etter hver av dem.

a) Etter første.
b) Etter andre.
c) Etter tredje.
d) I én av de tre operasjonene hadde noden bare ett barn. Hvilken, og hva
gjør du da?

📝Oppgave 7

Eksamensnivå, sjanger E

Min-heapen er 5, 9, 6, 11, 10, 8, 7, 15, 13
(ni elementer). Utfør RemoveMin én gang.

a) Oppgi arrayet etterpå.
b) Down-heapen valgte høyre barn i ett av stegene. Hvilket, og hvorfor?
c) Hva ville sluttarrayet blitt hvis du hadde byttet med venstre barn hver
gang i stedet?

📝Oppgave 8

Eksamensnivå, sjanger E

Min-heapen er 1, 2, 5, 4, 3, 9, 8, 7, 6 (ni
elementer). Utfør RemoveMin to ganger.

a) Oppgi arrayet etter første operasjon.
b) Oppgi arrayet etter andre.
c) Begge operasjonene stoppet før elementet nådde bunnen. Hvorfor er det ikke
en feil?

- Oppgave 5 testet den rene down-heapen to ganger på rad, og at du husker at
arrayet krymper mellom operasjonene.
- Oppgave 6 testet tilfellet der noden har bare venstre barn — felle
#3, og den enkeltdetaljen i faget som har hatt eksplisitt takpoeng i
sensorveiledningen.
- Oppgave 7 testet valget av minste barn i to steg på rad der høyre barn
vant, og viste hva som konkret går galt hvis du velger venstre.
- Oppgave 8 testet at down-heap stopper når noden ikke har flere barn, og at
et korrekt heap-array ikke er sortert.

Blir du usikker midt i en down-heap, gjør dette: skriv ned antall elementer
etter krympingen, og regn ut $2i+1$ og $2i+2$ for hver posisjon du står på. Er
$2i+1$ større enn eller lik antallet, er du ferdig — noden er et blad.

Bolk 3 — AVL-rotasjoner og gyldighetsvurdering (ca. 25 min)

Fem oppgaver. De tre første teller rotasjoner i innsettingssekvenser, den fjerde
viser sekvenser som ikke utløser noen rotasjon i det hele tatt, og den femte
ber deg avgjøre om en ferdig struktur er gyldig. Svaret er hver gang de samme tre
tingene: antall enkle rotasjoner, rotverdien, og gyldig eller ikke.

📝Oppgave 9

Eksamensnivå, sjanger E

Sett inn 100, 90, 80, 70, 60 og 50 i denne
rekkefølgen i et tomt AVL-tre.

a) Hvilke innsettinger utløste en rebalansering, og hvilket tilfelle var det?
b) Hvor mange enkle rotasjoner utføres totalt?
c) Hva er rotverdien til slutt, og er treet et gyldig AVL-tre?

📝Oppgave 10

Eksamensnivå, sjanger E

Sett inn 1, 2, 3, 4, 5, 6 og 7 i denne rekkefølgen i
et tomt AVL-tre.

a) Hvor mange enkle rotasjoner utføres totalt?
b) Hva er rotverdien til slutt?
c) Hvordan ser treet ut, og hva er spesielt med formen?

📝Oppgave 11

Eksamensnivå, sjanger E

Sett inn 10, 20, 30, 40, 50 og 25 i denne
rekkefølgen i et tomt AVL-tre.

a) Hvilke innsettinger utløste rebalansering, og hvilket tilfelle var hver av
dem?
b) Hvor mange enkle rotasjoner utføres totalt?
c) Hva er rotverdien til slutt, og er treet gyldig?
d) Hva ville svaret på b) blitt hvis oppgaven i stedet hadde spurt om antall
rebalanseringer?

📝Oppgave 12

Eksamensnivå, sjanger E

To innsettingssekvenser:

a) 8, 4, 12, 2, 6, 10, 14, 1, 3 i et tomt AVL-tre. Hvor mange enkle rotasjoner,
og hva er rotverdien?
b) 7, 3, 9, 1, 5, 8, 10, 4, 6, 2 i et tomt AVL-tre. Samme spørsmål.
c) Hva har de to sekvensene til felles, og hva er lærdommen for eksamen?

📝Oppgave 13

Eksamensnivå, sjanger E

Tre strukturer skal vurderes. Svar ja eller nei, og
begrunn med det konkrete bruddet der det finnes.

a) Er dette et gyldig AVL-tre?

                    40
               ____/ \____
              20          60
         ____/             \____
        10                      70
   ____/
  5

b) Er 3, 4, 8, 9, 5, 10, 12, 11 en gyldig min-heap (array, indeks fra 0)?
c) Er 2, 3, 5, 9, 4, 7, 6 en gyldig min-heap?
d) I c): er arrayet også et gyldig binært søketre lest som et komplett tre?

- Oppgave 9 testet en ren LL-sekvens og at rotverdien er et selvstendig
delsvar som ikke følger av rotasjonstallet.
- Oppgave 10 testet speilbildet, RR, og at én innsetting utløser høyst én
rebalansering.
- Oppgave 11 testet den ene detaljen som koster flest poeng i sjangeren:
dobbelrotasjon teller som to enkle, og oppgaven sier alltid hvilket tall den
vil ha.
- Oppgave 12 testet at null rotasjoner er et fullgodt svar, og at grensen
er balansefaktor $2$ eller $-2$ — ikke $1$ .
- Oppgave 13 testet gyldighetsvurdering av begge strukturene, og skillet
mellom heap-egenskapen (opp–ned) og søketre-egenskapen (venstre–høyre).

Er du i tvil om et rotasjonstall på eksamen: skriv ned hvilke rebalanseringer
du fant og hvilket tilfelle hver var. Da får du uttelling for resonnementet selv om
summeringen bommer, og du oppdager ofte feilen selv i samme slengen.

Typiske feil — fellekatalogen for håndkjøring av heap og AVL

Samlet, i den rekkefølgen de koster mest poeng.

- Down-heap uten å sjekke at barnet finnes — felle #3 i bokas
feilregister, og den ene detaljen som har hatt et eksplisitt takpoeng i
sensorveiledningen. Venstre barn $2i+1$ finnes bare hvis indeksen er mindre enn
antall elementer. Kontrollen: skriv ned antall elementer etter hver krymping.
- Down-heap mot venstre barn i stedet for det minste. De to reglene gir samme
svar av og til, og sensor ser hvilken du brukte. Skriv opp begge barneverdiene
før du velger.
- Dobbelrotasjon telt som én. En dobbelrotasjon er to enkle. Spør oppgaven om
enkle rotasjoner, er svaret det dobbelte av antall dobbelrotasjoner pluss
antall enkle.
- Glemt rotverdi eller glemt gyldighetssvar. AVL-svaret har tre deler, og de to
siste er de som oftest står igjen ubesvart.
- 1-indekserte heap-formler. Bruker du $\lfloor i/2 \rfloor$ og $2i$ , regner
du i en annen konvensjon enn faget. Riktig er $\lfloor (i-1)/2 \rfloor$ , $2i+1$
og $2i+2$ .
- Å levere treet i stedet for arrayet. Sluttilstanden på en heap-håndkjøring er
arrayet, kommaseparert, med indeks fra 0. Tegningen er ditt arbeidsverktøy, ikke
svaret.
- Å reparere en struktur før operasjonen. Får du en heap som du mistenker er
ugyldig, skal du utføre den oppgitte operasjonen på den heapen du fikk — ikke
«rydde» den først. Spør oppgaven derimot om strukturen er gyldig, er det den
vurderingen som er svaret.
- Å oppgi mer enn sluttilstanden. Sensor ber om sluttilstanden. Sporingen din
er verdt å ta med som arbeid, men den erstatter ikke et tydelig merket sluttsvar.
- Å forveksle heap-egenskapen med søketre-egenskapen — felle #9. Heapen
ordner opp–ned og sier ingenting om søsken; søketreet ordner venstre–høyre og
sier ingenting om at rota er minst.
- Å tro at et heap-array skal være sortert. 10, 25, 15, 40, 30, 35, 20 er en
helt korrekt min-heap.

Og den viktigste vanen: skriv ned delstegene mens du går. Blir sluttilstanden
feil, viser sporingen at metoden var riktig — og delvis riktig tilstand gir
delvis uttelling. Det siste poenget henger som regel på barn-sjekken i down-heap
og på at svaret er levert i eksamensformatet.

Begrepsbank

Begrepsbanken er flashcard-/repetisjonsstoff — den gjentar det du nettopp har
lest. Hopp trygt over ved førstegangslesing; tidsanslaget for kapitlet gjelder
kjernestoffet.

Heap-indeksene fra 0

i

Sift-up — innsetting i en min-heap

n

Down-heap — fjerning av minsteelementet

O(\log n)

Barn-sjekken i down-heap

2i+1

Sluttilstandsformatet for en heap

Svaret på en heap-håndkjøring er hele arrayet, kommaseparert, med indeks fra 0 — ikke treet, ikke bare elementene som ble flyttet, og ikke arrayet sortert. Tegningen av treet er ditt arbeidsverktøy underveis. Å levere den i stedet for arrayet koster poeng selv når innholdet er riktig.

Heap-egenskapen kontra søketre-egenskapen

Min-heapen ordner opp-ned : hver forelder er mindre enn eller lik begge barna, og det finnes ingen regel mellom søsken. Et binært søketre ordner venstre-høyre : alt i venstre subtre er mindre enn noden, alt i høyre er større. Å blande dem er felle #9 . Et korrekt heap-array er derfor sjelden sortert, og et binært søketre har sjelden det minste elementet i rota.

Enkel og dobbel rotasjon i et AVL-tre

Ubalanse i tilfellene LL og RR rettes med én enkel rotasjon; tilfellene LR og RL krever en dobbelrotasjon, som er to enkle utført etter hverandre. Tilfellet leses av veien fra den ubalanserte noden ned mot det nye elementet: to steg samme vei gir enkel, to steg i hver sin retning gir dobbel.

Rotasjonstellingen — dobbel teller som to

Spør oppgaven om antall enkle rotasjoner, teller hver dobbelrotasjon som 2 . Spør den om antall rebalanseringer, teller den som 1 . Dette er den enkeltdetaljen som koster flest poeng i AVL-sjangeren: to forskjellige tall for samme håndkjøring, og oppgaven sier alltid hvilket den vil ha.

Sluttilstandsformatet for et AVL-tre

Svaret har tre deler: antall enkle rotasjoner, rotverdien til slutt, og om resultatet er et gyldig AVL-tre . Rotverdien er et selvstendig delsvar — den endrer seg bare når rebalanseringen skjer i rota, og følger altså ikke av rotasjonstallet. Det er den delen som oftest står igjen ubesvart.

Balansefaktor

-1

Høyst én rebalansering per innsetting

2

Delvis uttelling på en håndkjøring

Sjanger E gir poeng per delmoment: riktig metode, riktig sluttilstand, og riktig format. Skriver du ned delstegene, får du uttelling for metoden selv om sluttilstanden blir feil. Det siste poenget henger typisk på barn-sjekken i down-heap og på at svaret er levert i eksamensformatet. Derfor skal ingen deloppgave stå tom — delene er uavhengige.

Repetisjon — kortet du tar med til eksamen

Dette kapitlet er skrevet av Anthropics toppmodeller (Claude Opus og Claude Fable) og er foreløpig ikke manuelt gjennomgått — kvalitetskontrollen gjøres av uavhengige KI-agenter, og innmeldte feil rettes fortløpende. Funnet en feil? Meld fra, så retter vi den. Les mer om hvordan innholdet lages.

Skolesaga er en uavhengig læringsressurs og er ikke tilknyttet eller godkjent av Universitetet i Oslo. Dette er ikke offisielt studiemateriell. Les mer.

4.5 DRILL — Håndkjøring av heap og AVL

Forkunnskaper

Bolk 1 — innsetting i min-heap (ca. 20 min)

Bolk 2 — RemoveMin og down-heap (ca. 25 min)

Bolk 3 — AVL-rotasjoner og gyldighetsvurdering (ca. 25 min)

Begrepsbank

Bolk 2 — `RemoveMin` og down-heap (ca. 25 min)