Wat is een binaire boom?

Een binaire boom is een type gegevensstructuur die wordt gebruikt bij computerprogrammering om informatie op te slaan, te sorteren en te toegang krijgen.Binaire bomen zijn de eenvoudigste verscheidenheid aan boom, maar zijn zeer nuttig en gemakkelijk te implementeren.Een typische implementatie van een binaire boom is gebaseerd op een rootknooppunt gekoppeld aan een reeks knooppunten die de boom zelf vormen door pointervariabelen.Dit type boom ontleent zijn naam aan het feit dat geen enkel knooppunt in de boom meer dan twee kinderen kan hebben.

Boomgegevensstructuren zijn er in vele variëteiten.Ze bestaan uit verschillende knooppunten, die in een hiërarchisch patroon zijn georganiseerd.Een enkel knooppunt, de root, is het toegangspunt waardoor de hele gegevensboom kan worden doorzocht of anderszins kan worden gemanipuleerd.Dit rootknooppunt verwijst naar het bovenste knooppunt in de boom zelf.

Elk knooppunt in een boom, behalve voor het bovenste knooppunt, heeft een bovenliggende knooppunt dat zich erboven bevindt in de hiërarchie van de boom.Het kan ook kinderknooppunten hebben, die zich eronder bevinden.Een gegeven knooppunt is toegankelijk via die erboven in de boom en biedt toegang tot die eronder.

Binaire boomgegevensstructuren zorgen ervoor dat elke knooppunt niet meer dan twee kinderen heeft.Een bepaald knooppunt kan dus nul-, één- of twee kinderknooppunten hebben bevestigd.Gewone binaire bomen staan knooppunten toe met een willekeurig aantal kinderen op elk punt in de boom.Ze leggen ook geen beperkingen op hoe de waarden die zijn opgeslagen in knooppunten die een boom omvatten zijn gerangschikt.

Gegevensstructuren zijn het meest nuttig wanneer ze de snelheid verbeteren waarmee gegevens toegankelijk zijn door een computer, en gemodificeerde versies van binaire bomen worden gebruikthun efficiëntie verbeteren.Een binaire zoekboom is er een waarin alle gegevenswaarden die zich op de linker afdalende tak van een gegeven knooppunt bevinden, waarden hebben die gelijk zijn aan of minder dan de waarde die in dat knooppunt is opgeslagen.Waarden aan de rechterkant van een knooppunt in een geordende binaire boom moeten op zijn beurt groter zijn dan de waarde in het basisknooppunt.Met deze gegevensopdracht kan een veel efficiënter zoekalgoritme worden geschreven.

De vorm van een binaire boom is ook belangrijk bij het bepalen van de efficiëntie van een zoekalgoritme.De minst efficiënte variëteit van een binaire boom is er een waarin elk knooppunt slechts één kind heeft.Een computer moet mogelijk elk gegevensitem in de hele boom onderzoeken om een enkel stuk informatie in deze configuratie te vinden.De meest efficiënte binaire boom daarentegen is er een waarin elk knooppunt speet voor die aan de onderkant van de boom twee kinderen heeft en waar alle bladknooppunten, de onderste knooppunten in de boom, dezelfde afstand van de wortel bevinden.