4.3 Balanserte trær — AVL og rød-svart

AVL-trær med rotasjoner (håndkjøring) og rød-svart-fargelegging — hvorfor balanse gir O(log n), og hvordan man teller rotasjoner.

55 min

8 oppgaver

Balanserte trærAVLrød-svart

Din fremgang i kapitlet

0 / 8 oppgaver

Kapitlets plass i kurset

Bygger på

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

Balanserte trær har vært på 3 av de 7 settene i arkivet (43 %). Det er
sjeldnere enn heap og vanlig søketre — men når temaet først kommer, kommer det i
én bestemt form:

- Sjanger E — håndkjøring av en datastruktur, altså at du utfører
operasjonen steg for steg på papir og oppgir kun sluttilstanden. Du får en
rekke tall og skal sette dem inn i et AVL-tre.

Og svaret sensor ber om, består av nøyaktig tre ting:

1. antall enkle rotasjoner — en dobbelrotasjon teller som to,
2. rotverdien til slutt,
3. er dette et gyldig AVL-tre?

Dette er et av de to stedene der IN2010 er tyngre enn NTNUs TDT4120. Der er
balanserte trær stort sett et faktapunkt du krysser av på. Her skal du kunne
rotere for hånd og telle rotasjonene riktig. Kommer du fra et NTNU-pensum
eller en generisk algoritmebok, er dette et tema du systematisk undervurderer.
(Det andre stedet er hashing, kap. 3.1.)

Om prioritet. Boka merker hvert tema med ett av tre nivåer: må sitte
(høyeste prioritet), kunne, og kjenne til. Balanserte trær ligger på
nivå to — kunne. De kommer ikke i hvert sett, men de er billige poeng for
den som har drillet dem, og de er ofte det som skiller en god besvarelse fra en
middels. Rød-svart-trær, som du møter helt til slutt i kapitlet, ligger på
nivå tre: kjenne til. Der holder det å kunne faktaene.

Slik er kapitlet lagt opp (55 min): fire løkker med tidsanslag, og et
pausepunkt midtveis.

Løkke	Innhold	Tid
1	Hvorfor balanse — og hva et AVL-tre er	ca. 12 min
2	De fire ubalansetilfellene og rotasjonene	ca. 16 min
3	Rotasjonstelling gjennom en hel innsettingsrekke	ca. 17 min
4	Rød-svart-trær — kort, og på nivå «kjenne til»	ca. 10 min

Forkunnskaper

- kap. 4.1 — BST-egenskapen, innsetting og in-order.
Et AVL-tre er et binært søketre; det eneste nye er at det holdes balansert.
Uten BST-egenskapen i ryggmargen gir rotasjonene ingen mening.
- kap. 1.1 — hva $O(\log n)$ betyr, og hvorfor
halvering gir en logaritme. Hele poenget med balanse er å holde høyden der.
- kap. 1.4 — faktapunktet om at et balansert søketre kan
brukes som prioritetskø. Det dukker opp igjen her, nå med begrunnelsen.

Har du ikke lest kap. 4.1, les den først. Resten av dette
kapitlet forutsetter at du kan sette inn i et vanlig søketre uten å tenke.

Notasjons- og pseudokodeliste

Løkke 1 — når søketreet blir en lenkeliste (ca. 12 min)

Et sykkelverksted registrerer ordrene sine i et binært søketre, med ordrenummeret
som nøkkel. Numrene deles ut fortløpende: 1001, 1002, 1003, 1004 og så videre.

Se hva som skjer. 1001 blir rot. 1002 er større, så den havner til høyre. 1003 er
større enn begge, så den havner til høyre for 1002. Etter tusen ordrer er treet
en kjede på tusen noder, uten en eneste forgrening til venstre.

Søketreet er teknisk sett feilfritt — BST-egenskapen holder i hver eneste node —
men det er blitt en lenket liste med ekstra pekere. Et søk må gå gjennom hele
kjeden, og kjøretiden er $O(n)$ , ikke $O(\log n)$ .

