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:

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=1024 of 2^10=1024).

Links