4.1 Binære søketrær (BST)

BST-egenskapen, innsetting og traversering — inkludert at in-order på et BST gir **sortert** rekkefølge.

50 min

8 oppgaver

Binære søketrær (BST)

Din fremgang i kapitlet

0 / 8 oppgaver

Kapitlets plass i kurset

Bygger på

2.1Sammenligningsbaserte sorteringer og invarianter

Brukes videre i

4.2Tre-algoritmer i pseudokode — beskjæring og lineær rekursjon 4.3Balanserte trær — AVL og rød-svart

Binære søketrær har vært på 6 av 7 sett i arkivet (86 %), og de dukker opp
på to steder i eksamenssettet:

- Sjanger E — håndkjøring av datastruktur, altså at du utfører operasjonen
steg for steg og oppgir kun sluttilstanden. Du får en rekke tall, setter
dem inn i et tomt tre, og leverer in-order-utskriften eller rotverdien.
Dette er Del 1, den auto-rettede delen av settet.
- Sjanger G — tre-algoritmer i pseudokode, altså at du skriver algoritmen
selv og oppgir kjøretiden. Den hører hjemme på Del 2, der karakteren
avgjøres, og den bygger helt og holdent på det du lærer her. Selve
skrivetreningen får du i kap. 4.2.

Kapitlet her er grunnmuren for begge. Prioritet: høyeste — sammen med
heap i kap. 4.4 er dette den sikreste
håndkjøringskandidaten i hele faget.

Og så den ene forvekslingen som koster flest poeng i Del 4: et søketre
sorterer venstre mot høyre, mens en heap sorterer oppover og nedover.
De to strukturene ser like ut på papiret og oppfører seg helt forskjellig.
Boka kaller den forvekslingen felle #9, og den kommer igjen i hvert
kapittel i denne delen.

Slik er kapitlet lagt opp (50 min): fire løkker med tidsanslag —
innsetting, traversering, søk og høyde, og til slutt sletting med de tre
tilfellene. Det er pausepunkter underveis.

Forkunnskaper

- kap. 2.1 — hva «sortert rekkefølge» betyr presist, og
invariant-tenkningen. Hele poenget med et søketre er at det holder på en
ordning uten å sortere noe på nytt.
- kap. 1.1 — O-notasjonen. Alle kjøretidene her er
$O(h)$ , der $h$ er høyden på treet, og hele kapitlet handler til slutt om
hvor stor $h$ kan bli.

Er det lenge siden du har tenkt på objekter med felter som peker videre til
andre objekter:

- Klasser og objekter: class, __init__ og self — en
node i et tre er nettopp et objekt med tre felter: en verdi og to pekere.

Notasjons- og pseudokodeliste

Løkke 1 — registeret som holder seg ordnet av seg selv (ca. 12 min)

En kommune har vannmålere ute hos abonnentene, og hver måler har et nummer.
Registeret må klare to ting samtidig: finne én bestemt måler raskt, og kunne
skrive ut alle målerne i stigende nummerrekkefølge når årsavregningen
kjøres. Nye målere settes inn hele tiden.

Du har to kjente løsninger, og begge svikter på hver sin halvdel:

- Et sortert array. Søk går raskt, fordi du kan halvere deg fram. Men å
sette inn en ny måler midt i betyr å flytte alt bak den ett hakk — $O(n)$
arbeid per innsetting.
- En usortert lenket liste. Innsetting er billig, men å finne én måler
krever at du går gjennom alt, og en sortert utskrift krever at du sorterer
først.

Det binære søketreet gir deg begge deler. Det er bygget av noder med en verdi
og to pekere, og den ene regelen som styrer alt, er hvor en verdi får lov til
å ligge i forhold til noden over.

Binært søketre (BST)

O(h)

BST-egenskapen

