## Binaire zoekbomen

Als we de elementen in een boom op een handige manier organiseren, dan kunnen we hierin efficiënt zoeken.
Een binaire boom is een boom waarbij elke knoop 2 subbomen heeft: een linker- en een rechter subboom. Hierbij kan een subboom leeg zijn.
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.
Voorbeeld van een binaire zoekboom:

Binaire zoekboom

In een dergelijke boom kunnen we efficiënt zoeken: het aantal zoekstappen is ongeveer 2log(N)2log(N). Dit is eigenlijk een vorm van binair zoeken (Binary Search); in het gedeelte over Zoeken en sorteren gaan we daar verder op in. Je zoekt in een binaire zoekboom op de volgende manier:

- als de waarde die je zoekt gelijk is aan de waarde in de wortel, dan ben je klaar;
- als de waarde die je zoekt kleiner is dan de waarde in de wortel, dan zoek je op dezelfde manier met de linker subboom als wortel;
- als de waarde die je zoekt groter is dan de waarde in de wortel, dan zoek je op dezelfde manier met de rechter subboom als wortel.

Je krijgt op deze manier een pad van de wortel naar de uiteindelijke knoop met de gezochte waarde. Dit pad kun je ook gebruiken voor het identificeren van de plek van de knoop in de boom.
Het zoekproces in een binaire zoekboom is alleen efficiënt als de boom redelijk gebalanceerd is: voor elke subboom is dan het aantal knopen links en rechts ongeveer gelijk. De hoogte van de boom is dan ongeveer 2log(N)2log(N), waarbij N het aantal knopen in de boom is.
Voorbeeld: voor 1000 knopen is de hoogte ongeveer 10 (210=1024210=1024).

#### Links

- Visualisatie van een binaire zoekboom
- Wikipedia: binaire zoekboom