Post 6 — Binært søgetræ (fælles afslutning)

#

Læringsmål

#

De studerende kan efter aktiviteten…

• Forklare hvordan et binært søgetræ er organiseret
• Bestemme kompleksiteten for søgning, indsættelse og sletning i et balanceret træ
• Forklare hvad der sker med kompleksiteten hvis træet bliver skævt

Forudsætninger

#

De studerende forventes at kende til:

• Begrebet kompleksitet og O-notation

Kort beskrivelse

#

Hele holdet bygger et binært søgetræ med fødselsdage. Underviser styrer opbygningen så træet bliver nogenlunde balanceret. Én studerende der har været uden for døren søger sig frem til sin plads ved at sammenligne fødselsdage ved hver node. Øvelsen viser intuitivt hvorfor søgning i et balanceret træ er O(log n) — antallet af sammenligninger halveres ved hvert trin.

Faglig kontekst

#

• Semester/fag: 4. semester — Avanceret Programmering
• Holdstørrelse: Hele holdet (24 studerende)
• Organisering: Fælles afslutning efter rotation mellem Post 1–5

Trin-for-trin

#

1. Send én studerende uden for døren.
2. Byg træet med resten — start med én der har fødselsdag ca. midt på året som rod.
3. Fortsæt ned i træet ved at placere studerende til venstre (tidligere fødselsdag) eller højre (senere fødselsdag).
4. Kald personen udenfor ind og lad dem søge sig frem til en bestemt person (øvelse 1).
5. Slet den fundne person og diskuter hvad der sker med resten (øvelse 2).
6. Lad personen udenfor finde sin egen plads i træet og stille sig der (øvelse 3).
7. Afslut med spørgsmålet om et skævt træ i plenum.

Materialer

#

• post6_instruktion.md — til dig som underviser
• post6_svar.md — svarark til den enkelte studerende (print ét pr. studerende)
• post6_svar_facit.md - udfyldt svarark til underviseren
• Blyanter

Tidsforbrug

#

Ca. 20–25 min. inkl. opbygning af træet og diskussion.

Modtagelse

#

Udvidelser

#

• Hvad sker der hvis alle fødselsdage er i januar? Træet degenererer til en LinkedList — O(n)
• Det er præcis derfor balancerede træer (AVL, Red-Black) findes

Noter til underviseren

#

• Byg træet hurtigt og pragmatisk — det behøver ikke være perfekt balanceret
• Spørgsmålet om skævt træ i svararket er broen til balancerede træer senere i faget
• Sletning er bevidst åbent formuleret — lad dem diskutere hvad der sker med børnene
• Det er en god ide at tegne træstrukturen på tavlen mens I bygger den fysisk
• Giv evt de studerende et udfyldt svarark til at tjekke deres egne svar med