Brodtkorb : DATS 2300202010

Hei alle sammen!

Denne uken fortsetter vi på med binære trær og ser på søketrær og minimumstrær/maksimumstrær. Vi ser også på heap som datastruktur og hvordan en minimumsheap kan brukes til heap-sortering.

Husk også ukens ukeoppgaver: gjør ukeoppgavene i dag, så står du bedre rustet når mappeeksamen blir utlevert denne uken:)!

Binære søketrær

I denne videoen går vi gjennom hvordan vi kan lage binære søketrær basert på forskjellige ordninger av de samme tallene. Dette gir veldig forskjellige søketrær, og det har mye å si for effektiviteten. De mest effektive trærne har få nivåer, og de mest ineffektive har veldig mange nivåer i forhold til antall noder.

OBS: her er det en feil i innlegging av siste tallet 5 - den skulle selvfølgelig vært til venstre for 6 og ikke til høyre!

Binære søketrær og binærsøk

I denne videoen går vi gjennom hvordan binærsøk kan sees på som et binærtre.

Datastruktur for binære søketrær

I denne videoen går vi gjennom hvordan vi kan lagre binære søketrær på datamaskinen. Vi har allerede sett på hvordan vi kan lagre det som et sortert array (binærsøk), men ser også på hvordan vi kan lagre det med noder. Dette likner veldig mye på lenkede lister hvor vi har foreldre- og barne-pekere istedenfor neste og forrige peker.

Fjerning av node fra binært søketre

I denne videoen går vi gjennom de forskjellige måtene å fjerne en node fra et binært søketre. Dette er avhengig av om noden vi skal fjerne har null, ett eller to barn. Null og ett barn kan løses veldig likt som man gjør i en dobbelt lenket liste, mens to barn krever mer tankearbeide.

OBS: Denne videoen har en feil i seg ved fjerning av en node med to barn. Ny oppdatert video kommer :) Se imens kompendiet: https://www.cs.hioa.no/~ulfu/appolonius/kap5/2/kap52.html#5.2.8

Forelesning tirsdag

I forelesning tirsdag gikk vi gjennom en del eksamens-relaterte spørsmål, samt koding av binære søketrær. Vi kodet også traversering av treet ved hjelp av rekursjon og en programatisk (ikke-rekursiv ikke-iterativ) metode.