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:
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.
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?
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: