3.3 DRILL — Håndkjøring av hauger og BST

Full drill på sjanger C for de to sikreste håndkjøringsstrukturene: bygg, sett inn, ekstraher og traverser — mekanisk og feilfritt.

85 min

14 oppgaver

DRILLHåndkjøring av haugerBST

Din fremgang i kapitlet

0 / 14 oppgaver

Kapitlets plass i kurset

Bygger på

3.2Binære søketrær

Håndkjøring av hauger og binære søketrær er den sikreste enkeltferdigheten i hele
faget. Temaet er talt i 16 av de 17 settene i grunnlaget (94 %), og det er
den hyppigste håndkjøringskandidaten av alle datastrukturene.

Dette kapitlet trener én sjanger, om og om igjen:

- Sjanger C — håndkjøring, altså at du utfører algoritmen steg for steg på
papir og oppgir bare sluttilstanden. Du får et array eller en
innsettingsrekkefølge, og skal levere strukturen etterpå, i det formatet
oppgaven ber om.

Høyeste prioritet — dette må sitte. Ferdigheten er mekanisk, den kan trenes
til den er feilfri, og den gir poeng uten at du trenger å finne på noe. Til
gjengjeld er den nådeløs: én feil indeks, og hele sluttilstanden er feil.

Tre ting avgjør uttellingen, og alle tre trenes her:

1. Riktig regel til riktig struktur. Haugen ordner seg oppover, søketreet
ordner seg sidelengs. Blander du dem, blir alt etterpå galt.
2. Mekanisk utførelse, også når input ser rar ut. Ber oppgaven deg kjøre en
operasjon på et array som ikke er en gyldig haug, skal du kjøre den likevel.
3. Riktig svarformat. En maks-haug leveres som hele arrayet fra indeks 1; et
søketre leveres som Inorder-Tree-Walk-utskriften. Riktig innhold i feil
format taper poeng helt unødvendig.

Slik er kapitlet lagt opp (85 min):

Del	Innhold	Tid
1	Løsningsoppskriften og de to reglene i kontrast	ca. 10 min
2	Den gjennomarbeidede eksamenscasen, med margnotater	ca. 15 min
3	Drill: `Build-Max-Heap`	ca. 15 min
4	Drill: `Heap-Extract-Max`, også på ugyldig input	ca. 15 min
5	Drill: én `Heapsort`-iterasjon	ca. 10 min
6	Drill: `Tree-Insert`, `Inorder-Tree-Walk` og `Tree-Maximum`	ca. 15 min
7	Blandet: hvilken regel gjelder?	ca. 5 min

Kapitlet er en treningsbank. Det er tre merkede pausepunkter underveis, og du
taper ingenting på å ta det over to økter.

Forkunnskaper

Dette kapitlet trener det du har lært i de to foregående, og innfører ingen ny
teori.

- kap. 3.1 — maks-haugen som array, Max-Heapify,
Build-Max-Heap, Heap-Extract-Max og Heapsort.
- kap. 3.2 — binære søketrær, Tree-Insert,
Inorder-Tree-Walk, Tree-Minimum og Tree-Maximum.

Dette sto der, og det er alt du trenger for å komme i gang:

Fra kap. 3.1: en maks-haug ligger i ett array
A[1..n] med indeks fra 1. Forelderen til posisjon $i$ er
$\lfloor i/2 \rfloor$ , og barna er $2i$ og $2i+1$ . Dette er
NTNU- og CLRS-konvensjonen, og den brukes gjennom hele denne boka.
Haugegenskapen er at $A[\lfloor i/2 \rfloor] \ge A[i]$ for alle
$i$ fra 2 til A.heap-size — altså at hver forelder er større enn eller lik
begge barna sine.

Fra kap. 3.2: et binært søketre lagrer nøkler slik at
alt i venstre deltre er mindre enn eller lik noden, og alt i høyre deltre er
større enn eller lik den. Inorder-Tree-Walk besøker venstre deltre, så noden,
så høyre deltre — og skriver derfor ut nøklene sortert.

Trenger du en mykere inngang til hva $O$ og $\Theta$ betyr før du leser
kjøretidene her, ligger den i
Algoritmedefinisjon, pseudokode og kompleksitet (Big-O).

Notasjons- og pseudokodeliste

Løsningsoppskriften — den du følger hver gang (~10 min)

En håndkjøringsoppgave gir deg tre ting: en struktur, en operasjon og et
spørsmål. Den ber deg nesten aldri forklare noe. Den ber om et resultat.