Dette er ikke et konstruert uhell. Sortert eller nesten sortert input er den
mest hverdagslige inputen som finnes: ordrenumre, datoer, ansiennitet,
løpenumre. Et vanlig søketre er raskt i gjennomsnitt og katastrofalt på nettopp
de dataene du oftest har.

Løsningen er å la treet gjøre litt ekstra arbeid ved hver innsetting, slik at det
aldri får lov til å bli skjevt. Det er det et AVL-tre gjør.

AVL-tre

O(\log n)

Balansefaktor

v

📜Høyden til et AVL-tre er

O(\log n)

— med tellingen

Påstanden er lett å hevde og verdt å regne på, for det er den som gjør hele
strukturen interessant.

Snu spørsmålet: i stedet for å spørre hvor høyt et tre med $n$ noder kan bli,
spør vi hvor få noder et AVL-tre av høyde $h$ kan slippe unna med. Kall det
$N(h)$ . Et magert AVL-tre av høyde $h$ har en rot, ett subtre av høyde $h-1$ , og
— så magert som kravet tillater — ett subtre av høyde $h-2$ :

$N(0) = 1, \quad N(1) = 2, \quad N(h) = 1 + N(h-1) + N(h-2)$

Regnet ut:

Høyde $h$	Minste antall noder $N(h)$	$2 \cdot N(h-2)$
0	1	-
1	2	-
2	4	2
3	7	4
4	12	8
5	20	14
6	33	24
7	54	40
8	88	66
9	143	108

Les den tredje kolonnen. I hver rad er

N(h)

større enn

2 \cdot N(h-2)

4 > 2

7 > 4

12 > 8

20 > 14

33 > 24

54 > 40

88 > 66

143 > 108

. Det er ikke en tilfeldighet, det følger direkte av formelen:

N(h) = 1 + N(h-1) + N(h-2)

er større enn

2 \cdot N(h-2)

fordi

N(h-1)

selv
er større enn

N(h-2)

.
Antall noder minst dobles for hver annen høyde. Da er

N(h) \ge 2^{h/2}, \quad \text{og siden } n \ge N(h): \quad h \le 2\log_2 n

Konkret: et AVL-tre med 143 noder har høyde høyst 9. Et vanlig søketre med
143 noder kan ha høyde 142 — kjeden fra verkstedet over.
Kjøretiden følger. Søk og innsetting følger én sti fra rota ned til et
blad, og gjør konstant arbeid i hver node. Antall noder på stien er høyden pluss

én, altså $O(h)$ , og med $h \le 2\log_2 n$ er det $O(\log n)$ .

AVL-treets kjøretider

O(\log n)

Operasjon	AVL-tre	Vanlig BST, verste tilfelle
Søk	$O(\log n)$	$O(n)$
Innsetting	$O(\log n)$	$O(n)$
Sletting	$O(\log n)$	$O(n)$
Minste/største	$O(\log n)$	$O(n)$
In-order-utskrift	$O(n)$	$O(n)$

✏️Eksempel 1: Er dette et gyldig AVL-tre?

Avgjør om treet under er et gyldig AVL-tre. Oppgi balansefaktoren til hver node.

                    50
         __________/ \____
        25                75
   ____/ \____             \____
  10          35                90

Framgangsmåten er alltid den samme: begynn nederst. En bladnode har to tomme
subtrær, begge med høyde

-1

, så

\mathrm{bf} = (-1) - (-1) = 0

- 10 er et blad: $\mathrm{bf} = 0$ .
- 35 er et blad: $\mathrm{bf} = 0$ .
- 90 er et blad: $\mathrm{bf} = 0$ .
- 25 har to bladbarn, begge med høyde 0: $\mathrm{bf} = 0 - 0 = 0$ .
- 75 har tomt venstre subtre (høyde $-1$ ) og bladet 90 til høyre (høyde 0):
$\mathrm{bf} = -1 - 0 = -1$ .
- 50 har venstre subtre med rot 25 (høyde 1) og høyre subtre med rot 75
(høyde 1): $\mathrm{bf} = 1 - 1 = 0$ .

