Een binaire boom is een vertakkende datastructuur waarin elk item, een knooppunt genoemd, naar beneden verwijst naar hoogstens twee andere knooppunten. Hij begint bij één bovenste knooppunt, de wortel, en spreidt uit als een omgekeerde boom. Elk knooppunt bevat een stukje data en wijst naar zijn linker- en rechterkind, als die er zijn. Die simpele twee-takkenregel blijkt een van de nuttigste vormen in software.
De duidelijkste vergelijking is een knock-outschema van een toernooi. De kampioen staat bovenaan, en daaronder splitst het schema zich keer op keer in tweeën, tot aan de eerste ronde. Om een uitslag te volgen loop je een pad van linker- en rechterkeuzes. Software doorloopt een binaire boom op dezelfde manier, laag voor laag met een breadth-first search of eerst helemaal langs één tak met een depth-first search.
Binaire bomen zie je overal: in snelle zoekstructuren, in hoe programma’s expressies interpreteren en in compressie. Voeg een ordeningsregel toe en je krijgt een binaire zoekboom, die data gesorteerd en snel doorzoekbaar houdt.
De reden dat developers steeds terugkeren naar de twee-takkenvorm, is dat die een probleem netjes in tweeën splitst. Bij elk knooppunt zijn er precies twee richtingen, en de meeste nuttige boombewerkingen leunen op dat simpele of-of. Compressieformaten bouwen een binaire boom om veelvoorkomende letters een korte code te geven en zeldzame een lange. Een rekenmachine zet ‘3 plus 4 keer 2’ om in een boom zodat de volgorde van bewerkingen klopt. Zelfs de manier waarop een spreadsheet een keten van formules herberekent, laat zich als boom modelleren. Niets daarvan handel je als ondernemer zelf af. Maar zodra je software geneste of gerangschikte data moet begrijpen, doet deze onopvallende vorm er vaak het zware werk onder.
Bij TopDevs leunen we op boomstructuren als de data van een klant van nature hiërarchisch is of snel doorlopen moet worden, zodat het juiste antwoord in een paar stappen terugkomt in plaats van met een trage zoektocht.