For hver node v i treet gjelder: alle verdier i venstre subtre er mindre enn v.x, og alle verdier i høyre subtre er større enn v.x . Merk ordet alle . Kravet gjelder ikke bare barna, men hele subtreet under dem — det er den presiseringen checkBST i kap. 4.2 handler om. Egenskapen er en venstre-høyre -ordning, i motsetning til heap-egenskapen i kap. 4.4, som er en opp-ned -ordning uten noen ordning mellom søsken. Å blande de to er felle #9 i bokas feilregister, og den fella er den vanligste i hele Del 4.

Noderepresentasjon i et binærtre

Hver node er et objekt med tre felter: verdien v.x og pekerne v.left og v.right . Mangler et barn, er pekeren nil . Et tomt tre er nil . På eksamen oppgir du selv hva du antar om representasjonen, og sensor binder seg ikke til én form. Du kan trygt anta at noden har de feltene du trenger — også v.parent hvis algoritmen din skal gå oppover — så lenge du sier det i besvarelsen.

📜Pseudokode-kontrakt: `Insert`

Antagelser om representasjon. Treet er bygget av noder med feltene v.x,
v.left og v.right; et tomt tre er nil. Verdiene kan sammenlignes med <
og >, og vi tillater ikke duplikater.

Prebetingelse: treet oppfyller BST-egenskapen.
Postbetingelse: treet oppfyller fortsatt BST-egenskapen, og x finnes i
det nøyaktig én gang.

Procedure Insert(v, x)
  Input:  rota v i et BST (nil hvis treet er tomt), verdien x
  Output: rota i treet etter at x er satt inn
  if v er nil:
      return NyNode(x)
  if x < v.x:
      v.left = Insert(v.left, x)
  else if x > v.x:
      v.right = Insert(v.right, x)
  return v

Grunnideen i én setning: en ny verdi legges nøyaktig der søket etter den
ville endt — på den første ledige plassen søkeveien peker mot — og derfor er
den fortsatt til å finne igjen med samme sammenligninger.

Legg merke til at else if x > v.x gjør at en verdi som allerede finnes,
ikke settes inn på nytt: begge betingelsene er usanne, og prosedyren
returnerer noden uendret.

Kjøretid: $O(h)$ . Hver rekursjon går ett nivå ned, og arbeidet på hvert
nivå er én sammenligning, så antall steg er høyden på treet. I et balansert
tre er det $O(\log n)$ ; i et degenerert tre er det $O(n)$ . Det er derfor
kjøretiden skrives $O(h)$ og ikke $O(\log n)$ — hvilken av dem du faktisk får,
avhenger av formen på treet.

✏️Eksempel 1: Innsetting i et tomt tre

Sett inn 50, 30, 70, 20, 40, 60 og 80 i denne rekkefølgen i et tomt binært
søketre. Tegn treet, og oppgi rotverdien og in-order-utskriften.

Hver innsetting starter i rota og går én vei nedover. Sammenligningene er hele
arbeidet:

Steg	Nøkkel	Sammenligninger fra rota	Plassering
1	50	treet er tomt	ny rot
2	30	`30 < 50 -> venstre`	venstre barn av 50
3	70	`70 > 50 -> høyre`	høyre barn av 50
4	20	`20 < 50 -> venstre; 20 < 30 -> venstre`	venstre barn av 30
5	40	`40 < 50 -> venstre; 40 > 30 -> høyre`	høyre barn av 30
6	60	`60 > 50 -> høyre; 60 < 70 -> venstre`	venstre barn av 70
7	80	`80 > 50 -> høyre; 80 > 70 -> høyre`	høyre barn av 70

Treet til slutt:

                    50
         __________/ \__________
        30                      70
   ____/ \____             ____/ \____
  20          40          60          80

- rotverdi: 50
- in-order (SORTERT): 20, 30, 40, 50, 60, 70, 80
- høyde (kanter): 2 antall noder: 7
Sluttilstanden du leverer er in-order-utskriften og rotverdien — det er
det sensor ber om, og det er nok til å avgjøre at treet ditt er riktig.
Legg merke til at innsettingsrekkefølgen ikke kan leses ut av utskriften.

