DATS 2300202013

Prev Up Next

Denne uken skal vi se på såkalt selv-balanserende trær. Dette er noe tungt stoff, så her anbefaler jeg å repetere videoene for å se hva som skjer, samt å se på lenkene jeg har lagt inn under.

 

Målet med disse trærne er å sørge for at vi unngår å få veldig dype trær. Vi skal se på to typer slike trær, 2-3-4-trær og rød-sorte trær. 2-3-4-trærne har mulighet til å ha inntil 3 verdier per node, og inntil 4 barn. Når vi legger inn så splittes noder med fler enn 3 verdier, og det er denne splittingen som gjør at treet er selv-balanserende. For rød-sorte trær (som er ekvivalente med 2-3-4-trær - dvs vi kan gå fra rød-sorte til 2-3-4-trær og tilbake), så fargelegger vi våre noder i et vanlig binærtre. Så har vi et par regler som gjør at treet blir selv-balanserende. 

 

Denne uken legges også eksamensoppgaver fra tidligere år ut så dere kan øve på dem som ukeoppgaver. Merk at siden eksamen i år er veldig annerledes er ikke disse oppgavene nødvendigvis representative for hva dere får på eksamen. Men, selve vanskelighetsgraden burde være tilsvarende, men deres eksamen blir da tilpasset annet format og kortere tid. 

 

Lenker til animasjoner:

• 2-3-4-tre Animasjon (OBS: Her splittes ikke 3-noder ved innlegging, men når en node "dyttes opp". Det blir en ekvivalent algoritme)
• 2-3-4-tre animasjon (OBS: Her splittes en 3-node med en gang man får tre verdier)
• Rød-sorte trær 

 

2-3-4-trær

OBS: liten feil ved ca 18 minutter. Her glemmer jeg venstre barnet til «16»-noden, altså «15». Legg inn tallene jeg har brukt i de interaktive 2-3-4-trær-animasjonene over.

 

Rød-sorte trær

 

Dijkstra

I denne videoen går vi gjennom Dijkstras algoritme for å finne korteste vei i en graf. Dijkstras er et bredde-først søk som konstant finner korteste vei til alle noder. Når man så gått fra node A og kommet frem til node B (besøkt fra alle dens naboer) vet vi at vi har funnet korteste vei fra A til B. Dette høres ut som et abstrakt problem uten praktisk betydning, men det er helt feil: internett, planlegging av kjøre-ruter for leveranser, og alle liknende problemer kan løses ved å bruke Dijkstras algoritme. Her er en animasjon av Dijkstra dere kan teste ut.

 

Lagring av graf i tekst-fil og som matrise

Lagring og lesing av grafer krever et fornuftig lagrings-format. I disse videoene går vi gjennom lagring som tekst-fil og lagring som en glissen matrise. Bruk av glissne matriser er svært utbredt, og du kan se eksempler på mange store slike matriser her.