Samlet, skrevet i pre-order slik du ville lest treet ovenfra og ned:

50:+0, 25:+0, 10:+0, 35:+0, 75:-1, 90:+0

Svar: ja, dette er et gyldig AVL-tre. Ingen balansefaktor er utenfor
$-1$ til $+1$ .

Legg merke til node 75. Den har bare ett barn, og likevel er den i orden:
høydeforskjellen er 1, som er akkurat innenfor. Det er en vanlig kilde til
tvil — «ett barn» er ikke i seg selv et brudd.

Fellenote. Fella her er felle #9 i bokas feilregister — å forveksle
BST-/AVL-balansen (som handler om høyder, altså opp og ned) med
heap-egenskapen (som handler om verdier mellom forelder og barn). Her sier
ingen at 25 må være mindre enn 50 av balansehensyn; det følger av
BST-egenskapen, som er en helt annen regel.

📝Oppgave 1

(Innstegsoppgave, sjanger E — håndkjøring av en datastruktur, altså at du
utfører operasjonen steg for steg på papir og oppgir sluttilstanden.) Se på dette
treet:

              30
         ____/ \____
        20          40
   ____/
  10

a) Oppgi balansefaktoren til hver node.
b) Er dette et gyldig AVL-tre?

Løkke 2 — de fire ubalansetilfellene (ca. 16 min)

Nå til selve maskineriet.

Du setter inn en ny nøkkel akkurat som i et vanlig søketre: følg stien fra rota
til den havner som et nytt blad. Deretter går du tilbake oppover langs den
samme stien og oppdaterer høydene. Den første noden du møter med
balansefaktor $+2$ eller $-2$ , er der ubalansen sitter, og den er den eneste du
skal gjøre noe med.

Hva du skal gjøre, avhenger av hvor den nye nøkkelen havnet i forhold til den
noden. Se på de to første stegene på stien nedover fra den ubalanserte noden mot
den nye nøkkelen. Hvert steg er enten venstre (L) eller høyre (R), og de to
bokstavene gir navnet på tilfellet:

Tilfelle	De to stegene ned mot den nye nøkkelen	Løsning	Enkle rotasjoner
LL	venstre, så venstre	én høyrerotasjon om den ubalanserte noden	1
RR	høyre, så høyre	én venstrerotasjon om den ubalanserte noden	1
LR	venstre, så høyre	venstrerotasjon om barnet, så høyrerotasjon om noden	2
RL	høyre, så venstre	høyrerotasjon om barnet, så venstrerotasjon om noden	2

De to første kalles enkle tilfeller — ubalansen ligger «rett ut», og én
rotasjon retter den. De to siste kalles doble: den nye nøkkelen havnet i det
indre subtreet, og da må det roteres to ganger.
Skriv opp den siste kolonnen og pugg den. Det er der poengene forsvinner.

Enkelrotasjon

O(1)

📜Pseudokode-kontrakt: `RotateLeft`

Antagelser om representasjon. Treet består av noder, og en node v har
feltene v.x (nøkkelen), v.left, v.right og v.height. Et tomt subtre
skrives tom og har høyde -1. Sensor binder seg ikke til én representasjon —
men du må oppgi den du bruker.

Prebetingelse: v.right er ikke tom. Postbetingelse: subtreet har samme
in-order-rekkefølge som før, og v.right fra før er blitt den nye roten i
subtreet.

Procedure RotateLeft(v)
  Input:  node v der v.right ikke er tom
  Output: den nye roten i subtreet etter en enkel venstrerotasjon
  ny = v.right
  v.right = ny.left
  ny.left = v
  oppdater v.height, deretter ny.height
  return ny

Grunnideen i én setning: ny.left er det eneste subtreet som ligger mellom
v og ny i sortert rekkefølge, så det er det eneste som må flyttes — og det
kan bare henges på v sin høyreside.

