3.2 Binære søketrær

`Tree-Insert`, `Inorder-Tree-Walk`, `Tree-Search`/`Minimum`/`Maximum` — inkludert nøkkelinnsikten at inorder på et BST gir **sortert** rekkefølge.

50 min

6 oppgaver

Binære søketrær

Din fremgang i kapitlet

0 / 6 oppgaver

Kapitlets plass i kurset

Bygger på

3.1Hauger og Heapsort

Brukes videre i

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

Binære søketrær og hauger er den sikreste håndkjøringskandidaten i faget.
Temaet er registrert i 16 av de 17 settene i grunnlaget (94 %). Grunnlaget
er de 17 settene fra august 2015 til august 2023 som er gjennomgått tema for
tema — det er nevneren hver gang boka oppgir en prosent.

To sjangre henter fra dette kapitlet:

- Sjanger C — håndkjøring, altså at du utfører algoritmen steg for steg på
papir og oppgir bare sluttilstanden. Den klassiske er: «sett inn disse
nøklene i denne rekkefølgen i et tomt søketre, og oppgi
Inorder-Tree-Walk-utskriften». Dette er den hyppigste håndkjøringen i hele
faget.
- Sjanger D — definisjon med egne ord, altså én presis setning med
hovedpoenget først. «Definér søketreegenskapen» kommer igjen og igjen.

Høyeste prioritet — dette må sitte. Eksamen er hjelpemiddelfri, og både
egenskapen og kjøretidene er ren gjenkalling.

Tre ting er verdt å merke seg med én gang:

1. Søketreegenskapen ordner venstre–høyre, haugegenskapen ordner opp–ned.
Å blande dem er fagets mest fremhevede datastrukturfeil, og den koster hele
oppgaven.
2. Inorder-Tree-Walk gir utskriften i sortert rekkefølge, ikke i
innsettingsrekkefølge. Det er både nøkkelinnsikten og en gratis kontroll på
at du har satt inn riktig.
3. Kjøretidene oppgis i høyden $h$ , ikke i $n$ . Tree-Insert er $O(h)$ , og
$h$ kan være alt fra $\lfloor\lg n\rfloor$ til $n-1$ .

Slik er kapitlet lagt opp (50 min):

Innhold	Tid
Søketreegenskapen, og kontrasten mot haugen	ca. 11 min
`Tree-Insert` og innsettingsveien	ca. 12 min
`Inorder-Tree-Walk` og de tre traverseringene	ca. 11 min
Søk, minimum og maksimum	ca. 8 min
Høyden — der kjøretiden avgjøres	ca. 8 min

Forkunnskaper

- kap. 3.1 — hauger. Dette sto der: en maks-haug
krever at hver forelder er $\ge$ begge barna, og den sier ingenting om
venstre mot høyre. Haugen ligger i et array A[1..n] med forelder
$\lfloor i/2\rfloor$ og barn $2i$ og $2i+1$ . Build-Max-Heap er $\Theta(n)$ ,
og Heapsort er $\Theta(n\lg n)$ . Søketreet i dette kapitlet ordner i den
andre retningen, og kontrasten er halve poenget med Del 3.
- kap. 2.1 — sortering. Vi bruker at et sortert
materiale kan søkes ved halvering, og sammenligner søketreets $O(h)$ med
sorteringens $\Theta(n\lg n)$ .
- kap. 1.1 — de asymptotiske symbolene. Skillet mellom
$O$ og $\Theta$ er bevisst brukt i hele kapitlet: operasjonene er $O(h)$ ,
ikke $\Theta(h)$ , fordi de kan stoppe tidlig.

Er logaritmen fersk: Potenser og logaritmer. I hele denne boka
betyr $\lg n$ det samme som $\log_2 n$ .

Notasjons- og pseudokodeliste

Søketreegenskapen, og kontrasten mot haugen (~11 min)

Et bibliotek har et kortregister der hvert kort peker videre til to andre kort:
ett for «lavere nummer» og ett for «høyere nummer». Leter du etter et bestemt
nummer, sammenligner du med kortet du står på og går én vei. Du slipper å lete
gjennom resten.

Det er et binært søketre. Strukturen er den samme som haugen — noder med to
barn hver — men regelen som ordner nodene er en helt annen.

Søketreegenskapen

\le

Kontrasten: haugegenskapen

\ge

Høyden

h

O(h)

📝Oppgave 1

(Innstegsoppgave, sjanger D — definisjon med egne ord, altså én presis setning
med hovedpoenget først.)

Definér søketreegenskapen, og si med én setning hva som skiller den fra
haugegenskapen.