Derfor er oppskriften kort, og den er den samme hver gang. Lær den utenat, og
bruk den også når oppgaven ser uvant ut.

📜Løsningsoppskrift for håndkjøring av haug og søketre

For haug:

1. tegn arrayet som tre;
2. utfør Build-Max-Heap/Heap-Extract-Max/Heapsort-trinn mekanisk
(reparér ikke ugyldig input først — det er felle #10, å «reparere» en
ugyldig haug før du utfører operasjonen);
3. oppgi kun det etterspurte (sluttarray / rot / ett tall).

For BST:

1. sett inn i gitt rekkefølge;
2. for inorder — utnytt at utskriften er sortert;
3. oppgi sluttilstand.

Hvorfor punkt 1 er verdt de tretti sekundene det tar. Arrayet er den
offisielle representasjonen, men øyet ditt ser ikke forelder–barn-forholdet i en
tallrekke. Treet gjør feilene synlige med én gang. Du leverer arrayet — men du
regner i treet.

Hvorfor punkt 3 er en poengregel og ikke en stilregel. Oppgavetekstene sier
det rett ut: «oppgi arrayet etterpå», «oppgi utskriften». Skriver du i tillegg en
forklaring av algoritmen, bruker du tid du trenger på de andre oppgavene, og du
risikerer å motsi ditt eget svar.

Svarformatet, som er halve poenget:

Struktur	Det du leverer	Den vanlige tabben
Maks-haug	hele arrayet, kommaseparert, med indeks fra 1	å tegne treet og la det være svaret
Én `Heapsort`-iterasjon	hele arrayet etter iterasjonen, med haugstørrelsen oppgitt	å kjøre hele sorteringen når bare én iterasjon var spurt
BST	`Inorder-Tree-Walk`-utskriften, som er sortert	å tro at inorder gir innsettingsrekkefølgen

Delvis riktig tilstand gir delvis uttelling. Har du fire av seks tall på riktig
plass, har du et delsvar — men bare hvis det står et array der. Et tomt svarfelt
med et pent tre ved siden av gir ingenting.

De to reglene, ved siden av hverandre

Den mest fremhevede datastrukturfeilen i faget er felle #2 — å forveksle
søketreegenskapen (venstre $\le$ rot $\le$ høyre) med haugegenskapen (forelder
$\ge$ begge barn, ingen orden mellom venstre og høyre). De to figurene under er
kapitlets referansebilde. Kommer du i tvil midt i en oppgave, er det hit du går
tilbake.

Les figuren slik: i haugen til venstre kan du sammenligne en node med
forelderen sin, og bare det. 13 og 20 står side om side uten at rekkefølgen deres
betyr noe — begge er mindre enn 25, og det er hele kravet. I søketreet til høyre
kan du derimot lese av at 31 må ligge mellom 20 og 45, og at 52 må ligge mellom
45 og 68.

Kontrollen som tar fem sekunder: i et array som skal være en maks-haug,
sjekk A[1]. Er ikke det største tallet der, er det ingen gyldig maks-haug. I et
søketre: skriv ut inorder. Kommer tallene ikke sortert, har du satt inn feil vei
et sted.

— naturlig pausepunkt —

📜Pseudokode-kontrakt: `Max-Heapify` og `Heap-Extract-Max`

Antagelser om representasjon. Haugen er arrayet A[1..n] med indeks fra
1. Feltet A.heap-size sier hvor mange plasser som fortsatt hører til haugen;
resten av arrayet finnes, men er utenfor. Forelderen til i er floor(i/2), og
barna er 2i og 2i+1.

Prebetingelse for Max-Heapify(A, i): deltrærne med rot i 2i og 2i+1 er
maks-hauger. Postbetingelse: hele deltreet med rot i i er en maks-haug.

Max-Heapify(A, i)
  Input:  array A, indeks i, feltet A.heap-size
  Output: deltreet med rot i i oppfyller haugegenskapen
  l = 2*i
  r = 2*i + 1
  storst = i
  if l <= A.heap-size and A[l] > A[storst]
      storst = l
  if r <= A.heap-size and A[r] > A[storst]
      storst = r
  if storst != i
      bytt A[i] og A[storst]
      Max-Heapify(A, storst)
  Kjoretid: O(lg n)

Invarianten i én setning: elementet som er på vei ned, er alltid det eneste
mulige bruddet på haugegenskapen — alt annet under det er allerede i orden.

Heap-Extract-Max er bygget rett oppå denne:

