Boomstructuur - een datastructuur

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
1 / 26
suivant
Slide 1: Diapositive
InformaticaMiddelbare schoolhavo, vwoLeerjaar 4-6

Cette leçon contient 26 diapositives, avec quiz interactifs, diapositives de texte et 1 vidéo.

time-iconLa durée de la leçon est: 30 min

Éléments de cette leçon

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

Slide 1 - Diapositive

Cet élément n'a pas d'instructions

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


Slide 2 - Diapositive

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

Slide 3 - Diapositive

Cet élément n'a pas d'instructions

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

Slide 4 - Diapositive

Cet élément n'a pas d'instructions

Slide 5 - Vidéo

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

Slide 6 - Diapositive

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

Slide 7 - Diapositive

Cet élément n'a pas d'instructions

Kennismaken met een boomstructuur, deel 2

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

Slide 8 - Diapositive

Cet élément n'a pas d'instructions

Slide 9 - Diapositive

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

Slide 10 - Diapositive

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

Slide 11 - Diapositive

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?

Slide 12 - Diapositive

Geen pijlen, 14 tweemaal, 15 rechts van 17
Welke 2 fouten zitten hierin?

Slide 13 - Diapositive

18 tweemaal, 5 moet rechts van 3
Welke fout zit hierin?

Slide 14 - Diapositive

Ik zie geen fout!

Slide 15 - Diapositive

Cet élément n'a pas d'instructions

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)

Slide 16 - Diapositive

https://allesovercrypto.nl/blog/hash-simpele-uitleg
Een boom heeft 1 wortel, knopen (nodes) en takken. Elke knoop kan 2 takken hebben

Slide 17 - Diapositive

Cet élément n'a pas d'instructions

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.

Slide 18 - Diapositive

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

Slide 19 - Diapositive

Cet élément n'a pas d'instructions

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

Slide 20 - Diapositive

maximaal 7
In deze module leer je de volgende datastructuren:
Rij, lijst, boom

Slide 21 - Diapositive

Cet élément n'a pas d'instructions

Slide 22 - Diapositive

Cet élément n'a pas d'instructions

Wat is een datastructuur?

Slide 23 - Question ouverte

Cet élément n'a pas d'instructions

Wat is geen datastructuur?
A
Boom
B
Eindige automaat
C
Lijst
D
Rij

Slide 24 - Quiz

Cet élément n'a pas d'instructions

Een boomstructuur wordt gebruikt om....
A
Waardes te sorteren
B
In een verzameling waardes efficiënt te zoeken
C
Zoek-algoritmes te implementeren

Slide 25 - Quiz

Cet élément n'a pas d'instructions

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


Slide 26 - Diapositive

Zie volgende dia