Naar inhoud
BetaAI Begrippen

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

Binaire boom

Engels: Binary tree · Ook wel: binary tree

In het kort

Een binaire boom (binary tree) is een gegevensstructuur waarin elk punt hoogstens twee kinderen heeft. Anders dan een gewone lijst kan elk punt hier naar links en naar rechts verder vertakken, en elke tak is zelf weer een binaire boom of leeg. Programma's leggen zo keuzes of gegevens vast en volgen daarna één tak per stap, bijvoorbeeld bij een ja-of-neevraag in een beslisschema.

Waarom is dit belangrijk?

Programma's kunnen met een binaire boom grote hoeveelheden gegevens sneller doorzoeken en sorteren dan wanneer zij elk gegeven apart moeten bekijken. In de wetenschap gebruiken onderzoekers deze vorm voor stambomen die laten zien welke soorten aan elkaar verwant zijn. Studenten en programmeurs komen deze opbouw tegen in software op school en op het werk, maar een scheve boom maakt zoeken traag en kost meer geheugen.

Zo werkt het in de praktijk

Huffman-codering bouwt een binaire boom zodat PKZIP, JPEG en MP3 veelvoorkomende tekens een korte code geven. Een studie van de Amerikaanse luchtmacht beschrijft vluchtsimulatoren met een boom voor binary space partitioning. De spelmotoren van Doom en Quake delen de ruimte daarmee in tweeën.

David Huffman zocht aan het MIT de kortste binaire code. Hij bouwde de boom van onderaf en bewees in 1952 dat dit de kortste code geeft. Henry Fuchs onderzocht hoe een BSP-boom vlakken in een 3D-scène ordent.

In CAD hoort de BSP-boom bij constructive solid geometry (vormen combineren met verzamelingen). Huffman-codering leest een prefixcode af langs de takken van de boom. Het leerboek Computer Graphics: Principles and Practice beschrijft de BSP-boom als werkwijze voor vlakken.

Bron: en.wikipedia.org

Gecontroleerd op 23 oktober 2026