In-order gir 20, 30, 40, 50, 60, 70, 80, mens vi satte inn 50 først. De to

listene har ingenting med hverandre å gjøre utover at de inneholder de samme

tallene.
Fellenote. Fella her er felle #9 — å lese treet som en heap. Hadde
dette vært en min-heap, ville kravet vært at forelderen er mindre enn begge

barna, uten noe krav om at 30 skal ligge til venstre for 70. I et søketre er
det motsatt: siden er alt.

📝Oppgave 1

(Innstegsoppgave, sjanger E — håndkjøring, altså at du utfører operasjonen
steg for steg og oppgir sluttilstanden.) Sett inn 6, 2, 8, 1, 4 og 7 i denne
rekkefølgen i et tomt binært søketre.

a) Hvor havner 4, og hvilke sammenligninger tok deg dit?
b) Oppgi rotverdien og in-order-utskriften.

Løkke 2 — traversering, og hvorfor in-order er sortert (ca. 10 min)

Å traversere et tre er å besøke hver node nøyaktig én gang. Rekkefølgen
bestemmes av når du behandler noden selv i forhold til de to subtrærne:

- in-order: venstre subtre, så noden, så høyre subtre
- pre-order: noden, så venstre subtre, så høyre subtre
- post-order: venstre subtre, så høyre subtre, så noden

Alle tre koster $O(n)$ , fordi hver node behandles én gang og arbeidet per node
er konstant. Det er den ene av dem som er interessant her: på et søketre gir
in-order verdiene i stigende rekkefølge. Ikke tilfeldigvis, men fordi
BST-egenskapen sier at alt til venstre er mindre og alt til høyre er større.
Skriver du ut i den rekkefølgen, skriver du ut i sortert rekkefølge.

Denne ene setningen er verdt mer enn den ser ut til. Den er grunnen til at
intervall-utskrift kan beskjæres i kap. 4.2, og den er
en av to måter å sjekke om et tre i det hele tatt er et gyldig søketre.

📜Pseudokode-kontrakt: `InOrder`

Antagelser om representasjon. Samme som for Insert: noder med v.x,
v.left, v.right, og nil for tomt subtre.

Prebetingelse: treet oppfyller BST-egenskapen.
Postbetingelse: alle $n$ verdiene er skrevet ut, i stigende rekkefølge, og
treet er uendret.

Procedure InOrder(v)
  Input:  rota v i et BST (nil hvis treet er tomt)
  Output: alle verdiene i subtreet skrevet ut i stigende rekkefoelge
  if v er nil:
      return
  InOrder(v.left)
  skriv ut v.x
  InOrder(v.right)

Invarianten i én setning: når kallet på en node er ferdig, er nøyaktig de
verdiene som ligger i subtreet under noden skrevet ut, og de er skrevet ut i
stigende rekkefølge.

Bytter du om på de tre linjene, får du de to andre traverseringene:
skriv ut først gir pre-order, skriv ut sist gir post-order. Bare in-order
gir sortert utskrift, og bare på et gyldig søketre.

Kjøretid: $O(n)$ , der $n$ er antall noder. Hver node får nøyaktig ett
kall, og arbeidet i kallet er konstant utenom rekursjonen — så antall steg er
proporsjonalt med antall noder. Merk at $h$ ikke er med i uttrykket i det hele
tatt: en traversering må uansett innom alt.

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

Et binært søketre er bygget ved å sette inn 15, 9, 20, 6, 12, 17, 25, 3, 8 og
11 i denne rekkefølgen. Oppgi in-order-, pre-order- og post-order-utskriften,
og forklar hva hver av dem forteller deg om treet.

