Zoekboom

Een zoekboom in de informatica is een boomstructuur 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.

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 een associatieve 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.

Soorten zoekbomen

Binaire zoekboom

Een binaire zoekboom

Zie Binaire 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 $\mathrm {O} (\log n)$ voor een boom met $n$ elementen.

B-boom

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 andere zelfbalancerende bomen.

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

(a, b)-boom

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

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

Trie

Een voorbeeld van een trie voor waarden "A", "to", "tea", "ted", "ten", "i", "in" en "inn". Merk op dat in dit voorbeeld niet alle kinderen gesorteerd zijn zoals zou moeten (het kind "t" van de wortel)

Een trie is een categorie zoekbomen, waarbij de waarden meestal tekenreeksen 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. ook suffixbomen en radixbomen.

Intervalboom

Een intervalboom is een zoekboom die gebruikt wordt om intervallen 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.

Zie ook

• Datastructuur
• Boom (datastructuur)