Wat is een binaire boom?

Een binaire structuur is een type gegevensstructuur die wordt gebruikt in computerprogrammering om informatie op te slaan, te sorteren en te openen. Binaire bomen zijn de eenvoudigste variëteit van boom, maar zijn zeer nuttig en gemakkelijk te implementeren. Een typische implementatie van een binaire boom is afhankelijk van een wortelknooppunt 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 varianten. 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 gemanipuleerd. Deze wortelknoop wijst naar de bovenste knoop in de boom zelf.

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

Met binaire boomgegevensstructuren kan elk knooppunt niet meer dan twee kinderen hebben. Een gegeven knooppunt kan dus nul, één of twee kinderknooppunten hebben. Gewone binaire bomen staan ​​knooppunten toe met een willekeurig aantal kinderen op elk punt in de boom. Ze stellen ook geen beperkingen aan hoe de waarden die zijn opgeslagen in knooppunten die een boom vormen, zijn gerangschikt.

Gegevensstructuren zijn het meest nuttig wanneer ze de snelheid verbeteren waarmee gegevens door een computer kunnen worden benaderd, en aangepaste versies van binaire bomen worden gebruikt om hun efficiëntie te verbeteren. Een binaire zoekboom is een boom waarin alle gegevenswaarden die zich op de linker aflopende tak van een bepaalde knoop bevinden waarden hebben die gelijk zijn aan of kleiner zijn dan de waarde die in die knoop is opgeslagen. Waarden aan de rechterkant van een knooppunt in een geordende binaire boom moeten op hun beurt groter zijn dan de waarde in het basisknooppunt. Met deze gegevensvolgorde 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 elke knoop slechts een enkel kind heeft. Een computer moet mogelijk elk gegevensitem in de hele structuur onderzoeken om een ​​enkel stukje informatie in deze configuratie te vinden. De meest efficiënte binaire boom, daarentegen, is er een waarin elke knoop behalve voor degenen aan de onderkant van de boom twee kinderen heeft en waarbij alle bladknopen, de onderste knopen in de boom, zich op dezelfde afstand van de wortel bevinden.