Boomstructuur - een datastructuur

• Informatica
• Middelbare school
• havo, vwo
• Leerjaar 4-6

Kennismaken met een boomstructuur, deel 1

Een boomstructuur wordt vaak gebruikt om zoek-algoritmes efficiënt te implementeren

Opdracht: Je maakt zelf een boomstructuur van een leuk item en van random getallen

Een datastructuur is een manier om data te ordenen. Hoe gegevens geordend worden, bepaalt mede hoe efficiënt een algoritme kan zijn.

Een boomstructuur is een datastructuur, die gebruikt wordt om efficiënt te zoeken in grote hoeveelheden data

Misschien even de link naar SLO openen en laten zien over datastructuren

Een goed voorbeeld van een boomstructuur is de organisatie van bestanden en mappen op je computer.

Een ander voorbeeld is een boek: De hoofdstukken en secties zijn georganiseerd in een boomstructuur

Een boom heeft een recursieve structuur: 1 of meer delen hebben dezelfde structuur als het geheel

leuke video: https://youtu.be/ikPPdBDZnz4

De opdracht erbij kan zijn: Verzin een item wat je koopt en teken hier een boomstructuur van, in de video worden auto's gebruikt

Termen: Root = wortel; Takken = edges; Knopen = nodes; Bladeren = leaves = eindknopen

Deze opdracht laten maken in Google presentaties, met een eigen gekozen onderwerp, dat werkte erg goed, lekker makkelijk. Daarna een random rij laten genereren, dat konden ze goed aan. En voorbeelden met fouten laten maken, ook dat vonden ze leuk om te doen

Opdracht: Maak zelf een boomstructuur in een Google-presentatie

Kies een item wat je leuk vindt en wat je kunt onderverdelen: Dat wordt de root = wortel

Maak subcategorieën.

Zorg voor minstens 1 pad van 3 pijlen

Minstens 1 knoop of node heeft 2 eindbladeren.

Van de eindknoppen zoek je afbeeldingen, die je toevoegt.

Schrijf de volgende termen erbij: Root, tak, hoogte, blad, knoop

Kennismaken met een boomstructuur, deel 2

Opdracht: Je genereert een random rij getallen en maakt hier een boomstructuur van 

Binary search kan ook weergegeven worden in een boomstructuur

We gaan van de volgende rij een boomstructuur maken:

15  7  17  16  12  9  16  0  14   8

1. Neem het 1e element: Hier 15, dat wordt de root (=wortel)
2. Elk element mag maximaal 2 kinderen hebben
3. Neem steeds het volgende element:
4. Zoek het knooppunt waar je dit in moet voegen. Is het groter dan de knoop, zet het dan rechts, anders links.
5. Het nieuwe element komt aan het einde van een tak
6. Heeft een knoop al 2 kinderen, dan breid je de boom uit
7.  Herhaal vanaf stap 4 tot alle elementen in de boom zitten

Doe dit zelf met een random rij, met RandomRij.fprg

Als de structuur gemaakt is, kan dit gebruikt worden voor zoekalgoritmes. Bv om een key te zoeken, of het minimum/maximum

15 7 17 16 12 9 16 0 14 8

Voorbereiding toets:

Neem de rij rechts als uitgangspunt. Pas quicksort toe. Hoeveel stappen tot het gesorteerd is?

Dan dezelfde rij en maak daar een boom van. Hoeveel stappen nu?

gebruik Flowgorithm om een eigen rij te maken.

Welke 3 fouten zie je hier?

Geen pijlen, 14 tweemaal, 15 rechts van 17

Welke 2 fouten zitten hierin?

18 tweemaal, 5 moet rechts van 3

Welke fout zit hierin?

Ik zie geen fout!

Wanneer wordt een boomstructuur gebruikt? In mappen, of bv om een game-situatie te implementeren.

Bij cryptocurrency wordt ook een boom gebruikt, de Merkle tree. Deze pagina vertelt over cryptocurrency en hashing (onderdeel van security)

https://allesovercrypto.nl/blog/hash-simpele-uitleg

Een boom heeft 1 wortel, knopen (nodes) en takken. Elke knoop kan 2 takken hebben

De paden in een boom, zoals bij de bestanden en mappen op je computer, worden weergegeven in een boomstructuur.

We gaan hier even naar kijken, via deze en de opdracht op deze pagina.

Als je bv. een website gaat maken in HTML, zul je moeten weten waar een bestand (web-pagina) zich bevindt en het pad op moeten kunnen geven.

https://maken.wikiwijs.nl/157978#!page-5854586

https://maken.wikiwijs.nl/157978#!page-5854590

De root wordt altijd aangegeven met /, hoever weg hij ook is. Stel dat je in map e 'zit' , dan kun je bij bestand b.txt via: /a/b.txt

Een zoekspel, waar je al kennis mee hebt gemaakt: Binary search: In hoeveel stappen kun je een willekeurig getal raden?

Bv. tussen 1 en 100

Om efficiënt te kunnen zoeken, wordt gebruik gemaakt van een boomstructuur. Dit noem je een datastructuur

Een datastructuur is een manier om gegevens te ordenen

maximaal 7

In deze module leer je de volgende datastructuren:

Rij, lijst, boom

Wat is een datastructuur?

Wat is geen datastructuur?

1. Boom
2. Eindige automaat
3. Lijst
4. Rij

Een boomstructuur wordt gebruikt om....

1. Waardes te sorteren
2. In een verzameling waardes efficiënt te zoeken
3. Zoek-algoritmes te implementeren

Dit algoritme hebben we uitgevoerd. Nu gaan we dit verwerken in een datastructuur

Zie volgende dia