Treet:

                                      15
                     ________________/ \__________
                    9                             20
         __________/ \__________             ____/ \____
        6                       12          17          25
   ____/ \____             ____/
  3           8           11

- rotverdi: 15
- in-order (SORTERT): 3, 6, 8, 9, 11, 12, 15, 17, 20, 25
- pre-order: 15, 9, 6, 3, 8, 12, 11, 20, 17, 25
- post-order: 3, 8, 6, 11, 12, 9, 17, 25, 20, 15
- høyde (kanter): 3 antall noder: 10

Hva de tre utskriftene forteller:

In-order er de ti verdiene i stigende rekkefølge. Den sier ingenting om
formen på treet — et helt annet søketre med de samme ti tallene ville gitt
nøyaktig samme in-order-utskrift.

Pre-order starter med 15, som er rota. Det er ingen tilfeldighet:
pre-order skriver alltid ut noden før subtrærne, så det første tallet er
alltid rotverdien. Denne utskriften bestemmer faktisk treet entydig, fordi du
kan lese den som en innsettingsrekkefølge.

Post-order slutter med 15. Noden skrives ut sist, så det siste tallet er
alltid rota. Post-order er rekkefølgen du trenger når arbeidet i en node
avhenger av svarene fra begge barna — akkurat slik diameter-algoritmen i
kap. 4.2 fungerer.

Kontrollen som tar fem sekunder: in-order-utskriften skal være sortert.
Er den ikke det, har du enten satt inn feil eller tegnet treet feil, og du vet
det før du leverer.

Fellenote. Fella her er å tro at in-order gir innsettingsrekkefølgen. Det
gjør pre-order — in-order gir den sorterte rekkefølgen, uansett hvilken
rekkefølge tallene kom inn i.

📝Oppgave 2

Sjanger E

Sett inn 12, 5, 18, 3, 9, 15 og 21 i denne rekkefølgen i et tomt
binært søketre.

a) Oppgi in-order- og pre-order-utskriften.
b) Hva er høyden på treet, målt i kanter?
c) Hvilken av de to utskriftene ville en medstudent kunne bruke til å
gjenskape nøyaktig dette treet?

Løkke 3 — søk, ytterpunktene, og høyden som avgjør alt (ca. 13 min)

— naturlig pausepunkt —

Søk i et søketre er den samme bevegelsen som innsetting, bare uten å legge
igjen noe: start i rota, sammenlign, gå én vei. Er verdien mindre enn noden,
kan den bare ligge til venstre — hele høyre subtre er utelukket i ett steg.

De to ytterpunktene faller ut gratis av den samme regelen. Den minste
verdien ligger så langt til venstre som det går an å komme, og den største
så langt til høyre. Ingen av dem trenger å ligge nederst i treet, og ingen av
dem har noe med rota å gjøre.

Alle tre operasjonene koster $O(h)$ . Og da er spørsmålet: hvor stor er $h$ ?

📜Pseudokode-kontrakt: `Search`

Antagelser om representasjon. Noder med v.x, v.left, v.right; nil
for tomt subtre. Verdiene kan sammenlignes.

Prebetingelse: treet oppfyller BST-egenskapen.
Postbetingelse: returverdien er sant hvis og bare hvis x finnes i
treet; treet er uendret.

Procedure Search(v, x)
  Input:  rota v i et BST, verdien x det soekes etter
  Output: sant hvis x finnes i treet, ellers usant
  while v er ikke nil:
      if x er lik v.x:
          return sant
      if x < v.x:
          v = v.left
      else:
          v = v.right
  return usant

Grunnideen i én setning: hver sammenligning utelukker et helt subtre, så
søket følger én sti nedover og trenger aldri å gå tilbake.

Her er løkkeformen skrevet ut, men den rekursive varianten er like god og gir
samme uttelling — rekursjon er pensum i dette faget og brukes fritt.

