Naar inhoud
BetaAI Begrippen

AI-begrippen in gewone taal. Zoek een begrip, blader op letter of filter op onderwerp.

Tree traversal

Engels: Tree traversal · Ook wel: tree walk, tree walking, boomdoorloop

In het kort

Het doorlopen van een boom is een methode die elk onderdeel precies één keer controleert of bijwerkt. Die onderdelen hangen via takken aan elkaar, anders dan gegevens in een rechte lijst, en een programma bezoekt ze in een vaste volgorde, eerst diep of eerst breed. Die volgorde bepaalt welk onderdeel het programma eerst leest of aanpast, zoals een keuze in een beslisboom.

Waarom is dit belangrijk?

Door een rekenformule als boom te behandelen, kan een programma die formule omzetten naar eenvoudige rekenstappen. In de wetenschap helpt het doorlopen van een boom om in een stamboom van soorten te bepalen welke soort dichter bij een andere staat. Op school en in softwarewerk stuurt die route welk resultaat een programma berekent, terwijl een grote boom veel rekentijd en geheugen vraagt.

Zo werkt het in de praktijk

Een programma doorloopt een boom om een kopie te maken of om de boom te wissen. Bij een kopie komt de bovenste knoop eerst, bij wissen komen de lagere knopen eerst vrij. Monte Carlo tree search bekijkt met steekproeven takken met kansrijke zetten.

Onderzoek naar deze volgorde zoekt de kortste route tussen twee punten, geteld in stappen. Edward Moore zocht in 1959 met een brede volgorde de uitgang van een doolhof. C. Y. Lee zette dat in 1961 om tot een methode voor draadroutes.

In softwarewerk hoort dit bij het algoritme van Cheney. Dat algoritme kopieert bereikbaar geheugen in een brede ronde en maakt ongebruikt geheugen vrij. Dezelfde ronde bouwt de foutfunctie van Aho-Corasick, een zoeker voor meerdere woorden tegelijk.

Bron: en.wikipedia.org

Gecontroleerd op 5 november 2026