Heap-Extract-Max(A)
  Input:  A[1..A.heap-size], som antas aa vaere en maks-haug
  Output: det stoerste elementet, og A reparert
  maks = A[1]
  A[1] = A[A.heap-size]
  A.heap-size = A.heap-size - 1
  Max-Heapify(A, 1)
  return maks
  Kjoretid: O(lg n)

Kjøretid: $O(\lg n)$ for begge. Max-Heapify flytter ett element høyst ett
nivå per bytte, og et komplett binærtre med $n$ noder har $\lfloor \lg n \rfloor$
nivåer over bunnen — én sti, ingen forgrening.

Legg merke til hva Heap-Extract-Max IKKE gjør: den sjekker ikke om A
faktisk er en maks-haug. Den leser A[1], uansett hva som står der. Det er
nøyaktig derfor oppgaven kan gi deg et ugyldig array og be deg kjøre likevel.

📜Pseudokode-kontrakt: `Tree-Insert` og `Inorder-Tree-Walk`

Antagelser om representasjon. Treet T har en rot T.rot. Hver node x har
feltene x.key, x.venstre og x.hoyre, der en manglende node er NIL.

Prebetingelse: T oppfyller søketreegenskapen. Postbetingelse etter
Tree-Insert: T inneholder én node til, og oppfyller fortsatt
søketreegenskapen.

Tree-Insert(T, k)
  Input:  soeketre T, ny noekkel k
  Output: T med k satt inn som blad
  if T.rot == NIL
      T.rot = ny node med noekkel k
      return
  x = T.rot
  while true
      if k < x.key
          if x.venstre == NIL
              x.venstre = ny node med noekkel k; return
          x = x.venstre
      else
          if x.hoyre == NIL
              x.hoyre = ny node med noekkel k; return
          x = x.hoyre
  Kjoretid: O(h)

Inorder-Tree-Walk(x)
  Input:  en node x, eller NIL
  Output: noeklene i deltreet under x, skrevet ut i sortert rekkefoelge
  if x != NIL
      Inorder-Tree-Walk(x.venstre)
      skriv ut x.key
      Inorder-Tree-Walk(x.hoyre)
  Kjoretid: Theta(n)

Grunnideen i én setning: Tree-Insert går nedover den ene stien der nøkkelen
hører hjemme og henger den inn der stien tar slutt, så alle nøkler som allerede
lå til venstre eller høyre for noden, blir liggende der.

Kjøretid: $O(h)$ for innsetting, der $h$ er treets høyde — $\Theta(\lg n)$
forventet for et tilfeldig bygd tre, men $\Theta(n)$ i verste tilfelle, når
nøklene kommer i sortert rekkefølge. Inorder-Tree-Walk er $\Theta(n)$ : hver
node besøkes nøyaktig én gang.

Den gjennomarbeidede eksamenscasen (~15 min)

Nå kjører vi en hel oppgave slik den ser ut på eksamen, og skriver i margen hva
som gir uttelling ved hvert steg. Etterpå gjør du det samme selv, tolv ganger.

✏️Eksempel 1: To haugoperasjoner etter hverandre, med margnotater

Et vaktlag på en fjellstue holder oversikt over ventende oppdrag i et array, der
tallet er hvor mange minutter oppdraget har hastet:

$A = [4,\ 12,\ 7,\ 1,\ 15,\ 9,\ 3,\ 10]$

a) Utfør Build-Max-Heap(A) og oppgi arrayet etterpå.

b) Utfør deretter Heap-Extract-Max(A) én gang. Oppgi hvilket tall som
returneres, og haugen etterpå.

a) Build-Max-Heap starter på

i = \lfloor n/2 \rfloor = \lfloor 8/2 \rfloor = 4

og teller ned til 1. Hvert kall på Max-Heapify er én rad; de rekursive kallene
står som egne rader.

Steg	Operasjon	Sammenligning	Array etter steget
1	`Max-Heapify(A, 4)`: bytt `A[4]` og `A[8]`	`A[4]=1`, venstre `A[8]=10`; størst er `A[8]`	`[4, 12, 7, 10, 15, 9, 3, 1]`
2	`Max-Heapify(A, 8)`: `A[8]` er allerede størst, stopp	`A[8]` har ingen barn innenfor haugstørrelsen	`[4, 12, 7, 10, 15, 9, 3, 1]`
3	`Max-Heapify(A, 3)`: bytt `A[3]` og `A[6]`	`A[3]=7`, venstre `A[6]=9`, høyre `A[7]=3`; størst er `A[6]`	`[4, 12, 9, 10, 15, 7, 3, 1]`
4	`Max-Heapify(A, 6)`: `A[6]` er allerede størst, stopp	`A[6]` har ingen barn innenfor haugstørrelsen	`[4, 12, 9, 10, 15, 7, 3, 1]`
5	`Max-Heapify(A, 2)`: bytt `A[2]` og `A[5]`	`A[2]=12`, venstre `A[4]=10`, høyre `A[5]=15`; størst er `A[5]`	`[4, 15, 9, 10, 12, 7, 3, 1]`
6	`Max-Heapify(A, 5)`: `A[5]` er allerede størst, stopp	`A[5]` har ingen barn innenfor haugstørrelsen	`[4, 15, 9, 10, 12, 7, 3, 1]`
7	`Max-Heapify(A, 1)`: bytt `A[1]` og `A[2]`	`A[1]=4`, venstre `A[2]=15`, høyre `A[3]=9`; størst er `A[2]`	`[15, 4, 9, 10, 12, 7, 3, 1]`
8	`Max-Heapify(A, 2)`: bytt `A[2]` og `A[5]`	`A[2]=4`, venstre `A[4]=10`, høyre `A[5]=12`; størst er `A[5]`	`[15, 12, 9, 10, 4, 7, 3, 1]`
9	`Max-Heapify(A, 5)`: `A[5]` er allerede størst, stopp	`A[5]` har ingen barn innenfor haugstørrelsen	`[15, 12, 9, 10, 4, 7, 3, 1]`

På eksamen leverer du bare linja under — tavlen er her for å vise hvordan du
kommer dit.
Svar a): [15, 12, 9, 10, 4, 7, 3, 1]
Som tre ser haugen slik ut:

                 15(1)
        12(2)             9(3)
   10(4)     4(5)     7(6)     3(7)
 1(8)

Margnotat til steg 1. Uttellingen begynner med startindeksen. Starter du på

i = n

i stedet for

i = \lfloor n/2 \rfloor

, gjør du fire unødvendige kall —
svaret blir riktig, men du bruker tid du ikke har. Starter du på

i = 1

, blir
svaret galt, fordi Max-Heapify forutsetter at deltrærne under allerede er
hauger.

Margnotat til steg 5. Her ligger det vanligste delpoengstapet i hele
oppgaven. A[2]=12 sammenlignes med begge barna, 10 og 15, og bytter med den

største. Bytter du med venstre barn fordi det står først, får du

[4, 10, 9, 12, 15, 7, 3, 1] — og der er $12 < 15$ , altså brudd på

haugegenskapen ett nivå ned.

Margnotat til steg 8. Etter byttet i steg 7 er ikke jobben ferdig: tallet 4
har havnet på posisjon 2 og må fortsette nedover. Stopper du etter det første
byttet i rota, mister du nettopp den delen av svaret sensuren kan se med én gang
— A[2] er da mindre enn A[5].
— naturlig pausepunkt —

b) Nå kjører vi Heap-Extract-Max på haugen fra a).

Steg	Operasjon	Sammenligning	Array etter steget
1	returner `A[1]` = 15; flytt `A[8]` = 1 til rota og sett `A.heap-size` = 7	ingen sammenligning	`[1, 12, 9, 10, 4, 7, 3]`
2	`Max-Heapify(A, 1)`: bytt `A[1]` og `A[2]`	`A[1]=1`, venstre `A[2]=12`, høyre `A[3]=9`; størst er `A[2]`	`[12, 1, 9, 10, 4, 7, 3]`
3	`Max-Heapify(A, 2)`: bytt `A[2]` og `A[4]`	`A[2]=1`, venstre `A[4]=10`, høyre `A[5]=4`; størst er `A[4]`	`[12, 10, 9, 1, 4, 7, 3]`
4	`Max-Heapify(A, 4)`: `A[4]` er allerede størst, stopp	`A[4]` har ingen barn innenfor haugstørrelsen	`[12, 10, 9, 1, 4, 7, 3]`

På eksamen leverer du bare linjene under — tavlen er her for å vise hvordan du
kommer dit.
Svar b): returnert verdi 15. Haugen etterpå: [12, 10, 9, 1, 4, 7, 3] med

A.heap-size = 7.
Margnotat til steg 1. Det er siste element i haugen som flyttes til rota,
ikke det siste i arrayet generelt, og ikke det største av barna. Her er de
heldigvis det samme, men i deloppgave b) på en oppgave der du allerede har