Typiske feil ved søketreegenskapen

- Å forveksle søketreegenskapen med haugegenskapen. Dette er felle #2
— å blande de to strukturene. En haug ordner opp–ned; et søketre ordner
venstre–høyre. Kontrollen: kjør Inorder-Tree-Walk i hodet. Kommer nøklene
ut sortert, er det et søketre.
- Å bare sjekke de nærmeste barna. Egenskapen gjelder hele deltreet. Et tre
der rota er 46, venstre barn er 25 og 25 sitt høyre barn er 50, bryter
egenskapen — 50 ligger i rotas venstre deltre og er større enn 46 — selv om
hver enkelt forelder–barn-relasjon ser riktig ut.
- Å anta at treet er balansert. Ingenting i egenskapen krever det, og
høyden kan bli $n-1$ .

`Tree-Insert` og innsettingsveien (~12 min)

Innsetting er den enkleste operasjonen, og den som oftest håndkjøres. Ideen er
at den nye nøkkelen skal ende opp nøyaktig der et søk etter den ville stoppet.

📜Pseudokode-kontrakt: `Tree-Insert`

Antagelser om representasjon. Hver node x har feltene x.key, x.left,
x.right og x.p. Manglende barn og manglende forelder er NIL. Treet T
har T.root. Noden z som settes inn, har z.left = z.right = NIL.

Prebetingelse: T oppfyller søketreegenskapen.
Postbetingelse: T inneholder z i tillegg til de gamle nøklene, og
oppfyller fortsatt søketreegenskapen. z er et blad.

Tree-Insert(T, z)
  Input:  soeketreet T og en ny node z med noekkel z.key
  Output: T med z satt inn som blad
  y = NIL
  x = T.root
  while x != NIL
      y = x
      if z.key < x.key
          x = x.left
      else
          x = x.right
  z.p = y
  if y == NIL
      T.root = z
  else if z.key < y.key
      y.left = z
  else
      y.right = z
  Kjoeretid: O(h)

Invarianten i én setning: hvis z.key skal inn i treet, ligger den
riktige plassen i deltreet med rot x — og y er alltid forelderen til x.

Legg merke til at ingen eksisterende node flyttes. Innsettingen henger bare
på et nytt blad. Det er derfor et søketre bygget ved gjentatte innsettinger kan
bli skjevt: strukturen bestemmes helt av rekkefølgen nøklene kommer i.

Kjøretid: $O(h)$ — løkka følger én sti fra rota og nedover, og gjør
konstant arbeid per nivå. Grensen er $O$ og ikke $\Theta$ fordi stien kan være
kort.

✏️Eksempel 1: Åtte innsettinger, og veien hver nøkkel tar

Åtte medlemsnumre registreres i denne rekkefølgen: `46, 25, 68, 13, 31, 57,
79, og til slutt 29`.

Sett dem inn i et tomt binært søketre med Tree-Insert, og oppgi
Inorder-Tree-Walk-utskriften til slutt.

Nøkkel	Sammenligninger på veien ned	Havner som
46	—	rot
25	$25 < 46$ , gå venstre	venstre barn av 46
68	$68 > 46$ , gå høyre	høyre barn av 46
13	$13 < 46$ , gå venstre; $13 < 25$ , gå venstre	venstre barn av 25
31	$31 < 46$ , gå venstre; $31 > 25$ , gå høyre	høyre barn av 25
57	$57 > 46$ , gå høyre; $57 < 68$ , gå venstre	venstre barn av 68
79	$79 > 46$ , gå høyre; $79 > 68$ , gå høyre	høyre barn av 68
29	$29 < 46$ , gå venstre; $29 > 25$ , gå høyre; $29 < 31$ , gå venstre	venstre barn av 31

Treet ser slik ut etterpå:

                  46
          25              68
      13      31      57      79
            29

Sluttilstanden — det du ville levert på eksamen:
13, 25, 29, 31, 46, 57, 68, 79
Kontrollen er gratis. Inorder-utskriften skal være sortert. Er den ikke
det, har du satt inn feil et sted — og du finner feilen ved å gå tilbake til
den første nøkkelen som kommer ut av rekkefølge.
Legg merke til veien 29 tok. Den gikk til venstre fra 46, til høyre fra 25,
og til venstre fra 31. Tre sammenligninger, og så et ledig sted. Det er alltid

slik: nøkkelen ender der søket etter den ville stoppet.

Høyden til treet er 3 — den lengste stien er

46–25–31–29.

📝Oppgave 2

Eksamensnivå, sjanger C

