Wat is een binaire zoekboom?

Een binaire zoekboom is een van de verschillende gegevensstructuren die ons helpen bij het ordenen en sorteren van gegevens. Het is een efficiënte manier om gegevens in een hiërarchie op te slaan en is zeer flexibel.

In dit artikel zullen we nader bekijken hoe het werkt, samen met zijn eigenschappen en toepassingen.

Wat is een binaire zoekboom?

Een binaire zoekboom is een gegevensstructuur die is samengesteld uit knooppunten, vergelijkbaar met gekoppelde lijsten. Er kunnen twee soorten knooppunten zijn: een ouder en een kind. Het hoofdknooppunt is het beginpunt van de structuur die zich vertakt in twee onderliggende knooppunten, het linkerknooppunt en het rechterknooppunt genoemd.

Er kan alleen naar elk knooppunt worden verwezen door zijn ouder, en we kunnen de knooppunten van de boom doorkruisen, afhankelijk van de richting. De binaire zoekboom heeft drie hoofdeigenschappen:

1. Het linker knooppunt is kleiner dan het bovenliggende knooppunt.
2. Het rechterknooppunt is groter dan het bovenliggende knooppunt.
instagram viewer
3. De linker- en rechtersubstructuur moeten binaire zoekbomen zijn.

Een perfecte binaire zoekboom wordt bereikt wanneer alle niveaus zijn gevuld en elke knoop een linker en rechter onderliggende knoop heeft.

Verwant: Data Science-bibliotheken voor Python die elke datawetenschapper zou moeten gebruiken

Basisbewerkingen van een binaire zoekboom

Nu je een beter idee hebt van wat een binaire zoekboom is, kunnen we de basishandelingen hieronder bekijken.

1. Zoekbewerking

Zoeken stelt ons in staat om een ​​bepaalde waarde in de boom te lokaliseren. We kunnen twee soorten zoekopdrachten gebruiken: breedte-eerst zoeken (BFS) en diepte-eerst zoeken (DFS). Breedte-eerst zoeken is een zoekalgoritme dat begint bij het hoofdknooppunt en horizontaal doorloopt, van links naar rechts, totdat het doel is gevonden. Elk knooppunt wordt tijdens deze zoekopdracht één keer bezocht.

Diepte-eerst zoeken, aan de andere kant, doorkruist de boom verticaal - beginnend bij het wortelknooppunt en werkend langs een enkele tak. Als het doel is gevonden, eindigt de operatie. Maar zo niet, dan zoekt het de andere knooppunten.

2. Invoegbewerking

De invoegbewerking gebruikt de zoekbewerking om de locatie te bepalen waar de nieuwe knoop moet worden ingevoegd. Het proces begint vanaf het hoofdknooppunt en het zoeken begint totdat de bestemming is bereikt. Er zijn drie gevallen te overwegen bij het inbrengen.

• Geval 1: Wanneer er geen knooppunt bestaat. Het in te voegen knooppunt wordt het hoofdknooppunt.

• Casus 2: Er zijn geen kinderen. In dit geval wordt het knooppunt vergeleken met het hoofdknooppunt. Als het groter is, wordt het het juiste kind; anders wordt het het linkerkind.

• Geval 3: Wanneer de wortel en zijn kinderen aanwezig zijn. Het nieuwe knooppunt wordt vergeleken met elk knooppunt op zijn pad om te bepalen welk knooppunt het vervolgens bezoekt. Als het knooppunt groter is dan het hoofdknooppunt, zal het door de rechter sub-boom of anders naar links gaan. Evenzo worden op elk niveau vergelijkingen gemaakt om te bepalen of het naar rechts of naar links zal gaan totdat het op zijn bestemming aankomt.

3. Bewerking verwijderen

De verwijderbewerking wordt gebruikt om een ​​bepaald knooppunt in de boom te verwijderen. Verwijderen wordt als lastig beschouwd, omdat na het verwijderen van een knooppunt de boom dienovereenkomstig opnieuw moet worden georganiseerd. Er zijn drie belangrijke gevallen om te overwegen:

