Binaire zoekboom

Een binaire zoekboom is een binaire boom met eigenschappen die ervoor zorgen dat een waarde snel gevonden kan worden. In een binaire zoekboom verwijst elke knoop naar maximaal twee andere knopen. Verder heeft elke knoop in de boom de eigenschap dat alle waarden in de linker subboom kleiner of gelijk zijn dan de waarde in de knoop en alle waarden in de rechtersubboom groter of gelijk dan de waarde in de knoop.

Om efficiënt te kunnen zoeken dient de boom ook gebalanceerd te zijn; dit wil zeggen dat de subbomen van een knoop zo veel mogelijk even diep zijn. Bij een scheefgegroeide boom (niet gebalanceerde boom) is de tijdwinst voor bewerkingen kleiner dan een gebalanceerde boom aangezien er (veel) meer waarden in knopen bekeken moet worden om te weten of een waarde in de boom te vinden is.

Zoeken in een binaire zoekboom

Bij het opzoeken van een waarde in een binaire zoekboom begint men bij de wortel van de boom. Afhankelijk van de waarde in die knoop gaat men verder zoeken in de linker- of rechtersubboom. Dit wordt herhaald tot men de waarde vindt of wanneer men bij een blad gekomen is.

Het algoritme voor het opzoeken van een waarde in een binaire zoekboom in pseudocode:

 if zoekwaarde < waarde in knoop
   then zoek in linkersubboom
 else if zoekwaarde > waarde in knoop
   then zoek in rechtersubboom
 else if zoekwaarde == waarde in knoop
   then return waarde
 else if blad tegengekomen
   then return niet gevonden

Eigenschappen bij het zoeken

Een niet-gebalanceerde zoekboom

Dezelfde wel gebalanceerde zoekboom

De volgende twee eigenschappen beïnvloeden het zoekproces:

Waarden in linkersubboom kleiner of gelijk aan waarde in knoop en waarden in rechtersubboom groter of gelijk aan waarde in knoop (eigenschap van een zoekboom)
Gebalanceerdheid (de subbomen van een knoop zijn zo veel mogelijk even diep)

De eerste eigenschap is een vereiste want anders is de boom geen zoekboom (en zonder die eigenschap kunnen ook geen uitspraken gedaan worden of men verder moet zoeken in de linker- of rechtersubboom). De tweede eigenschap is geen vereiste maar maakt het zoeken wel efficiënter.

Eigenschap van een binaire zoekboom

In het optimale geval zorgt deze eigenschap per knoop voor een halvering van het aantal knopen dat nog bekeken moet worden. Als een waarde groter of kleiner is dan de waarde in een knoop dan is bekend in welke subboom verder gezocht moet worden. De andere subboom hoeft niet meer bekeken te worden. Dit kan alleen wanneer de boom voldoet aan deze eigenschap (bij bijvoorbeeld het toevoegen van nieuwe knopen moet hiermee dus rekening gehouden worden).

Gebalanceerdheid

Een boom kan met de eigenschap hierboven een zoekboom zijn maar zich niet lenen voor efficiënt zoeken. Het is namelijk mogelijk dat bij elke stap in het opzoekingsproces maar een kleine (of geen) deelboom wordt uitgesloten. Hoe meer een zoekboom (of een deel ervan) is scheefgegroeid, hoe meer knopen vergeleken moeten worden. Zie de afbeeldingen hiernaast voor een niet en een wel gebalanceerde boom.

Om de waarde '12' in de niet gebalanceerde zoekboom te vinden, moeten de knopen '50', '17', '9' en '14' eerst bekeken worden om uiteindelijk '12' tegen te komen. In de gebalanceerde zoekboom zijn de knopen met hun kinderen beter gekozen waardoor het opzoeken van de waarde '12' sneller gaat: na '50' en '17' is deze gevonden. Ook het concluderen dat een waarde niet in de zoekboom aanwezig is, gaat in een gebalanceerde zoekboom sneller (vergelijk bijvoorbeeld het opzoeken van '11' in beide bomen).

Toevoegen van een nieuw element

