Een binaire zoekboom is een manier om data te ordenen zodat zoeken, toevoegen en verwijderen snel blijven, ook als de verzameling enorm wordt. Elk item zit in een knooppunt met hoogstens twee takken. Alles wat kleiner is dan een knooppunt gaat de linkertak in, alles wat groter is de rechtertak. Die ene simpele regel zorgt dat je bij elke vergelijking de helft van wat overblijft kunt negeren.
Stel je een gesorteerde kaartenbak voor waarin je altijd in het midden begint. Zoek je ‘Müller’? Vergelijk met de middelste kaart, bepaal of die eerder of later komt, en je hebt zojuist de helft van de bak weggegooid zonder te kijken. Herhaal dat en je vindt elke naam in een paar stappen, zelfs in een bak van een miljoen kaarten. Het is een speciale binaire boom, en het snelheidsvoordeel is precies het logaritmische gedrag dat Big O-notatie beschrijft.
De adder is balans. Worden items in een ongelukkige volgorde toegevoegd, dan kan de boom scheef en traag worden, en daarom gebruiken productiesystemen vaak zelfbalancerende varianten. Maar het kernidee, halveer het probleem bij elke stap, maakt het zo houdbaar.
Waarom zou een ondernemer hier iets om geven? Omdat de keuze voor een structuur stilletjes bepaalt hoe je software aanvoelt. Zet dezelfde klantenlijst in een platte, ongesorteerde array en elke zoekopdracht moet vanaf het begin scannen, wat prima gaat bij honderd records en pijnlijk wordt bij honderdduizend. Zet je hem in een gebalanceerde zoekboom, dan blijft een zoekopdracht snel, hoe groot de lijst ook wordt. Je ziet de boom nooit. Je ziet alleen dat het zoekvak nog steeds direct antwoordt als het bedrijf tien keer zo groot is geworden. Dat soort beslissing maak je vroeg in een bouw en betaalt zich jarenlang terug, en het kost niets extra om het in één keer goed te doen.
Bij TopDevs grijpen we naar dit soort structuren als de data van een klant constant doorzocht moet worden, zodat het systeem snel blijft in plaats van trager te worden naarmate de records zich opstapelen.