• Geval 1: Een bladknooppunt verwijderen. Een bladknoop is een knoop zonder kinderen. Dit is het gemakkelijkst te verwijderen omdat het geen enkel ander knooppunt beïnvloedt; we doorkruisen eenvoudig de boom totdat we deze bereiken en verwijderen.

• Geval 2: Een knooppunt met één kind verwijderen. Als u een ouder met één knooppunt verwijdert, neemt het kind zijn positie in en alle volgende knooppunten gaan een niveau omhoog. Er verandert niets aan de structuur van de subbomen.

• Geval 3: Een knooppunt met twee kinderen verwijderen. Wanneer we een knoop met twee kinderen moeten verwijderen, moeten we eerst een volgende knoop vinden die zijn positie kan innemen. Twee nodes kunnen de verwijderde node vervangen, de inorder opvolger of voorganger. De opvolger in volgorde is het meest linkse kind van de rechter subboom, en de voorganger in volgorde is het meest rechtse kind van de linker subboom. We kopiëren de inhoud van de opvolger/voorganger naar de node en verwijderen de inorder/opvolger.

Verwant: Hoe gegevensstructuren te bouwen met JavaScript ES6-klassen

Hoe een binaire zoekboom te doorkruisen

Traversal is het proces waarmee we door een binaire zoekboom navigeren. Het wordt gedaan om een ​​specifiek item te lokaliseren of om een ​​omtrek van de boom af te drukken. We beginnen altijd vanaf het hoofdknooppunt en moeten de randen volgen om bij de andere knooppunten te komen. Elk knooppunt moet worden beschouwd als een substructuur en het proces wordt herhaald totdat alle knooppunten zijn bezocht.

• Doorloop in volgorde: Als u in de juiste volgorde doorloopt, wordt een kaart in oplopende volgorde geproduceerd. Bij deze methode beginnen we bij de linker subboom en gaan we verder naar de root en de rechter subboom.

• Pre-order doorloop: Bij deze methode wordt eerst het hoofdknooppunt bezocht, gevolgd door de linker subboom en de rechter subboom.

• Doorloop na bestelling: Deze traversal houdt in dat u als laatste het hoofdknooppunt bezoekt. We beginnen met de linker subboom, dan de rechter subboom, en dan de root node.

Toepassingen in de echte wereld

Dus, hoe gebruiken we binaire zoekboomalgoritmen? Zoals kan worden vermoed, zijn ze uiterst efficiënt in zoeken en sorteren. De grootste kracht van binaire bomen is hun georganiseerde structuur. Het maakt zoeken met opmerkelijke snelheden mogelijk door de hoeveelheid gegevens die we moeten analyseren met de helft te verminderen per passage.

Binaire zoekbomen stellen ons in staat om een ​​dynamisch veranderende dataset efficiënt te onderhouden in een georganiseerde vorm. Voor toepassingen waarbij gegevens vaak worden ingevoegd en verwijderd, zijn ze erg handig. Engines voor videogames gebruiken een algoritme op basis van bomen die bekend staat als binaire ruimtepartitie om te helpen bij het ordelijk weergeven van objecten. Microsoft Excel en de meeste spreadsheetsoftware gebruiken binaire bomen als hun basisgegevensstructuur.

Het zal je misschien verbazen te weten dat morsecode een binaire zoekboom gebruikt om gegevens te coderen. Een andere prominente reden waarom binaire zoekbomen zo handig zijn, is hun meerdere variaties. Door hun flexibiliteit zijn er talloze varianten ontstaan ​​om allerlei problemen op te lossen. Bij correct gebruik zijn binaire zoekbomen een grote aanwinst.

Binaire zoekbomen: het perfecte startpunt

Een van de belangrijkste manieren om de expertise van een ingenieur te meten, is door hun kennis en toepassing van datastructuren. Gegevensstructuren zijn nuttig en kunnen helpen om een ​​efficiënter systeem te creëren. Binaire zoekbomen zijn een geweldige introductie tot datastructuren voor elke beginnende ontwikkelaar.

15 JavaScript-array-methoden die u vandaag moet beheersen

Wilt u JavaScript-arrays begrijpen, maar kunt u er geen grip op krijgen? Bekijk onze voorbeelden van JavaScript-arrays voor hulp.

Lees volgende

Over de auteur