Sett inn nøklene 40, 62, 18, 55, 71, 9, 27 i denne rekkefølgen i et tomt
binært søketre.

a) Oppgi Inorder-Tree-Walk-utskriften.
b) Hva er rotas nøkkel, og hva er treets høyde?

`Inorder-Tree-Walk` og de tre traverseringene (~11 min)

Traverseringen er der søketreets viktigste egenskap kommer til syne.

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

Antagelser om representasjon. Som over: x.key, x.left, x.right, med
NIL for manglende barn. Kallet utenfra er
Inorder-Tree-Walk(T.root).

Prebetingelse: deltreet med rot x oppfyller søketreegenskapen.
Postbetingelse: alle nøkler i deltreet er skrevet ut, i stigende
rekkefølge.

Inorder-Tree-Walk(x)
  Input:  rota x i et deltre
  Output: alle noekler i deltreet, skrevet ut sortert
  if x != NIL
      Inorder-Tree-Walk(x.left)
      skriv ut x.key
      Inorder-Tree-Walk(x.right)
  Kjoeretid: Theta(n)

Grunnideen i én setning: søketreegenskapen sier at alt i venstre deltre er
$\le$ x.key og alt i høyre deltre er $\ge$ x.key — så skriver du ut venstre
først, deretter x selv, deretter høyre, kommer nøklene ut i orden.

Kjøretid: $\Theta(n)$ . Hver node besøkes nøyaktig én gang, og arbeidet per
node er konstant. Her er grensen tett: ingen input gjør traverseringen
kortere, siden alle nodene skal skrives ut.

De to søsknene følger samme mønster, men med utskriften plassert et annet
sted: preorder skriver x før deltrærne, og postorder skriver x
etter dem. Ingen av dem gir sortert utskrift.

✏️Eksempel 2: De tre traverseringene på samme tre

Bruk treet fra Eksempel 1 — det med rota 46 og nøklene `13, 25, 29, 31, 46,
57, 68, 79`.

Oppgi utskriften fra Inorder-Tree-Walk, fra preorder og fra postorder, og si
hva hver av dem er nyttig til.

Traversering	Utskrift
inorder (venstre, node, høyre)	`13, 25, 29, 31, 46, 57, 68, 79`
preorder (node, venstre, høyre)	`46, 25, 13, 31, 29, 68, 57, 79`
postorder (venstre, høyre, node)	`13, 29, 31, 25, 57, 79, 68, 46`

Inorder gir sortert rekkefølge. Det er den ene av de tre som utnytter
søketreegenskapen, og den eneste som er interessant på eksamen.
Preorder starter i rota og tar venstre deltre ferdig før høyre. Den er
nyttig til å skrive ned et tre slik at det kan bygges opp igjen med nøyaktig

samme form — legg merke til at preorder-listen begynner med 46, som er rota.
Postorder besøker begge barna før noden selv. Den passer når noe skal

gjøres nedenfra og opp, for eksempel å frigjøre minne.
Fellen: inorder gir ikke innsettingsrekkefølgen. Innsettingsrekkefølgen
i Eksempel 1 var 46, 25, 68, 13, 31, 57, 79, 29, og den ser du ikke igjen i

noen av de tre listene. Preorder er nærmest, men er ikke den samme: den ville
gitt 46, 25, 13, 31, 29, 68, 57, 79.

📝Oppgave 3

Eksamensnivå, sjanger F

Ta stilling til hver av påstandene:

a) Inorder-Tree-Walk skriver ut nøklene i den rekkefølgen de ble satt
inn.
b) To ulike søketrær over de samme nøklene gir samme inorder-utskrift.
c) Inorder-Tree-Walk er $O(h)$ .

Søk, minimum og maksimum (~8 min)

De tre siste operasjonene er varianter av det samme: følg én sti nedover.

📜Pseudokode-kontrakt: `Tree-Search`, `Tree-Minimum` og `Tree-Maximum`

Antagelser om representasjon. Som over. Alle tre kalles med rota i det
deltreet det skal letes i.

Prebetingelse: deltreet oppfyller søketreegenskapen; for Tree-Minimum og
Tree-Maximum må det være ikke-tomt.
Postbetingelse: Tree-Search returnerer noden med nøkkelen v hvis den
finnes, ellers NIL. Tree-Minimum returnerer noden med den minste nøkkelen,
Tree-Maximum den med den største.

Tree-Search(x, v)
  Input:  rota x i et deltre og en noekkel v
  Output: noden med noekkel v, eller NIL
  while x != NIL and v != x.key
      if v < x.key
          x = x.left
      else
          x = x.right
  return x