Kjøretid: $O(h)$ . Løkka gjør ett steg per nivå og går aldri oppover igjen,
så antall sammenligninger er høyst høyden pluss én. Verste tilfelle for et
degenerert tre er $O(n)$ — se eksempel 3.

📜Pseudokode-kontrakt: `Min` og `Maks`

Antagelser om representasjon. Som over, og treet er ikke tomt.

Prebetingelse: v er rota i et ikke-tomt BST.
Postbetingelse: returverdien er den minste (henholdsvis største) verdien i
treet; treet er uendret.

Procedure Min(v)
  Input:  rota v i et ikke-tomt BST
  Output: den minste verdien i treet
  while v.left er ikke nil:
      v = v.left
  return v.x

Maks er den samme prosedyren med v.right i stedet for v.left.

Invarianten i én setning: noden du står på er alltid den minste i det
subtreet du har igjen, og du stopper når det ikke finnes noe mindre til
venstre.

Kjøretid: $O(h)$ — løkka går rett nedover langs venstrekanten og stopper
senest i en bladnode. Merk at den minste verdien ikke nødvendigvis er en
bladnode: den kan ha et høyre barn. Den har bare ikke noe venstre barn.

✏️Eksempel 3: Samme søk i to trær med de samme tallene

Søk etter 40, 65, 80, 50 og 21 i søketreet fra eksempel 1 (bygget av 50, 30,
70, 20, 40, 60, 80). Søk deretter etter 5, 3 og 6 i et tre som er bygget ved å
sette inn 1, 2, 3, 4, 5 i denne rekkefølgen. Sammenlign antall
sammenligninger.

Første tre — det fra eksempel 1:

                    50
         __________/ \__________
        30                      70
   ____/ \____             ____/ \____
  20          40          60          80

Nøkkel	Vei fra rota	Resultat	Antall sammenligninger
40	`50 -> 30 -> 40`	funnet	3
65	`50 -> 70 -> 60`	ikke funnet	3
80	`50 -> 70 -> 80`	funnet	3
50	`50`	funnet	1
21	`50 -> 30 -> 20`	ikke funnet	3

Sju noder, og ingen søk koster mer enn tre sammenligninger. Det er

O(\log n)

i praksis.
Andre tre — tallene satt inn i sortert rekkefølge:

Nøkkel	Vei fra rota	Resultat	Antall sammenligninger
5	`1 -> 2 -> 3 -> 4 -> 5`	funnet	5
3	`1 -> 2 -> 3`	funnet	3
6	`1 -> 2 -> 3 -> 4 -> 5`	ikke funnet	5

Det er samme algoritme, samme antall noder i samme størrelsesorden — og helt

annen kostnad. Det andre treet har ingen forgreninger i det hele tatt. Hver
node har bare et høyre barn, så strukturen er en lenket liste med ekstra

pekere, og søket er et lineært søk.

Det er nettopp derfor kjøretiden skrives $O(h)$ og ikke $O(\log n)$ . Høyden er

2 i det første treet og 4 i det andre, og med 1000 noder i stedet for sju ville
forskjellen vært omtrent 10 mot 999.
Fellenote. Fella her er felle #10 — å oppgi en kjøretid uten å si hva
størrelsen er. Skriver du « $O(\log n)$ » om et søketre uten å nevne at det
forutsetter balanse, har du gitt et svar som er galt for det andre treet over.

Høyden

h

til et tre

-1

Balansert tre

h = O(\log n)

Degenerert (skjevt) tre

h = n - 1

📝Oppgave 3

Sjanger E

Sett inn 9, 7, 5, 3 og 1 i denne rekkefølgen i et tomt binært
søketre.

a) Tegn treet, og oppgi in-order-utskriften og høyden.
b) Hvor mange sammenligninger koster et søk etter 1?
c) Hvilken innsettingsrekkefølge av de samme fem tallene ville gitt lavest
mulig høyde?

📝Oppgave 4

Sjanger C