Merk rekkefølgen på de to siste linjene. Høyden til v må oppdateres
før høyden til ny, fordi v nå er barn av ny. Bytter du om, blir
ny.height regnet ut fra en foreldet verdi. Dette er et av de stedene sensor
gir delpoeng for å ha tenkt riktig.

Kjøretid: $O(1)$ . Tre pekertilordninger og to høydeoppdateringer, uavhengig
av $n$ . Det er derfor rebalanseringen ikke gjør innsettingen dyrere enn
$O(\log n)$ : selve nedstigningen koster $O(\log n)$ , og rotasjonen på toppen
koster ingenting.

✏️Eksempel 2: RR — sett inn 10, 20, 30 i et tomt AVL-tre

Sett inn 10, 20 og 30 i denne rekkefølgen i et tomt AVL-tre. Oppgi antall enkle
rotasjoner, rotverdien til slutt, og om resultatet er et gyldig AVL-tre.

Steg	Nøkkel	Ubalanse oppdaget i	Tilfelle	Rotasjon(er)	Enkle rot. i steget	Sum enkle rot.	Rot etter steget
1	10	ingen	-	ingen	0	0	10
2	20	ingen	-	ingen	0	0	10
3	30	10	RR	enkel venstrerotasjon om 10	1	1	20

Steg for steg.
Etter steg 1 er 10 alene, med 10:+0.
Etter steg 2 henger 20 til høyre for 10:

  10
   \____
        20

Balansefaktorene er 10:-1, 20:+0. Fortsatt lovlig — $-1$ er innenfor.

Etter steg 3 havner 30 til høyre for 20. Nå er 10 sin høyre side to nivåer høy og

venstre side tom, altså $\mathrm{bf}(10) = -1 - 1 = -2$ . Ubalansen sitter i

10. De to stegene ned mot 30 er høyre, så høyre — altså RR. Én enkel

venstrerotasjon om 10:

        20
   ____/ \____
  10          30

Balansefaktorene er 20:+0, 10:+0, 30:+0, og in-order er 10, 20, 30.
Sluttilstand — dette er svaret du leverer:
- totalt antall ENKLE rotasjoner: 1

- rotverdi til slutt: 20

- gyldig AVL-tre: JA

Fellenote. Fella her er å levere treet i stedet for de tre tallene. Sensor ber

om antall rotasjoner, rotverdi og gyldighet — tegner du et fint tre uten å svare
på de tre spørsmålene, får du ikke poengene.

📝Oppgave 2

Sjanger E

Sett inn 30, 20 og 10 i denne rekkefølgen i et tomt AVL-tre. Oppgi
antall enkle rotasjoner, rotverdien til slutt, og om resultatet er et gyldig
AVL-tre.

📝Oppgave 3

Sjanger E

RotateLeft sto i pseudokode-kontrakten over. Skriv RotateRight,
speilbildet. Oppgi antagelser om representasjon og kjøretid, og forklar i én
setning hvorfor in-order-rekkefølgen er uendret.

Dobbelrotasjon

Rebalanseringen som kreves når den nye nøkkelen havner i det indre subtreet til den ubalanserte noden, altså i LR- og RL-tilfellene. Den består av to enkle rotasjoner : først én om barnet, som gjør tilfellet om til et LL eller RR, deretter én om noden selv. I LR-tilfellet er det først en venstrerotasjon om venstre barn, så en høyrerotasjon om noden. Den teller som to. Spør oppgaven om antall enkle rotasjoner, er svaret 2 for hver dobbelrotasjon. Dette er den enkeltfeilen som koster flest poeng på AVL-håndkjøringer, og den er lett å unngå når du først vet om den.

✏️Eksempel 3: LR — sett inn 30, 10, 20 i et tomt AVL-tre

Sett inn 30, 10 og 20 i denne rekkefølgen i et tomt AVL-tre. Oppgi antall enkle
rotasjoner, rotverdien til slutt, og om resultatet er et gyldig AVL-tre.

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