ekstrahert én gang, er de det ikke — og da er dette det avgjørende skillet.

Margnotat til svarformatet. Oppgaven spør om to ting: hvilket tall som

returneres, og haugen etterpå. Svarer du bare med arrayet, mangler du halve
svaret. Svarer du bare med tallet 15, mangler du den andre halvparten. Les
spørsmålet to ganger og tell hvor mange ting det ber om.
Fellenote. Fellen som er innebygd i denne oppgaven, er felle #9 — å
oppgi feil kjøretidsfakta, her at Build-Max-Heap skulle være
$\Theta(n\lg n)$ . Den er $\Theta(n)$ : de fleste kallene skjer nede i treet, der

elementene har kort vei å synke. Blir du bedt om kjøretiden i en deloppgave, er
$\Theta(n)$ svaret — og $O(\lg n)$ er svaret for Heap-Extract-Max.

Drill: `Build-Max-Heap` (~15 min)

Tre oppgaver på samme mønster. Skriv ned svaret ditt før du åpner løsningen —
det er selve poenget med et drillkapittel.

📝Oppgave 1

Eksamensnivå, sjanger C

Utfør Build-Max-Heap på arrayet [2, 9, 4, 16, 11, 6].

Oppgi arrayet etterpå. Oppgaven ber om output, ikke om en forklaring av
algoritmen.

📝Oppgave 2

Eksamensnivå, sjanger C

Utfør Build-Max-Heap på arrayet [5, 13, 2, 25, 7, 17, 20].

a) Oppgi arrayet etterpå.
b) Hvilket tall står på plass A[3] til slutt?

📝Oppgave 3

Eksamensnivå, sjanger C

Utfør Build-Max-Heap på arrayet [8, 3, 19, 6, 22, 11, 4, 14, 9].

a) Oppgi arrayet etterpå.
b) Hvor mange ganger kaller selve løkka i Build-Max-Heap på Max-Heapify?
Regn ikke med de rekursive kallene.

Drill: `Heap-Extract-Max`, også på ugyldig input (~15 min)

De to neste oppgavene ser like ut, men den ene gir deg et array som ikke er
en gyldig maks-haug. Det er en helt bevisst oppgavetype, og den er lett å bomme
på: du blir bedt om å utføre algoritmen, ikke om å fikse inputen.

📝Oppgave 4

Eksamensnivå, sjanger C

Arrayet [28, 19, 24, 12, 6, 21, 9] er en gyldig maks-haug med
A.heap-size = 7. Utfør Heap-Extract-Max én gang.

a) Hvilket tall returneres?
b) Oppgi haugen etterpå.

📝Oppgave 5

Eksamensnivå, sjanger C

Arrayet [6, 14, 2, 11, 5] er ikke en gyldig maks-haug. Utfør likevel
Heap-Extract-Max én gang ved å følge algoritmen mekanisk, med
A.heap-size = 5.

a) Hvilket tall returneres?
b) Oppgi haugen etterpå.

📝Oppgave 6

Eksamensnivå, sjanger C

Arrayet [7, 4, 18, 30, 2, 9] er ikke en gyldig maks-haug. Utfør
Heap-Extract-Max én gang, mekanisk, med A.heap-size = 6.

a) Oppgi returverdien og haugen etterpå.
b) Er resultatet en gyldig maks-haug? Svar ja eller nei, og begrunn med én
setning.

📝Oppgave 7

Eksamensnivå, sjanger C

Arrayet [33, 27, 18, 14, 26, 12, 9] er en gyldig maks-haug med
A.heap-size = 7. Utfør Heap-Extract-Max to ganger.

a) Hvilke to tall returneres, i rekkefølge?
b) Oppgi haugen etter den andre ekstraheringen.

Drill: én `Heapsort`-iterasjon (~10 min)

En Heapsort-iterasjon er tre trekk: bytt A[1] med det siste elementet i
haugen, krymp haugen med én, og kall Max-Heapify(A, 1). Legg merke til at
elementet som ble byttet ut, blir liggende i arrayet — det er ferdigsortert, men
det er fortsatt en del av svaret ditt.

📝Oppgave 8

Eksamensnivå, sjanger C

A = [26, 21, 17, 8, 13, 5, 11] er en gyldig maks-haug med A.heap-size = 7.
Utfør én iterasjon av Heapsort.

a) Oppgi hele arrayet etterpå.
b) Hva er A.heap-size etter iterasjonen?