Avgjør om hvert utsagn er sant eller usant, og begrunn med
én setning.

a) Den minste verdien i et binært søketre ligger alltid i en bladnode.
b) In-order-utskriften av et gyldig søketre er alltid sortert.
c) Et søk i et binært søketre med $n$ noder koster $O(\log n)$ .
d) Rotverdien er alltid den første verdien som ble satt inn.

Løkke 4 — sletting, og de tre tilfellene (ca. 15 min)

— naturlig pausepunkt —

Å fjerne en verdi er den eneste operasjonen på et søketre som ikke er én rett
vei nedover. Å finne noden er lett; problemet er hva du gjør med hullet den
etterlater seg, og svaret avhenger av hvor mange barn noden har.

Det er derfor sletting alltid deles i tre tilfeller, og det er derfor du
bør skrive dem opp som tre tilfeller når du svarer:

1. Bladnode — ingen barn. Noden fjernes, og ingenting mer skjer.
2. Ett barn — barnet løftes opp og tar nodens plass. Hele subtreet under
følger med, og BST-egenskapen holder fortsatt, fordi alt i det subtreet
allerede lå på riktig side av forelderen.
3. To barn — her går det ikke an å løfte opp noen av barna direkte, for da
ville det andre barnet bli hjemløst. I stedet finner du verdien som ligger
rett etter den du skal fjerne i sortert rekkefølge, kopierer den inn i
noden, og sletter den på sin gamle plass.

Den verdien i punkt 3 har et navn.

In-order-etterfølger

Verdien som kommer rett etter en gitt node i in-order-utskriften. For en node med to barn er det alltid den minste verdien i høyre subtre — altså Min(v.right) . Den er akkurat den riktige erstatteren ved sletting: den er større enn alt i venstre subtre og mindre enn alt annet i høyre subtre, så BST-egenskapen holder etter byttet. Og fordi den er minst i sitt subtre, har den aldri et venstre barn — så sletting av den selv faller alltid i tilfelle 1 eller 2.

📜Pseudokode-kontrakt: `Delete`

Antagelser om representasjon. Noder med v.x, v.left, v.right; nil
for tomt subtre. Prosedyren returnerer den nye rota i subtreet, slik at
forelderen kan koble den inn — det er den enkleste måten å slippe
parent-pekere.

Prebetingelse: treet oppfyller BST-egenskapen.
Postbetingelse: x finnes ikke i treet, alle andre verdier er uendret, og
BST-egenskapen holder fortsatt.

Procedure Delete(v, x)
  Input:  rota v i et BST, verdien x som skal fjernes
  Output: rota i subtreet etter at x er fjernet
  if v er nil:
      return nil
  if x < v.x:
      v.left = Delete(v.left, x)
  else if x > v.x:
      v.right = Delete(v.right, x)
  else:
      if v.left er nil:
          return v.right
      if v.right er nil:
          return v.left
      e = MinNode(v.right)
      v.x = e.x
      v.right = Delete(v.right, e.x)
  return v

MinNode er Min fra kontrakten over, men den returnerer selve noden i stedet
for verdien.

Legg merke til hvor kompakt de tre tilfellene er blitt. De to første
if-ene inne i else dekker både bladnode og ett barn: har noden ingen
venstre, returnerer vi høyre — og er høyre også nil, returnerer vi nil,
som er nøyaktig det bladnode-tilfellet skal gjøre.

Kjøretid: $O(h)$ . Søket ned til noden er $O(h)$ , og i to-barn-tilfellet
koster MinNode pluss det andre Delete-kallet til sammen én ny vei nedover
i høyre subtre — altså $O(h)$ til, som ikke endrer orden.

✏️Eksempel 4: Tre slettinger etter hverandre

Ta søketreet fra eksempel 1 (bygget av 50, 30, 70, 20, 40, 60, 80) og slett
20, deretter 30, deretter 70. Oppgi treet og in-order-utskriften etter hver
sletting, og si hvilket av de tre tilfellene hver av dem er.