Tree-Minimum(x)
  while x.left != NIL
      x = x.left
  return x

Tree-Maximum(x)
  while x.right != NIL
      x = x.right
  return x
  Kjoeretid: O(h) for alle tre

Grunnideen i én setning: søketreegenskapen gjør at hver sammenligning
utelukker et helt deltre — og at det minste elementet ligger så langt til
venstre som det er mulig å komme.

Kjøretid: $O(h)$ for alle tre. Hver runde går ett nivå ned, og det finnes
$h$ nivåer.

Kontrasten mot maks-haugen er verdt å merke seg. I en maks-haug ligger
maksimum alltid på A[1] og koster $\Theta(1)$ å finne, mens minimum
krever at du leter gjennom alle bladene, altså $\Theta(n)$ . I et søketre
koster begge $O(h)$ — strukturen er mer symmetrisk.

📝Oppgave 4

Eksamensnivå, sjanger C…

Bruk treet fra Eksempel 1 (rota 46, nøklene 13, 25, 29, 31, 46, 57, 68, 79).

a) Hvilke noder besøker Tree-Search når den leter etter 57?
b) Hva returnerer Tree-Minimum(T.root) og Tree-Maximum(T.root)?
c) Hva er kjøretiden til et søk, uttrykt i høyden?

Høyden — der kjøretiden avgjøres (~8 min)

Alle kjøretidene over er $O(h)$ . Det er et ærlig svar, men det utsetter
spørsmålet: hvor stor er $h$ ?

Svaret avhenger fullstendig av rekkefølgen nøklene ble satt inn i, og det er
her et søketre kan gå fullstendig galt.

Høydens ytterpunkter

n

Forventet høyde for et tilfeldig bygd tre

n

✏️Eksempel 3: Samme nøkler, to helt ulike trær

Seks lagernumre skal inn i et søketre: 8, 15, 23, 34, 42, 56.

a) Hva blir treets høyde hvis de settes inn i denne rekkefølgen?
b) Finn en innsettingsrekkefølge som gir så lav høyde som mulig, og oppgi
høyden.
c) Hva er inorder-utskriften i de to tilfellene?

a) Nøklene kommer i stigende rekkefølge, så hver eneste innsetting går til
høyre. Treet blir en kjede:

Høyden er 5, altså $n-1$ . Et søk etter 56 må
gjennom alle seks nodene.

b) Sett inn medianen først, deretter medianene i hver halvdel:
34, 15, 56, 8, 23, 42.

              34
        15          56
      8    23     42

Høyden er 2, altså $\lfloor\lg 6\rfloor = 2$ — så lavt det går med seks noder.

c) Den samme i begge tilfeller: 8, 15, 23, 34, 42, 56.

Det er hele poenget. Inorder-utskriften avhenger bare av hvilke nøkler
treet inneholder, ikke av hvordan de ligger. Formen påvirker kjøretiden,
ikke innholdet.

Svarformen på eksamen: høyden er ett tall, utskriften er én linje. Ikke
tegn treet med mindre oppgaven ber om det.

📝Oppgave 5

Eksamensnivå, sjanger F

En kandidat skriver i besvarelsen sin: «Søk i et binært søketre er
$\Theta(\lg n)$ , siden treet halverer søkeområdet i hvert steg.»

Er utsagnet riktig? Svar ja eller nei, og gi et konkret motbevis.

📝Oppgave 6

Eksamensnivå, sjanger H

Du får $n$ forskjellige heltall i vilkårlig rekkefølge og skal skrive dem ut
sortert.

a) Beskriv en løsning som bygger et binært søketre.
b) Hva er kjøretiden i beste og verste tilfelle, og hvorfor er dette et
dårligere valg enn Merge-Sort?

Typiske feil

De to første koster hele oppgaven.

- Å forveksle søketreegenskapen med haugegenskapen. Dette er felle #2 —
å blande de to strukturene. Kontrollen er å kjøre Inorder-Tree-Walk i
hodet: kommer nøklene ut sortert, er det et søketre.
- Å tro at inorder gir innsettingsrekkefølgen. Den gir sortert
rekkefølge. Innsettingsrekkefølgen finnes ikke lagret noe sted i treet.
- Å gå til feil side under innsetting. Mindre går til venstre, større til
høyre — og sammenligningen gjøres mot den noden du står i, ikke mot rota.
- Å svare $\Theta(\lg n)$ på et spørsmål om verste tilfelle.
$\Theta(\lg n)$ er den forventede høyden for et tilfeldig bygd tre. Verste
tilfelle er $\Theta(n)$ , og det inntreffer på sortert input.
- Å oppgi $\Theta(h)$ der operasjonen er $O(h)$ . Et søk kan stoppe i rota;
grensen er derfor bare øvre.
- Å oppgi Inorder-Tree-Walk som $O(h)$ . Den er $\Theta(n)$ — hver node
skrives ut.
- Å bare sjekke nærmeste barn når du skal avgjøre om et tre er et søketre.
Egenskapen gjelder hele deltreet.