Steg for steg.
Etter steg 2 henger 10 til venstre for 30:

        30
   ____/
  10

Balansefaktorene er 30:+1, 10:+0.

Etter steg 3: 20 er mindre enn 30, så vi går til venstre; 20 er større enn 10, så

vi går til høyre. Nøkkelen havner som høyre barn av 10. Nå er

$\mathrm{bf}(30) = 1 - (-1) = +2$ . Ubalansen sitter i 30, og de to stegene ned

mot 20 er venstre, så høyre — altså LR.

Én rotasjon holder ikke her. Hadde du høyrerotert om 30 med én gang, ville 10 blitt
rot med 20 og 30 til høyre — like skjevt, bare motsatt vei. I stedet:
1. venstrerotasjon om 10 gjør stien om til venstre, venstre — altså et vanlig
LL-tilfelle,

2. høyrerotasjon om 30 retter det.
Resultatet:

        20
   ____/ \____
  10          30

Balansefaktorene er 20:+0, 10:+0, 30:+0, og in-order er 10, 20, 30.
Sluttilstand — dette er svaret du leverer:

- totalt antall ENKLE rotasjoner: 2

- rotverdi til slutt: 20

- gyldig AVL-tre: JA

Fellenote. Fella her er kapitlets egen, og den står ikke i det nummererte

feilregisteret fordi den er så spesifikk: å telle dobbelrotasjonen som én
rotasjon. Sensor spør etter enkle rotasjoner, og en dobbel er to av dem.
Svarer du 1 her, har du regnet helt riktig og likevel mistet poenget.

📝Oppgave 4

Sjanger E

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

a) Hvilket av de fire tilfellene oppstår, og i hvilken node?
b) Oppgi antall enkle rotasjoner, rotverdien til slutt, og om resultatet er
et gyldig AVL-tre.

Typiske feil

De fire under er hentet fra det som faktisk trekkes på AVL-oppgaver. Den første
er den dyreste.

- Å telle en dobbelrotasjon som én rotasjon. Spørsmålet er «hvor mange
enkle rotasjoner», og en dobbel består av to. Kontroll: legg sammen
kolonnen «Enkle rot. i steget» i sporingen din, og se etter om noen av
radene sier «dobbelrotasjon» med tallet 1 ved siden av.
- Å ikke oppgi rotverdien eller gyldigheten. Svaret består av tre ting, og et
tegnet tre er ikke ett av dem. Skriv de tre linjene eksplisitt, også når du
synes de er opplagte.
- Å forveksle AVL-balansen med heap-egenskapen. Dette er felle #9 i bokas
feilregister. AVL-kravet handler om høyder — hvor dypt subtrærne går. Heapen
handler om verdier mellom forelder og barn. Et AVL-tre kan gjerne ha en
liten verdi under en stor; det er BST-egenskapen, ikke balansekravet, som styrer
verdiene.
- Å tro at rød-svart-trær har en annen asymptotisk høyde enn AVL-trær. Begge
er $O(\log n)$ . Rød-svart-trær er litt løsere balansert og roterer sjeldnere,
men i $O$ -forstand er de like.

Og den gjennomgående, som gjelder hele boka: å bruke $n$ uten å definere det
— felle #10. Skriver du «kjøretiden er $O(\log n)$ », si i samme setning at
$n$ er antall noder i treet. Det koster fem ord.

Løkke 3 — rotasjonstelling gjennom en hel innsettingsrekke (ca. 17 min)

— naturlig pausepunkt —

Tre noder er en oppvarming. Eksamensoppgaven gir deg fem til ti nøkler og spør
etter totalen.

Da trenger du én ting til, og det er en god nyhet: hver innsetting utløser
høyst én rebalansering. Du trenger altså ikke lete videre oppover etter at du
har rettet den første ubalansen — treet er ferdig balansert i samme øyeblikk.

Grunnen er at rotasjonen setter subtreets høyde tilbake til det den var før
innsettingen. Og var høyden uendret der, merker ingen node lenger oppe at noe har
skjedd. Dette gjelder ved innsetting; ved sletting kan flere rotasjoner
kreves, men sletting i AVL-tre håndkjøres ikke i dette faget.

