Trær Flashcards
Hva er et tre?
En sammenhengende, asyklisk graf.
Hva er forholde mellom noder og kanter i et tre?
Om et tre har n noder, har det n-1 kanter.
Hva er en forfeder / ancestor av en node i et tre?
Det er enten selve noden, dens foreldre node, eller en forfeder av dens forelder.
Sammlingen av alle foreldre fra og med selve noden er alle dens forfedre.
Hva er en etterkommer / descendant av en node i et tre?
En node v er etterkommer av node u, om u er en forfeder til v.
Altså enten noden selv, eller en hver node som forekommer i subtreet hvor den gitte noden er roten.
Hvordan defineres dybden i et tre?
Dybden til en node er en mer enn foreldrenoden.
Roten har dybde 0.
Om vi tillater et tomt tre, gir vi det dybde -1.
Vi teller altså dybden fra toppen og ned.
Hvordan defineres høyden til et tre?
Høyden av et tre er gitt av den høyeste avstanden til en etterkommer.
Altså dybden av den dypeste løvnoden.
Høyden til en node:
- Om v er en ekstern node, da er høyden lik 0
- Ellers er høyden lik 1 plus maksimum høyden av et barn av v.
Vi teller altså høyden fra bunn og opp.
Hva er preorder traversering og hva kan det brukes til?
Å utfører operasjonen på seg selv først, og barna etterpå.
- Kan brukes til å kopiere et tre.
Hva er postorder traversering og hva kan det brukes til?
Å utfører operasjonen på barna først, og seg selv etterpå.
- Kan brukes til å slette et tre.
Hvordan defineres et binært søketre?
Et binærtre som for hver node v så er v.element:
- Større enn alle elementer i venstre subtre.
- Mindre enn alle elementer i høyre subtre.
Hva er spesielt med sletting fra et binærtre?
Vi må tette igjen eventuelle hull, vi gjør det ved å finne det minste elementet i høyre subtre til noden vi vil fjerne og erstatter noden vi vil fjerne med denne (evt. største i venstre).
Hvordan defineres et AVL tre?
Et binærsøketre hvor høydeforskjellen på venstre og høyre subtre av en hver node må være mindre eller lik 1.
Når må vi utføre rotasjoner for et AVL tre?
Om treet er høyretungt, utfører vi en venstrerotasjon.
Om treet er venstretungt, utfører vi en høyrerotasjon.
Hvordan utføres en AVL rotasjon?
Venstrerotasjon:
For en node z tar vi høyrebarn y til z og setter z som venstrebarn av y, deretter setter vi det som var y sitt venstrebarn som z sitt høyrebarn.
Høyrerotasjon:
For en node z tar vi venstrebarn y til z og setter z som høyrebarn av y, deretter setter vi det som var y sitt høyrebarn som z sitt venstrebarn.
Ved et venstretungt tre, må det sjekkes om det venstre barnet har en ‘balansefaktor’ mindre enn 0
- Om så, må vi gjøre en venstre-høyre rotasjon
Ved et høyretungt tre, må det sjekkes om det høyre barnet har en ‘balansefaktor’ større enn 0
- Om så, må vi gjøre en høyre-venstre rotasjon
Balansefaktor for en node v:
- høyden(v.left) - høyden(v.right)
- Om den tunge siden av treet fortsetter i en strak linje = vanlig rotasjon
- Om den tunge siden av treet lager en bue inn mot midten = dobbel rotasjon
Hva er et rød-svart tre?
Et binært balansert søketre.
De er raskere enn AVL når innsetting og sletting forekommer ofte, siden den er mindre balansert enn AVL og trenger færre rotasjoner.
Invarianter for rød-svarte trær
- Hver node fargelegges rød eller svart
- Roten til treet er svart
- En rød node kan ikke ha et rødt barn
- Hver gren fra roten til et tomt tre (eller null) inneholder like mange svarte noder (MERK, hver gren, altså veien ned til en ekstern node, ikke hele subtreet)
Hva er et spenntre?
Et spenntre av en graf, er et tre som består av alle noder og akkurat nokk kanter til å forbinde alle disse.
- Å legge til en vilkårlig kant ekstra vil så føre til en sykel.
- Et spenntre har altså |V| - 1 kanter.