Starttreet:

                    50
         __________/ \__________
        30                      70
   ____/ \____             ____/ \____
  20          40          60          80

Slett 20 — tilfelle: bladnode (ingen barn). noden fjernes uten mer arbeid

              50
   __________/ \__________
  30                      70
   \____             ____/ \____
        40          60          80

- rot: 50 | in-order: 30, 40, 50, 60, 70, 80 | høyde: 2

Slett 30 — tilfelle: ett barn. barnet 40 løftes opp og tar nodens plass

        50
   ____/ \__________
  40                70
               ____/ \____
              60          80

- rot: 50 | in-order: 40, 50, 60, 70, 80 | høyde: 2

Slett 70 — tilfelle: to barn. in-order-etterfølgeren er 80 (minste i høyre
subtre); verdien kopieres inn i noden, og 80 slettes på sin gamle plass

        50
   ____/ \__________
  40                80
               ____/
              60

- rot: 50 | in-order: 40, 50, 60, 80 | høyde: 2

Se på det siste steget. Noden som holdt 70, har nå verdien 80, og den gamle
80-noden er borte. Erstatteren finner du ved å gå én gang til høyre fra
noden som skal fjernes, og deretter så langt til venstre det går. Her er høyre
barn av 70 nettopp 80, og 80 har ikke noe venstre barn — så 80 er
in-order-etterfølgeren. Det stemmer med in-order-rekka før slettingen: 40, 50,
60, 70, 80, der tallet rett etter 70 er 80.

Kontrollen etter hver sletting: in-order-utskriften skal fortsatt være
sortert, og den skal ha nøyaktig ett tall færre. Begge deler stemmer i alle tre
stegene over.

Fellenote. Fella her er å bytte inn feil node i to-barn-tilfellet — for
eksempel det største barnet, eller venstre barn. Erstatteren må være
in-order-etterfølgeren, altså Min(v.right), ellers brytes BST-egenskapen
med en gang.

📝Oppgave 5

Sjanger E

Ta søketreet bygget av 50, 30, 70, 20, 40, 60 og 80, og slett
rotverdien 50.

a) Hvilket av de tre tilfellene er dette, og hvilken verdi tar over?
b) Tegn treet etterpå, og oppgi rotverdien og in-order-utskriften.
c) Hvorfor kan du ikke bare løfte opp venstre barn, 30, i stedet?

📝Oppgave 6

Sjanger E

Et søketre er bygget ved å sette inn 15, 9, 20, 6, 12, 17, 25, 3,
8 og 11 i denne rekkefølgen. Slett først 25, deretter 17.

a) Hvilket tilfelle er hver av de to slettingene?
b) Oppgi in-order-utskriften etter hver sletting.
c) Endret høyden på treet seg?

Typiske feil

- Å forveksle BST-egenskapen med heap-egenskapen. Dette er felle #9 i
bokas feilregister, og den dyreste i Del 4. Et søketre ordner venstre mot
høyre: alt i venstre subtre er mindre enn noden, alt i høyre er større. En
heap ordner opp mot ned: forelderen er mindre enn begge barna, og det
finnes ingen ordning mellom søsken. Kontrollen: skriv ut in-order. Er
utskriften sortert, er det et søketre.
- Å tro at in-order gir innsettingsrekkefølgen. In-order gir alltid den
sorterte rekkefølgen, uansett hvordan verdiene kom inn. Det er pre-order
som kan leses som en innsettingsrekkefølge.
- Å anta at treet er balansert. Et vanlig BST har ingen slik garanti.
Kjøretiden er $O(h)$ , og $h$ kan være alt fra omtrent $\log_2 n$ til
$n - 1$ . Skriver du « $O(\log n)$ » uten forbehold, har du svart feil på et
degenerert tre — og det er felle #10, å oppgi en kjøretid uten å si hva
størrelsen er og hva som forutsettes.
- Å gå til feil side ved innsetting. Den vanligste regnefeilen under
tidspress, og den forplanter seg: alle senere verdier som skulle ned samme
vei, havner galt. Kontrollen: in-order-utskriften din skal være sortert.
Er den ikke det, er treet feil.
- Å bytte inn feil node ved sletting av en node med to barn. Erstatteren
er in-order-etterfølgeren, altså den minste verdien i høyre subtre. Å
løfte opp et av barna direkte ødelegger treet.
- Å levere treet når sensor ba om in-order. Håndkjøringssjangeren spør
etter en bestemt sluttilstand — les hva den ber om, og lever nøyaktig det:
in-order-utskriften, rotverdien, eller begge.

