b"\n_START_ARTICLE_\nBinaire zoekboom\n_START_PARAGRAPH_\nEen 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._NEWLINE_Om effici\xc3\xabnt 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.\n_START_SECTION_\nZoeken in een binaire zoekboom\n_START_PARAGRAPH_\nBij 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._NEWLINE_Het algoritme voor het opzoeken van een waarde in een binaire zoekboom in pseudocode:_NEWLINE_ if zoekwaarde < waarde in knoop_NEWLINE_   then zoek in linkersubboom_NEWLINE_ else if zoekwaarde > waarde in knoop_NEWLINE_   then zoek in rechtersubboom_NEWLINE_ else if zoekwaarde == waarde in knoop_NEWLINE_   then return waarde_NEWLINE_ else if blad tegengekomen_NEWLINE_   then return niet gevonden\n_START_SECTION_\nEigenschap van een binaire zoekboom\n_START_PARAGRAPH_\nIn 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).\n_START_SECTION_\nGebalanceerdheid\n_START_PARAGRAPH_\nEen boom kan met de eigenschap hierboven een zoekboom zijn maar zich niet lenen voor effici\xc3\xabnt 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._NEWLINE_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).\n_START_SECTION_\nToevoegen van een nieuw element\n_START_PARAGRAPH_\nOm 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)._NEWLINE_In pseudocode wordt dit:_NEWLINE_ if invoegwaarde < waarde in knoop_NEWLINE_   then toevoegen in linkersubboom_NEWLINE_ else if invoegwaarde > waarde in knoop_NEWLINE_   then toevoegen in rechtersubboom_NEWLINE_ else if invoegwaarde == waarde in knoop_NEWLINE_   then toevoegen aan deze knoop (linker- of rechtersubboom is mogelijk)_NEWLINE_ else if blad tegengekomen_NEWLINE_   then hier toevoegen_NEWLINE_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\xc3\xabntie bij het zoeken. Het is daarom wenselijk dat men ervoor zorgt dat de boom die men oplevert na het toevoegen ook gebalanceerd is.\n_START_SECTION_\nEenvoudig sorteeralgoritme\n_START_PARAGRAPH_\nMen 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._NEWLINE_In pseudocode verloopt in-order traversal als volgt:_NEWLINE_ if er is een linkerkind_NEWLINE_   doorloop linkerboom met in-order traversal_NEWLINE_ verwerk element in huidige knoop (zoals tonen of een andere operatie)_NEWLINE_ if er is een rechterkind_NEWLINE_   doorloop rechterboom met in-order traversal_NEWLINE_Het sorteeralgoritme verloopt in pseudocode nu als volgt:_NEWLINE_ invoer = een ongesorteerde lijst O met n elementen_NEWLINE_ uitvoer = een gesorteerde lijst S met n elementen_NEWLINE__NEWLINE_ maak een zoekboom B_NEWLINE_ for each element e in O_NEWLINE_   voeg e in in zoekboom B_NEWLINE_ maak een lijst S_NEWLINE_ doorloop B met in-order traversal_NEWLINE_   per element: voeg inhoud van het element toe aan S_NEWLINE_ na afloop bevat S de elementen van O in gesorteerde volgorde_NEWLINE_In het slechtste geval heeft dit algoritme  nodig om de elementen te sorteren: als men een gesorteerde lijst als invoer geeft dan wordt een gelinkte lijst opgebouwd zonder linkerdeelbomen."