Zoekboom
Van Wikipedia
Een zoekboom is een binaire boom met eigenschappen die er voor zorgen dat een waarde snel gevonden kan worden. In een zoekboom heeft elke knoop maximaal twee verwijzingen naar een andere knoop. Verder heeft elke knoop in de zoekboom 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 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.
Inhoud |
[bewerk] Zoeken in een zoekboom
Bij het opzoeken van een waarde in een 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 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
[bewerk] Eigenschappen bij het zoeken
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.
[bewerk] Eigenschap van een 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).
[bewerk] 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 maar een kleine (of geen) subboom wordt 'weggedaan'. 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).
[bewerk] 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 inzit 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 één 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 er voor zorgt dat de boom die men oplevert na het toevoegen ook gebalanceerd is.
[bewerk] 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 verwijdert 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):
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.
