## Binaire zoekbomen

Binaire Zoekboom

Een binaire zoekboom (Binary Search Tree, BST) is een datastructuur die de efficiënte organisatie en toegang tot gegevens mogelijk maakt. Hier is hoe een BST werkt en wat de belangrijkste eigenschappen zijn:

Basisprincipes van een Binaire Zoekboom:

1. Structuur:
   - Elke knoop in de boom heeft maximaal twee kinderen: een linker en een rechter kind.
   - In een binaire zoekboom is het maximum van de waarden in de linker subboom kleiner dan de waarde in de knoop zelf; het minimum van de waarden in de rechter subboom is ten minste (>=) de waarde in de knoop zelf..
2. Zoekproces:
   - Stap 1: Begin bij de wortel (root) van de boom.
   - Stap 2: Vergelijk de waarde die je zoekt met de waarde in de wortel.
     - Als de waarde gelijk is, ben je klaar.
     - Als de waarde kleiner is, herhaal het proces in de linker subboom.
     - Als de waarde groter is, herhaal het proces in de rechter subboom.
   - Dit proces herhaalt zich totdat je de gezochte waarde vindt of bij een bladknoop aankomt (een knoop zonder kinderen).
3. Zoeken en Efficiëntie:
   - Het zoeken in een BST is efficiënt als de boom gebalanceerd is. Dit betekent dat het aantal knopen in de linker en rechter subbomen van elke knoop ongeveer gelijk is.
   - In een gebalanceerde BST is het aantal stappen dat nodig is om een waarde te vinden ongeveer gelijk aan de hoogte van de boom, wat log (N). Hier staat N voor het aantal knopen in de boom.

Uitleg gebalanceerde zoekboom:

Een gebalanceerde binaire zoekboom (of balanced binary search tree, BST) is een datastructuur die ervoor zorgt dat gegevens op zo’n manier worden opgeslagen dat je er efficiënt in kunt zoeken, invoegen en verwijderen. Laten we dat stap voor stap toelichten:

Zoals gezien is een binaire zoekboom een boomstructuur waarin elke knoop (node) maximaal twee kinderen heeft: een linker en een rechter.

- De linkerkinderen bevatten waarden kleiner dan de ouder.
- De rechterkinderen bevatten waarden groter dan de ouder.

Bijvoorbeeld, als je 5 in de boom stopt, en daarna 3 en 7:

Wat betekent "gebalanceerd"?

Een binaire zoekboom is gebalanceerd als de hoogte van de boom ongeveer zo klein mogelijk is. Dit betekent dat het verschil in diepte tussen de linker- en rechter-subboom bij elke knoop klein is, meestal maximaal 1 of 2 niveaus verschil (afhankelijk van het type balansregel).

Waarom is dit belangrijk?

- Omdat de hoogte van de boom bepaalt hoe snel je kunt zoeken.
- Hoe lager de boom, hoe minder stappen je nodig hebt om een element te vinden (O(log n) tijd in het beste geval).

Voorbeeld van een ongebalanceerde boom

Als je getallen in oplopende volgorde invoegt, krijg je:

Dit is niet gebalanceerd – hij lijkt meer op een lijst, en zoeken duurt langer (O(n)).

Voorbeeld van een gebalanceerde boom

Als je dezelfde getallen anders organiseert:

Dan is de boom veel evenwichtiger, en zoekoperaties zijn sneller.

Samengevat

Een gebalanceerde binaire zoekboom is een datastructuur die:
In elke knoop een waarde heeft met een linkerkind (<) en rechterkind (>),
Zichzelf in balans houdt zodat zoeken snel blijft (meestal O(log n)).

Het Concept van 2log (N)

Kleine toelichting op het concept van 2log (N):

Logaritme in Basis 2:

- - Het logaritme in basis 2 (log2​) van een getal N is de macht waartoe je 2 moet verheffen om N te krijgen.
    Bijvoorbeeld, log2(1024) = 10 omdat 210 = 1024.