Arbeidsgangen per nøkkel blir derfor mekanisk:

1. sett inn nøkkelen som i et vanlig søketre,
2. gå oppover langs stien og se etter den første noden med balansefaktor
$+2$ eller $-2$ ,
3. finner du en: avgjør LL / RR / LR / RL av de to stegene nedover, roter, og
legg 1 eller 2 til rotasjonstelleren,
4. finner du ingen: gå videre til neste nøkkel.

📜Håndkjøringsformatet for AVL

Sensor ber om sluttilstanden, ikke om veien dit. For AVL består sluttilstanden av
tre ting, og alle tre må stå der:

1. Antall enkle rotasjoner totalt. Dobbelrotasjon teller som to.
2. Rotverdien etter siste innsetting.
3. Er dette et gyldig AVL-tre? Svaret er ja hvis du har rebalansert korrekt
underveis — men spørsmålet stilles fordi noen oppgaver gir deg et ferdig tre
og ber deg vurdere det.

Delvis riktig gir delvis uttelling. Får du rotverdien riktig og
rotasjonstallet galt, får du fortsatt uttelling for rotverdien. Derfor: la aldri
noen av de tre linjene stå tomme, selv om du er usikker.

En kontroll som tar ti sekunder: skriv ned in-order-utskriften av treet ditt
til slutt. Den skal være nøklene dine i sortert rekkefølge — alle sammen,
ingen mistet, ingen duplisert. Har du rotert feil, avslører in-order det nesten
alltid.

✏️Eksempel 4: Fem stigende nøkler — 1, 2, 3, 4, 5

Sett inn 1, 2, 3, 4 og 5 i denne rekkefølgen i et tomt AVL-tre. Hvor mange enkle
rotasjoner utføres totalt, og hva er rotverdien til slutt?

Dette er nøyaktig verkstedscasen fra starten av kapitlet: stigende nøkler, som i
et vanlig søketre ville gitt en kjede på fem noder med høyde 4.

Steg	Nøkkel	Ubalanse oppdaget i	Tilfelle	Rotasjon(er)	Enkle rot. i steget	Sum enkle rot.	Rot etter steget
1	1	ingen	-	ingen	0	0	1
2	2	ingen	-	ingen	0	0	1
3	3	1	RR	enkel venstrerotasjon om 1	1	1	2
4	4	ingen	-	ingen	0	1	2
5	5	3	RR	enkel venstrerotasjon om 3	1	2	2

Steg for steg.
Etter steg 3 er treet balansert med 2 som rot:

        2
   ____/ \____
  1           3

Balansefaktorene er 2:+0, 1:+0, 3:+0.
Etter steg 4 henger 4 til høyre for 3:

        2
   ____/ \____
  1           3
               \____
                    4

Balansefaktorene er 2:-1, 1:+0, 3:-1, 4:+0. Merk at rota nå har $-1$ — det er

lovlig, og derfor gjøres ingenting.

Etter steg 5 havner 5 til høyre for 4, og $\mathrm{bf}(3) = -1 - 1 = -2$ .

Ubalansen oppdages i 3, ikke i rota: 3 er den første noden med $\pm 2$ på

vei oppover. Tilfellet er RR, og én venstrerotasjon om 3 gir

        2
   ____/ \__________
  1                 4
               ____/ \____
              3           5

Balansefaktorene er 2:-1, 1:+0, 4:+0, 3:+0, 5:+0, og in-order er 1, 2, 3, 4, 5
— sortert, alle fem med, ingen duplisert.

Sluttilstand — dette er svaret du leverer:
- totalt antall ENKLE rotasjoner: 2
- rotverdi til slutt: 2

- gyldig AVL-tre: JA

Høyden ble 2 i stedet for 4, med to rotasjoner som pris.
Merk hvor ubalansen ble oppdaget i steg 5. Ikke i rota, men i 3. Å lete fra