📝Oppgave 9

Eksamensnivå, sjanger C

A = [31, 24, 18, 20, 7, 16, 3] er en gyldig maks-haug med A.heap-size = 7.
Utfør to iterasjoner av Heapsort.

a) Oppgi hele arrayet etter den andre iterasjonen.
b) Hvilke to tall er ferdigsortert, og hvor ligger de?

— naturlig pausepunkt —

Er du sliten nå, er dette et godt sted å stoppe. Haugdelen er ferdig. Resten av
kapitlet handler om søketrær, og den delen er kortere.

Drill: `Tree-Insert`, `Inorder-Tree-Walk` og `Tree-Maximum` (~15 min)

BST-håndkjøringen er den mekanisk enkleste sjangeren i faget, og den har et
innebygd kontrollmiddel: inorder-utskriften skal komme sortert. Får du noe
annet, har du gått feil vei et sted underveis. Bruk den kontrollen hver gang.

✏️Eksempel 2: Åtte innsettinger, med margnotater

En turistforening registrerer hyttenumre i den rekkefølgen hyttene blir bookinger
for sesongen:

$41,\ 17,\ 63,\ 9,\ 25,\ 55,\ 78,\ 30$

Sett dem inn i et tomt binært søketre i den rekkefølgen.

a) Oppgi Inorder-Tree-Walk-utskriften.
b) Hva returnerer Tree-Maximum, og hvilken vei går den?

Steg	Nøkkel	Søkevei fra rota	Resultat
1	41	treet er tomt	41 blir rot
2	17	17 < 41, gå til venstre	17 blir venstre barn av 41
3	63	63 > 41, gå til høyre	63 blir høyre barn av 41
4	9	9 < 41, gå til venstre ; 9 < 17, gå til venstre	9 blir venstre barn av 17
5	25	25 < 41, gå til venstre ; 25 > 17, gå til høyre	25 blir høyre barn av 17
6	55	55 > 41, gå til høyre ; 55 < 63, gå til venstre	55 blir venstre barn av 63
7	78	78 > 41, gå til høyre ; 78 > 63, gå til høyre	78 blir høyre barn av 63
8	30	30 < 41, gå til venstre ; 30 > 17, gå til høyre ; 30 > 25, gå til høyre	30 blir høyre barn av 25

Treet ser da slik ut:

                        41
                       /  \
      17                            63
     /  \                          /  \
9           25                55          78
              \
                  30

På eksamen leverer du bare linjene under — tavlen er her for å vise hvordan du
kommer dit.
Svar a): 9, 17, 25, 30, 41, 55, 63, 78
Svar b): Tree-Maximum returnerer 78, ved å følge høyre barn fra rota:
41, 63, 78.
Margnotat til steg 8. Nøkkelen 30 er den eneste som må tre nivåer ned. Legg
merke til at den ender som høyre barn av 25, ikke som venstre barn av 41 —

plassen bestemmes av hele søkeveien, ikke av det første valget.

Margnotat til svaret på a). Utskriften er sortert. Det er ikke en tilfeldighet

og heller ikke noe du trenger å bevise i svaret — det er kontrollen din. Men det
er også en felle: har du bare fått oppgitt tallene, kan du ikke bare sortere

dem og levere det som svar hvis oppgaven i tillegg spør om rota, høyden eller et

deltre. Da må treet faktisk bygges.
Margnotat til svaret på b). Oppgaven spurte om to ting: hva som returneres,

og hvilken vei algoritmen går. Veien er tre noder, ikke to.

📝Oppgave 10

Eksamensnivå, sjanger C

Sett inn nøklene 50, 22, 71, 14, 39, 65, 88 i denne rekkefølgen i et tomt
binært søketre.

a) Oppgi Inorder-Tree-Walk-utskriften.
b) Hva returnerer Tree-Maximum?

📝Oppgave 11

Eksamensnivå, sjanger C

Sett inn nøklene 33, 12, 47, 8, 19, 41, 60, 27 i denne rekkefølgen i et tomt
binært søketre.

a) Oppgi Inorder-Tree-Walk-utskriften.
b) Hva returnerer Tree-Minimum og Tree-Maximum?
c) Hva er høyden til treet?

📝Oppgave 12

Eksamensnivå, sjanger C

Sett inn nøklene 7, 15, 21, 34, 46 i denne rekkefølgen i et tomt binært
søketre.

