binaire zoekboom

• Informatica
• Middelbare school
• havo
• Leerjaar 4

Leerdoelen

je kunt uitleggen waarom sommige vormen handiger zijn om mee te werken dan andere vormen

je weet hoe een binaire zoekboom werkt

kun je uitleggen wat een algoritme is

1 betekenis - meerdere vormen

We gaan dezelfde 10 getallen

in 2 verschillende representaties / vormen representeren

1. in een lijst
2. in een binaire zoekboom

Welke representatie is het handigst bij het zoeken?

1. Lijst representatie

10 getallen op een rij in een lijst

44, 10, 35, 43, 25, 7, 65, 73, 66, 45

Gegeven de representatie van 10 getallen in een lijst
44, 10, 35, 43, 25, 7, 65, 73, 66, 45
Hoeveel getallen moet je vergelijken met getal 45 om getal 45 in de lijst te vinden?

2. Binaire zoekboom representatie

10 getallen in een binaire zoekboom

44, 10, 35, 43, 25, 7, 65, 73, 66, 45

Algoritme

1. Plaats het eerste getal uit de lijst in de wortelknoop van de boom

2. Als het volgende getal uit de lijst kleiner is dan die in de boom, plaats het getal in de linker tak v/d boom

3. Als het volgende getal uit de lijst groter is dan die in de boom, plaats het getal in de rechter tak v/d boom

Herhaal voor alle getallen in de lijst

44, 10, 35, 43, 25, 7, 65, 73, 66, 45

Kleiner dan 44

links van 44

Groter dan 44

rechts van 44

Groter dan 10

rechts van 10

Definitie

Een algoritme is een handelingsvoorschrift:

dit beschrijft precies welke stappen je moet nemen voor het bereiken van het beoogde resultaat.

Maak een aantekening

1

2

2

3

3

4

5

6

7

8

9

10

44

10

35

43

25

7

65

73

66

45

Op zoek naar getal 45

Hoeveel vergelijkingen tussen een getal in de boom en het getal 45 dat je zoekt moet je maken om het getal te vinden?

< naar links

> naar rechts

begin bij de wortel

Op zoek naar getal 45

Hoeveel vergelijkingen tussen een getal in de boom en het getal 45 dat je zoekt moet je maken om het getal te vinden?

Vergelijking 1

45 is groter dan 44, dus zoek rechts verder

Vergelijking 2

45 is kleiner dan 65, dus zoek links verder

Vergelijking 3

45 is gelijk aan 45, dus gevonden

Gegeven de representatie van 10 getallen in de boomstructuur
Schrijf de vergelijkingen
en handelingen op om getal 35 te vinden?

De lijst en de binaire zoekboom bevatten precies dezelfde getallen.
Welke representatie is efficiënter bij het zoeken naar een getal?

1. De lijst
2. De binaire zoekboom
3. Weet ik niet
4. Geen verschil

Waarom is de binaire boom handiger om mee te werken dan de lijst?

Wat is een algoritme?

Leerdoelen

je kunt uitleggen waarom sommige vormen handiger zijn om mee te werken dan andere vormen

je weet hoe een binaire zoekboom werkt

kun je uitleggen wat een algoritme is