rota og nedover i stedet for fra den nye noden og oppover er en klassisk kilde

til feil svar: da roterer du feil node, og både rotverdien og rotasjonstallet
blir galt.
Fellenote. Fella her er å tro at rota alltid er den som må roteres. Det er

den nederste noden med balansefaktor $\pm 2$ som skal rebalanseres, og etter

den ene rotasjonen er hele treet i orden igjen.

📝Oppgave 5

Sjanger E

Sett inn 50, 40, 30, 20 og 10 i denne rekkefølgen i et tomt AVL-tre.
Oppgi antall enkle rotasjoner, rotverdien til slutt, og om resultatet er et gyldig
AVL-tre.

📝Oppgave 6

Sjanger E

Sett inn 5, 10, 15, 12 og 14 i denne rekkefølgen i et tomt AVL-tre.

a) Hvilke tilfeller oppstår, og i hvilke noder?
b) Oppgi antall enkle rotasjoner, rotverdien til slutt, og om resultatet er
et gyldig AVL-tre.

📝Oppgave 7

Sjanger E, krevende

Sett inn 15, 25, 35, 5, 10 og 20 i denne rekkefølgen i et
tomt AVL-tre.

a) Før en tabell med ett steg per innsetting, der du oppgir hvilken node
ubalansen oppdages i, hvilket tilfelle det er, og hvor mange enkle rotasjoner
steget koster.
b) Oppgi antall enkle rotasjoner totalt, rotverdien til slutt, og om
resultatet er et gyldig AVL-tre.

Løkke 4 — rød-svart-trær (ca. 10 min)

Dette avsnittet ligger på nivå «kjenne til». Rød-svart-trær håndkjøres ikke i
IN2010 — du blir aldri bedt om å fargelegge et tre for hånd. Det som testes, er
noen få faktapunkter på Del 1, og de er raskt lært. Har du dårlig tid, er dette
avsnittet det første du kan lese overfladisk.

Et rød-svart-tre er den andre måten å holde et søketre balansert på. I stedet
for å telle høyder gir man hver node en farge, rød eller svart, og krever at
fargene fordeler seg etter noen enkle regler. Reglene er indirekte nok til at
treet ikke er helt så stramt balansert som et AVL-tre — men de holder høyden på
$O(\log n)$ likevel.

Bytteforholdet er verdt å kjenne: AVL-treet er strengere balansert og gir litt
raskere søk, mens rød-svart-treet roterer sjeldnere og gir litt raskere
innsetting og sletting. Begge er $O(\log n)$ på alt. Det er derfor de fleste
standardbiblioteker bruker rød-svart-varianten.

Rød-svart-tre

O(\log n)

Fargeinvariantene

O(\log n)

📜AVL og rød-svart — hva som er likt og hva som skiller

Likt, og det er det som testes:

- Begge er binære søketrær med BST-egenskapen.
- Begge garanterer høyde $O(\log n)$ .
- Begge har $O(\log n)$ på søk, innsetting og sletting i verste tilfelle.
- Begge kan brukes som prioritetskø med samme kjøretidsorden som en heap: det
minste elementet ligger lengst til venstre og hentes i $O(\log n)$ .

Og det faste sant-punktet: hvert AVL-tre kan fargelegges slik at det blir
et gyldig rød-svart-tre. AVL-kravet er det strengeste av de to, så et tre som
tilfredsstiller det, tilfredsstiller også de løsere fargereglene med en passende
fargelegging. Motsatt vei gjelder ikke: et rød-svart-tre kan være skjevere enn
AVL-kravet tillater.

Det som skiller, i praksis og ikke i $O$ -notasjon:

AVL-tre	Rød-svart-tre
Balansekrav	strengt (høydeforskjell høyst 1)	løsere (fargeregler)
Høyde	$O(\log n)$ , lav i praksis	$O(\log n)$ , litt høyere i praksis
Søk	litt raskere	litt tregere
Innsetting/sletting	flere rotasjoner	færre rotasjoner