a) Oppgi Inorder-Tree-Walk-utskriften.
b) Hva er høyden til treet?
c) Hvor mange sammenligninger gjør Tree-Insert når nøkkelen 46 settes inn?

📝Oppgave 13

Eksamensnivå, sjanger C

Sett inn nøklene 58, 24, 73, 11, 36, 66, 91, 49 i denne rekkefølgen i et tomt
binært søketre.

a) Tegn treet.
b) Oppgi Inorder-Tree-Walk-utskriften.
c) Hvilken node er forelder til 49?

Blandet: hvilken regel gjelder? (~5 min)

Siste oppgave blander de to strukturene. Den er kort, men den treffer nøyaktig
den forvekslingen som koster mest.

📝Oppgave 14

Eksamensnivå, sjanger C…

Arrayet [30, 12, 15, 4, 2, 9, 8] er resultatet av Build-Max-Heap på
[12, 4, 9, 30, 2, 15, 8].

a) Er [30, 12, 15, 4, 2, 9, 8] en gyldig maks-haug? Svar ja eller nei, og
begrunn med én setning.
b) Leser du det samme arrayet som et binært tre på vanlig måte — rot på
plass 1, barna til plass $i$ på plass $2i$ og $2i+1$ — er det da et gyldig binært
søketre? Svar ja eller nei, og begrunn med én setning.
c) Hva blir Inorder-Tree-Walk-utskriften av dette treet?

Typiske feil

De tre første er de dyreste, og alle tre er rene disiplinfeil.

- Å reparere en ugyldig haug før du utfører operasjonen. Felle #10. Ber
oppgaven om Heap-Extract-Max på et array som ikke oppfyller haugegenskapen,
skal du returnere A[1] som det står, flytte siste haugelement opp og kalle
Max-Heapify(A, 1). Kontrollen: har du kjørt Build-Max-Heap uten at oppgaven
ba om det? Da har du svart på noe annet.
- Å blande de to reglene. Felle #2. Haugen ordner oppover (forelder
$\ge$ begge barn, ingen orden mellom søsken), søketreet ordner sidelengs
(hele venstre deltre $\le$ noden $\le$ hele høyre deltre). Kontrollen for
søketreet: kommer inorder sortert? Kontrollen for haugen: står det største
tallet i A[1]?
- Å bytte med venstre barn i stedet for det største. Max-Heapify bytter med
det største av de to barna. Bytter du med venstre barn fordi det står
først, lager du et nytt brudd rett under deg — og det brer seg nedover i resten
av sporingen.

Og de fire som koster deler av poenget:

- Feil startindeks i Build-Max-Heap. Løkka starter på
$i = \lfloor n/2 \rfloor$ , ikke på $i = n$ og ikke på $i = 1$ .
- Å lese utenfor A.heap-size. Etter en Heap-Extract-Max eller en
Heapsort-iterasjon er haugen kortere enn arrayet. Max-Heapify sammenligner
bare med barn som ligger innenfor A.heap-size.
- Å levere treet i stedet for arrayet. Svarformatet for en haug-håndkjøring
er hele arrayet, kommaseparert, med indeks fra 1. Tegn treet gjerne — men skriv
arrayet under.
- Feil kjøretidsfakta i en deloppgave. Felle #9: Build-Max-Heap er
$\Theta(n)$ , ikke $\Theta(n\lg n)$ ; Max-Heapify og Heap-Extract-Max er
$O(\lg n)$ ; Heapsort er $\Theta(n\lg n)$ og ustabil;
Inorder-Tree-Walk er $\Theta(n)$ .

Den siste, og den enkleste å unngå: å svare på mer enn det som ble spurt om.
Ba oppgaven om arrayet, skriver du arrayet. Ba den om returverdien og arrayet,
skriver du begge. Ba den om utskriften, skriver du utskriften — ikke treet, ikke
en forklaring av Inorder-Tree-Walk.

Kjøretidene du kan bli spurt om i en deloppgave

Håndkjøringsoppgaver har ofte en kort deloppgave om kjøretid. Disse tallene skal
sitte hjelpemiddelfritt.

