Een beginnershandleiding voor binaire bomen

Als je een cursus datastructuren hebt gevolgd in je computerwetenschappen, of een autodidactische programmeur bent, is de kans groot dat je de term 'binaire bomen' bent tegengekomen. Hoewel ze misschien een beetje overweldigend en complex klinken, is het concept van een binaire boom vrij eenvoudig.

Lees verder terwijl we binaire bomen ontleden en waarom ze een noodzakelijk kernconcept zijn voor programmeurs.

Wat zijn binaire bomen?

Binaire bomen behoren tot een van de eerste datastructuren die studenten leren in een cursus datastructuren. Een binaire boom bestaat uit vele knooppunten en elk knooppunt van de binaire boom bevat twee wijzers die de linker en rechter onderliggende gegevensknooppunten aangeven.

Het eerste knooppunt in een binaire boom wordt de "root" genoemd. Knopen van het laatste niveau in een boom worden bladeren genoemd.

Elk knooppunt bevat een gegevensitem en twee knooppuntwijzers. Een lege binaire boom wordt weergegeven door een null-pointer. Zoals je misschien al hebt ontdekt, kunnen binaire bomen slechts twee kinderen hebben (vandaar de naam).

Soorten binaire boomstructuren

Er zijn verschillende binaire boomstructuren, afhankelijk van de manier waarop de knooppunten zijn gepositioneerd. Een binaire boom wordt een volledige binaire boom genoemd wanneer elk knooppunt in de boom nul of twee kinderen heeft. In een perfecte binaire boom hebben alle knooppunten twee kinderen en zijn de bladeren allemaal op dezelfde diepte.

Verwant: De beste manieren om gratis te leren coderen

Een complete binaire boom heeft knopen die op elk niveau zijn ingevuld, met uitzondering van het laatste niveau. In volledige binaire bomen zijn knooppunten geconcentreerd aan de linkerkant van de wortel. Een andere veel voorkomende structuur is een evenwichtige binaire boom; in deze structuur mogen de hoogten van de rechter en linker deelbomen hoogstens één verschillen. Het is ook vereist dat de linker- en rechtersubbomen ook in evenwicht moeten zijn.

Het is belangrijk op te merken dat de hoogte van de gebalanceerde binaire boom O(logn) is, waarbij n het aantal knopen in de boom is.

In sommige gevallen, als elk knooppunt slechts één linker- of rechterkind heeft, kan de binaire boom een ​​scheve binaire boom worden. Het zal zich dan gedragen als een gekoppelde lijst, dergelijke bomen worden ook wel een gedegenereerde boom genoemd.

Wat zijn binaire zoekbomen?

Een binaire zoekboom (BST) is in wezen een geordende binaire boom met een speciale eigenschap die bekend staat als de eigenschap "binaire zoekboom". De BST-eigenschap betekent dat knooppunten met een sleutelwaarde kleiner dan de root in de linker substructuur worden geplaatst en dat knooppunten met een sleutelwaarde groter dan de root deel uitmaken van de rechter substructuur.

De eigenschap BST moet waar zijn voor elk volgend bovenliggend knooppunt in de structuur.

Binaire zoekbomen bieden snel invoegen en opzoeken. Invoeg-, verwijderings- en zoekbewerkingen hebben in het slechtste geval een tijdcomplexiteit van O(n), die vergelijkbaar is met een gekoppelde lijst.

Voordelen van binaire bomen

Binaire bomen bieden veel voordelen en daarom blijven ze een zeer nuttige gegevensstructuur. Ze kunnen worden gebruikt om de structurele relaties en hiërarchieën in een dataset weer te geven. Belangrijker is dat binaire bomen efficiënt zoeken, verwijderen en invoegen mogelijk maken.

Het is ook heel eenvoudig om een ​​binaire boom te implementeren en te onderhouden. Een binaire boom biedt programmeurs de voordelen van een geordende array en een gekoppelde lijst; zoeken in een binaire boom is net zo snel als in een gesorteerde array en invoeg- of verwijderingsbewerkingen zijn net zo efficiënt als in gekoppelde lijsten.

Binaire bomen zijn belangrijke gegevensstructuren

Binaire bomen zijn een zeer belangrijke gegevensstructuur en het is van cruciaal belang dat programmeurs ze gemakkelijk in hun programma's kunnen toepassen. Vaak stellen interviewers eenvoudige binaire boomproblemen zoals traversals, maximale diepte, spiegeling, enz.

We raden ten zeerste aan het concept van de binaire boom te begrijpen en bekend te zijn met typische interviewproblemen.

TreeViz: een eenvoudige manier om gegevensstructuren te visualiseren

Lees volgende

Over de auteur