Ingen av forskjellene i tabellen er asymptotiske. Påstanden «rød-svart-trær har
dårligere asymptotisk høyde enn AVL-trær» er usann, og den er en fast
distraktor.

📝Oppgave 8

Sjanger C

Avgjør sant eller usant, og begrunn hver med én setning.

a) Et rød-svart-tre har $O(\log n)$ høyde.
b) Hvert AVL-tre kan fargelegges slik at det blir et gyldig rød-svart-tre.
c) En dobbelrotasjon i et AVL-tre teller som én enkel rotasjon.
d) Et AVL-tre kan brukes som prioritetskø med samme kjøretidsorden som en
heap.

Begrepsbank

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

LL-tilfellet

+2

RR-tilfellet

-2

LR-tilfellet

Ubalansen sitter i en node der de to første stegene går venstre, så høyre — den nye nøkkelen havnet i det indre subtreet. Rettes med en dobbelrotasjon : først en venstrerotasjon om venstre barn (som gjør situasjonen om til et LL), deretter en høyrerotasjon om noden selv. Teller som 2 enkle rotasjoner.

RL-tilfellet

Ubalansen sitter i en node der de to første stegene går høyre, så venstre . Rettes med en dobbelrotasjon : først en høyrerotasjon om høyre barn (som gjør situasjonen om til et RR), deretter en venstrerotasjon om noden selv. Teller som 2 enkle rotasjoner.

Svarformatet for en AVL-håndkjøring

Tre linjer, og alle tre skal stå der: 1. antall enkle rotasjoner totalt — dobbelrotasjon teller som to, 2. rotverdien til slutt, 3. er dette et gyldig AVL-tre? Delvis riktig gir delvis uttelling, så la aldri en av linjene stå tom. Kontroll: in-order-utskriften av treet ditt skal være nøklene i sortert rekkefølge, alle med.

Høyst én rebalansering per innsetting

En innsetting i et AVL-tre utløser høyst én rebalansering — enten én enkelrotasjon eller én dobbelrotasjon. Grunnen er at rotasjonen setter subtreets høyde tilbake til det den var før innsettingen, så ingen node lenger oppe merker at noe har skjedd. Du kan altså stoppe å lete så snart du har rettet den første ubalansen. Ved sletting gjelder dette ikke — men sletting i AVL-tre håndkjøres ikke i dette faget.

AVL-tre kontra rød-svart-tre

O(\log n)

Hvert AVL-tre kan fargelegges som et rød-svart-tre

Fast sant-punkt på Del 1: AVL-kravet er strengere enn fargeinvariantene, så et høydebalansert tre kan alltid farges slik at de fire reglene holder. Motsatt vei gjelder ikke — et rød-svart-tre kan være skjevere enn AVL-kravet tillater, fordi den lengste stien får være dobbelt så lang som den korteste.

Et balansert søketre som prioritetskø

O(\log n)

AVL-balanse er ikke heap-egenskapen

AVL-kravet handler om høyder : hvor dypt de to subtrærne til en node går. Heap-egenskapen handler om verdier : at forelderen er mindre enn eller lik begge barna. Å blande dem er felle #9 i bokas feilregister. I et AVL-tre er det BST-egenskapen (venstre er mindre, høyre er større) som styrer verdiene, og balansekravet sier ingenting om dem. Se kap. 4.4 for heap-siden av forvekslingen.

Balanserte trær er tyngre i IN2010 enn i TDT4120

Her håndkjøres AVL-rotasjoner: du får en innsettingsrekke og skal telle rotasjoner, oppgi rotverdi og vurdere gyldighet. Temaet har vært på 3 av 7 sett (43 %) . I NTNUs TDT4120 har balanserte trær mindre eksamensvekt og testes stort sett som faktapunkter. Kommer du derfra, eller fra en generisk algoritmebok, undervurderer du dette temaet — det er én av to slike blindsoner i faget, sammen med hashing i kap. 3.1 .

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.