Og den gjennomgående: å levere treet når oppgaven ba om utskriften.
Svarformatet for en søketre-håndkjøring er Inorder-Tree-Walk-linja, eventuelt
med rotverdien hvis den er spurt om.

Kjøretidene samlet

Dette er kapitlets puggeflate. Eksamen er hjelpemiddelfri, så tabellen må ligge
i hodet.

Operasjon	Kjøretid	Krav / egenskap
`Tree-Insert`	$O(h)$	ny node blir alltid et blad; ingen eksisterende node flyttes
`Tree-Search`	$O(h)$	hver sammenligning utelukker ett helt deltre
`Tree-Minimum`	$O(h)$	følg `left` så langt det går
`Tree-Maximum`	$O(h)$	følg `right` så langt det går
`Inorder-Tree-Walk`	$\Theta(n)$	gir sortert utskrift; tett grense, alle noder besøkes
Preorder- og postorder-traversering	$\Theta(n)$	gir ikke sortert utskrift
Høyden $h$	$\Theta(\lg n)$ forventet, $\Theta(n)$ verste	verste tilfelle på sortert input
Sortering via søketre	$\Theta(n\lg n)$ beste, $\Theta(n^2)$ verste	dårligere enn `Merge-Sort`, som garanterer

Én presisering som er verdt å ta med seg. Alle

O(h)

-operasjonene er

\Theta(n)

i verste tilfelle, siden

h

kan bli

n-1

. Skriver du bare
«

O(\lg n)

» om et søketre uten å nevne balansen, har du lovet noe strukturen
ikke garanterer.
Kontrasten mot maks-haugen fra kap. 3.1:

Maks-haug	Binært søketre
Ordner	opp–ned: forelder $\ge$ begge barn	venstre–høyre: venstre $\le$ rot $\le$ høyre
Finne maksimum	$\Theta(1)$ — ligger på `A[1]`	$O(h)$ — helt til høyre
Finne minimum	$\Theta(n)$ — må lete i alle bladene	$O(h)$ — helt til venstre
Sortert utskrift	krever `Heapsort`, $\Theta(n\lg n)$	`Inorder-Tree-Walk`, $\Theta(n)$
Form	alltid nesten komplett	kan bli en lenket liste

Begrepsbank

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

Binært søketre

O(h)

Søketreegenskapen

\le

`Tree-Insert`

O(h)

`Inorder-Tree-Walk`

\Theta(n)

Preorder-traversering

\Theta(n)

Postorder-traversering

\Theta(n)

`Tree-Search`

O(h)

`Tree-Minimum` og `Tree-Maximum`

O(h)

Høyden

h

\lfloor\lg n\rfloor \le h \le n-1

Degenerert søketre

n-1

Forventet høyde

\Theta(\lg n)

Felle #2 — søketre mot haug

\le

Blad

en node uten barn. Nye nøkler settes alltid inn som blader, og det er blader som ligger dypest i treet. Høyden er avstanden til det dypeste bladet, målt i antall kanter.

Svarformat for en søketre-håndkjøring

oppgi Inorder-Tree-Walk -utskriften, og rotverdien hvis den er spurt om. Tegn treet bare når oppgaven ber om det. Kontrollen før du leverer: er utskriften sortert, og inneholder den nøyaktig de nøklene som ble satt inn?

Sjanger C — håndkjøring

oppgavetypen der du utfører en navngitt algoritme steg for steg og oppgir sluttilstanden. Søketrær og hauger er de to hyppigste strukturene: temaet er registrert i 16 av de 17 settene i grunnlaget. Svarformen er kun sluttilstanden. En forklaring av algoritmen gir ingen ekstra uttelling.

Sjanger D — definisjon med egne ord

oppgavetypen der du skal forklare et begrep presist og kort. Svarformen er én til to setninger med hovedpoenget først . «Definér søketreegenskapen» er den hyppigste definisjonsoppgaven i Del 3.

Sjanger F — «stemmer dette?»

oppgavetypen der du får en påstand og skal ta stilling til den. Svarformen er ja eller nei først, deretter én presis setning. Et konkret motbevis holder når svaret er nei — ett tre der påstanden svikter.

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.