📝Oppgave 7

Sjanger E, eksamensnivå

Sett inn 5, 3, 8, 2, 4, 7, 9 og 1 i denne
rekkefølgen i et tomt binært søketre.

a) Oppgi in-order-, pre-order- og post-order-utskriften, samt høyden.
b) En medstudent påstår at treet også er en gyldig min-heap, «siden 5 er
minst av 5, 3 og 8 sine forfedre». Avgjør påstanden.
c) Hvilken av de tre utskriftene ville du levert hvis oppgaven bare sa
«oppgi sluttilstanden»?

📝Oppgave 8

Sjanger E og C,…

Et søketre er bygget ved å sette inn 24, 11,
37, 6, 18, 30, 44, 14 og 21 i denne rekkefølgen.

a) Oppgi in-order-, pre-order- og post-order-utskriften, samt rotverdi og
høyde.
b) Du skal fjerne 11. Hvilket tilfelle er det, hvilken verdi tar over, og
hva blir in-order-utskriften etterpå?
c) Hvor mange sammenligninger koster et søk etter 21, og hvordan forholder
det tallet seg til høyden?

Begrepsbank

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

`Insert` i et BST

O(h)

In-order-traversering

O(n)

Pre-order og post-order

O(n)

`Search` i et BST

O(h)

`Min` og `Maks` i et BST

O(h)

Sletting av en bladnode

Tilfelle 1: noden har ingen barn og fjernes uten mer arbeid. Ingen andre noder berøres, og BST-egenskapen kan ikke brytes av å fjerne noe helt nederst.

Sletting av en node med ett barn

Tilfelle 2: barnet løftes opp og tar nodens plass, med hele subtreet sitt. Det er trygt fordi alt i det subtreet allerede lå på riktig side av forelderen over — ordningen mellom dem endres ikke av at ett ledd forsvinner.

Sletting av en node med to barn

O(h)

BST-egenskap kontra heap-egenskap

BST: venstre-høyre. Alt i venstre subtre er mindre enn noden, alt i høyre er større. Heap: opp-ned. Forelderen er mindre enn begge barna, og det finnes ingen ordning mellom søsken. Å blande de to er felle #9, den vanligste feilen i Del 4. Kontrollen tar fem sekunder: er in-order-utskriften sortert, er det et søketre.

Sjanger E — håndkjøring av datastruktur

Del 1-sjangeren der du får en operasjonsrekke og skal oppgi kun sluttilstanden til strukturen. Minst én per sett, ofte to. Delvis riktig sluttilstand gir delvis uttelling, så la aldri svaret stå tomt — men les nøye hva slags sluttilstand oppgaven ber om.

Svarformatet for et BST på eksamen

In-order-utskriften, som er verdiene i stigende rekkefølge, eventuelt sammen med rotverdien . Det tilsvarer «hele arrayet» for en heap og «hele tabellen med_» for en hashtabell: hver struktur har sitt eget format, og å levere feil format koster poeng selv når håndkjøringen er riktig. Er du i tvil, ta med både in-order-utskriften og rotverdien.

Repetisjon — kapitlet på ett kort

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.