TRÆR

Question 1

Hva er definisjonen av et tre?

Answer 1

Det tomme treet eller 
- en node med peker til et element
- 0 eller flere pekere til barnenoder, og 
- nøyaktig én foreldrenode
Et tre kan ikke inneholde sykler

Question 2

Alle lister er trær, men er alle trær lister?

Answer 2

Nei, ikke alle trær er lister.

Question 3

Hvordan representerer man tomme trær?

Answer 3

Null

Question 4

Kan et tre inneholde sykler?

Answer 4

Nei

Question 5

Hva er dybde i et tre?

Answer 5

(Målt nedover)
Dybden til en node er én mer enn foreldrenoden
Roten har dybde 0
Et tomt tre har dybde -1

Question 6

Hva er høyde i et tre?

Answer 6

Den høyeste avstanden til en etterkommer

Dvs. dybden av den dypeste løvnoden

Question 7

Traversering: Hva gjør en preorder i et tre?

Answer 7

Traverserer gjennom et tre, og utfører operasjonen på seg selv først. Deretter utfører den operasjonen på barna

Question 8

Traversering: Hva gjør en postorder i et tre?

Answer 8

Traverserer gjennom treet, og gjør operasjonen på barna først. Så utfører den operasjonen på seg selv.

Question 9

Hva kan man bruke postorder til?

Answer 9

For å slette et tre

Question 10

Hva kan man bruke preorder til?

Answer 10

For å kopiere et tre

Question 11

Hva er et binært tre?

Answer 11

Et tre der hver node har maks to barn.

Question 12

Hva er et binært søketre?

Answer 12

Et binært tre med spesielle egenskaper.
For hver node v så er v.element:
- Større enn alle elementer i venstre subtre
- Mindre enn alle elementer i høyre subtre

Question 13

Hva slags datastruktur gjør binærsøk enkelt, og støtter effektiv innsetting og sletting?

Answer 13

Binært søketre

Question 14

Hva skiller et AVL-tre fra et binært søketre?

Answer 14

AVL-trær har de samme egenskapene som et binært søketre, men et AVL-tre må i tillegg oppfylle denne betingelsen:
- for hver node i et AVL-tre må høydeforskjellen på venstre og høyre subtre være mindre eller lik 1

Question 15

Balanserte søketrær: Hva gjør en balansefaktor-algoritme?

Answer 15

Sjekker hvor balansert treet er. Returnerer et heltall som er høyden i venstre subtre - høyden i høyre subtre. Returnerer algoritmen et positivt tall, er treet venstretungt, returnerer den et negativt tall er treet høyretungt. 0 indikerer at treet er balansert.

Question 16

Hvordan skiller algoritmene for innsetting og sletting seg i balanserte søketrær (AVL) og vanlige binære søketrær?

Answer 16

I balanserte søketrær må man i tillegg til algoritmene fra binære søketrer også lagre høyden til hver node og balansere treet når du er ferdig med innsetting/sletting.

Question 17

Hva skiller AVL-trær og rød-svarte trær?

Answer 17

Rød-svarte trær har lavere krav om balanse
Rød-svarte trær bruker mindre minne, siden de ikke trenger å lagre høydene
Rød-svarte trær bruker færre rotasjoner

Question 18

Hvilken farge er roten til et rød-svart tre?

Answer 18

Svart

Question 19

Rød-svarte trær: Hvilken node kan ikke ha et rødt barn?

Answer 19

En rød node

Question 20

AVL-trær: Hvilken vei må vi rotere til slutt når vi har et venstretungt tre?

Answer 20

Høyre-rotasjon