Om een nieuw element toe te voegen aan de zoekboom beginnen we eerst met het zoeken naar dat element in de zoekboom (dit verloopt zoals hierboven beschreven). Als het element er niet in zit dan komen we bij een blad uit en op die plaats kan het nieuwe element toegevoegd worden. Als we het element wel tegenkomen dan wordt het element aan een van de subbomen toegevoegd (zowel de linker- als rechtersubboom is toegestaan aangezien de eigenschap van de zoekboom in beide gevallen behouden blijft).

In pseudocode wordt dit:

 if invoegwaarde < waarde in knoop
   then toevoegen in linkersubboom
 else if invoegwaarde > waarde in knoop
   then toevoegen in rechtersubboom
 else if invoegwaarde == waarde in knoop
   then toevoegen aan deze knoop (linker- of rechtersubboom is mogelijk)
 else if blad tegengekomen
   then hier toevoegen

Deze manier van toevoegen zorgt ervoor dat het een zoekboom blijft maar op den duur kan dit resulteren in een ongebalanceerde boom. In het slechtste geval worden nieuwe elementen telkens aan dezelfde subboom toegevoegd waardoor de diepte daar telkens toeneemt. Dit zorgt voor een slechte efficiëntie bij het zoeken. Het is daarom wenselijk dat men ervoor zorgt dat de boom die men oplevert na het toevoegen ook gebalanceerd is.

Verwijderen van een knoop

Er zijn drie mogelijkheden bij het verwijderen van een element uit de zoekboom:

Verwijderen van een blad: We verwijderen simpelweg het blad uit de boom.
Verwijderen van een knoop met één kind: We verwijderen de knoop en het kind komt op diezelfde plaats.
Verwijderen van een knoop met twee kinderen: Stel dat knoop $N$ verwijderd moet worden. We vervangen dan de waarde van $N$ met de eerstvolgende opvolgende waarde (dit is het meest linker kind in de rechtersubboom) of met de eerste waarde net voor $N$ (dit is het meest rechter kind in de linkersubboom).

Ter illustratie verwijderen we de knoop met waarde 7 uit de onderstaande boom. Als we deze vervangen door de knoop met waarde 6 dan krijgen we de linkersituatie waar de subboom die eerst onder 6 hing nu op de plaats van 6 staat. De knoop met waarde 7 is verwijderd en vervangen door de knoop met waarde 6. In de rechtersituatie is het vergelijkbaar maar dan is de knoop met waarde 7 vervangen door de eerste knoop met een hogere waarde (in dit geval de knoop met waarde 9):

Het verwijderen van de knoop met waarde 7

Zodra we de knoop met een waarde net voor of net na knoop $N$ hebben gevonden, wisselen we deze om met $N$ en verwijderen we die knoop. Aangezien beide van die twee knopen minder dan twee kinderen hebben (anders kunnen ze niet een voorganger of opvolger van $N$ zijn), kan die knoop verwijderd worden op een eerder genoemde manier. Een goede implementatie zorgt er ook voor dat niet telkens dezelfde knoop (bijvoorbeeld telkens de opvolger van $N$ ) wordt verwijderd want dit kan resulteren in een ongebalanceerde boom.

Eenvoudig sorteeralgoritme

Men kan een binaire zoekboom gebruiken om een eenvoudig sorteeralgoritme te implementeren. Een lijst elementen, zoals getallen, kan in een zoekboom ingevoegd worden en vervolgens kan men de zoekboom van klein naar groot doorlopen. Dit komt overeen met een in-order traversal van de binaire zoekboom.

In pseudocode verloopt in-order traversal als volgt:

 if er is een linkerkind
   doorloop linkerboom met in-order traversal
 verwerk element in huidige knoop (zoals tonen of een andere operatie)
 if er is een rechterkind
   doorloop rechterboom met in-order traversal

Het sorteeralgoritme verloopt in pseudocode nu als volgt:

 invoer = een ongesorteerde lijst O met n elementen
 uitvoer = een gesorteerde lijst S met n elementen

 maak een zoekboom B
 for each element e in O
   voeg e in in zoekboom B
 maak een lijst S
 doorloop B met in-order traversal
   per element: voeg inhoud van het element toe aan S
 na afloop bevat S de elementen van O in gesorteerde volgorde

In het slechtste geval heeft dit algoritme $\Theta (n^{2})$ nodig om de elementen te sorteren: als men een gesorteerde lijst als invoer geeft dan wordt een gelinkte lijst opgebouwd zonder linkerdeelbomen.