Operasjon	Beste	Verste	Egenskap / krav
`Max-Heapify`	$\Theta(1)$ (ingen bytter)	$O(\lg n)$	forutsetter at deltrærne under allerede er hauger
`Build-Max-Heap`	$\Theta(n)$	$\Theta(n)$	ikke $\Theta(n\lg n)$ — de fleste kallene skjer nede i treet
`Heap-Extract-Max`	$\Theta(1)$	$O(\lg n)$	forutsetter en gyldig maks-haug for at svaret skal være det største
`Heapsort`	$\Theta(n\lg n)$	$\Theta(n\lg n)$	på stedet, ustabil
`Tree-Insert`	$\Theta(1)$	$O(h)$ , altså $\Theta(n)$ i verste tilfelle	$\Theta(\lg n)$ forventet for et tilfeldig bygd tre
`Inorder-Tree-Walk`	$\Theta(n)$	$\Theta(n)$	gir sortert utskrift
`Tree-Minimum`, `Tree-Maximum`	$\Theta(1)$	$O(h)$	følger én sti, aldri forgrening

Én setning du bør kunne begrunne: Build-Max-Heap er

\Theta(n)

fordi
omtrent halvparten av nodene er blader som ikke synker i det hele tatt, og bare
én node kan synke

\lg n

nivåer — arbeidet er dominert av de mange billige
kallene, ikke av de få dyre.

Begrepsbank

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

Håndkjøring

å utføre en algoritme steg for steg på papir, med en gitt input, og oppgi tilstanden etterpå. Dette er en av oppgavesjangrene i faget, og den krever ingen forklaring — bare et korrekt resultat i riktig format. Verktøyet er en sporingstavle: én rad per steg, med strukturens tilstand etter hvert steg.

Svarformat for en maks-haug

hele arrayet, kommaseparert, med indeks fra 1 — for eksempel [15, 12, 9, 10, 4, 7, 3, 1] . Er haugstørrelsen endret underveis, oppgis den i tillegg. Et tegnet tre er et hjelpemiddel underveis, ikke svaret; delvis riktig array gir delvis uttelling, mens et tomt svarfelt ikke gir noe.

Svarformat for et binært søketre

Inorder-Tree-Walk -utskriften, som alltid kommer sortert, og eventuelt rotverdien når oppgaven ber om den. Utskriften er samtidig kontrollen din: kommer tallene ikke i stigende rekkefølge, har du satt inn feil vei et sted.

Svarformat for én `Heapsort`-iterasjon

hele arrayet etter iterasjonen, med haugstørrelsen oppgitt . Det ferdigsorterte elementet ligger igjen bakerst i arrayet og er en del av svaret. Den vanligste tabben er å kjøre hele sorteringen når bare én iterasjon var spurt.

Haugegenskapen (maks-haug)

A[\lfloor i/2 \rfloor] \ge A[i]

Søketreegenskapen

alt i venstre deltre er mindre enn eller lik noden, og alt i høyre deltre er større enn eller lik den — for hver node i treet. Kravet gjelder hele deltrær, ikke bare de to barna. Konsekvens: Inorder-Tree-Walk skriver ut nøklene sortert.

`Max-Heapify`

O(\lg n)

`Build-Max-Heap`

i = \lfloor n/2 \rfloor

`Heap-Extract-Max`

O(\lg n)

Mekanisk kjøring av ugyldig input

når en oppgave ber deg utføre en haugoperasjon på et array som bryter haugegenskapen, skal du følge algoritmens linjer nøyaktig og ikke reparere først. Dette er felle #10 i bokas feilregister. Å kjøre Build-Max-Heap først gir et annet — og galt — svar, både på returverdien og på sluttarrayet.

`Inorder-Tree-Walk`

\Theta(n)

`Tree-Minimum` og `Tree-Maximum`

O(h)

Repetisjonsoppgaver

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 Norges teknisk-naturvitenskapelige universitet. Dette er ikke offisielt studiemateriell. Les mer.

3.3 DRILL — Håndkjøring av hauger og BST

Forkunnskaper

Løsningsoppskriften — den du følger hver gang (~10 min)

De to reglene, ved siden av hverandre

Den gjennomarbeidede eksamenscasen (~15 min)

Drill: Build-Max-Heap (~15 min)

Drill: Heap-Extract-Max, også på ugyldig input (~15 min)

Drill: én Heapsort-iterasjon (~10 min)

Drill: Tree-Insert, Inorder-Tree-Walk og Tree-Maximum (~15 min)

Blandet: hvilken regel gjelder? (~5 min)

Kjøretidene du kan bli spurt om i en deloppgave

Begrepsbank

Drill: `Build-Max-Heap` (~15 min)

Drill: `Heap-Extract-Max`, også på ugyldig input (~15 min)

Drill: én `Heapsort`-iterasjon (~10 min)

Drill: `Tree-Insert`, `Inorder-Tree-Walk` og `Tree-Maximum` (~15 min)