Eenzoekboom in deinformatica is eenboomstructuur die gebruikt wordt voor het vinden van specifieke waarden uit een verzameling. Een belangrijke eigenschap die een zoekboom van een gewone boom onderscheidt is het gegeven dat de waarde van een top groter moet zijn dan de waarden in de linkersubboom en kleiner dan de waarden in de rechtersubboom.^[1]

Het voordeel van zoekbomen is hun efficiënte zoekoperatie, gegeven dat de boom redelijk gebalanceerd is. Dit wil zeggen dat de bladeren van de boom allemaal ongeveer even diep zitten. Er bestaan verschillende soorten zoekbomen; verschillende soorten hebben ook efficiënte toevoeg- en verwijderoperaties.

Zoekbomen worden vaak gebruikt om eenassociatieve array te implementeren. Dit kan door de sleutels van de sleutel/waarden-paren uit de array te gebruiken als waarden voor de toppen in de boom.

ZieBinaire zoekboom voor het hoofdartikel over dit onderwerp.

Een binaire zoekboom is een zoekboom waarbij elke top hoogstens twee kinderen heeft. De linkerdeelboom bevat alle waarden die kleiner zijn dan de waarde van de huidige top, terwijl de rechterdeelboom alle grotere waarden bevat.

Het slechtste geval qua tijdscomplexiteit voor het opzoeken in een binaire zoekboom is de diepte van de boom. In het optimale geval, bij een gebalanceerde boom, gaat het om${\displaystyle \mathrm{O}(\log n)}$ voor een boom met${\displaystyle n}$ elementen.

B-bomen zijn een generalisatie van binaire zoekbomen, waarbij een top een variabel aantal kinderen kan hebben. Hoewel het bereik van de kinderen vastligt, zijn deze kinderen niet altijd aanwezig. Hierdoor is het mogelijk dat B-bomen wat geheugen kunnen verspillen. Het voordeel is dan dat B-bomen niet zo vaak opnieuw gebalanceerd moeten worden als anderezelfbalancerende bomen.

Vanwege het variabele bereik van hun toppen zijn B-bomen geoptimaliseerd voor het lezen van grote blokken data. Ze worden ook vaak gebruikt indatabanken.

Een${\displaystyle (a,b)}$-boom is een zoekboom waarvan alle bladeren dezelfde diepte hebben. Elke top heeft minstens${\displaystyle a}$ en maximaal${\displaystyle b}$ kinderen, terwijl de wortel tussen 2 en${\displaystyle b}$ kinderen heeft. De waarden voor a en b kunnen bepaald worden met volgende formule:^[2]

${\displaystyle 2\le a\le \frac{(b+1)}{2}}$

Een trie is een categorie zoekbomen, waarbij de waarden meestaltekenreeksen zijn. Ook typerend is dat toppen geen waarde opslaan; de positie in de boom definieert de waarde van de top. Onder tries vallen o.a. ooksuffixbomen enradixbomen.

Een intervalboom is een zoekboom die gebruikt wordt omintervallen op te slaan. Het laat toe om op efficiënte wijze alle intervallen die overlappen met een gegeven interval of punt te vinden. Deze soort (en zijn varianten) wordt vaak gebruikt bij ruimtelijke problemen, zoals het vinden van alle straten binnen een bepaald vierkant op een kaart.

• Datastructuur
• Boom (datastructuur)

• Boom (datastructuur)

• Wikipedia:Onbereikbare externe link