Wat is een binaire zoekboom?
De binaire zoekboom is een geavanceerd algoritme dat wordt gebruikt voor het analyseren van het knooppunt, de linker- en rechtertakken, die in een boomstructuur worden gemodelleerd en de waarde retourneren. De BST is ontworpen op basis van de architectuur van een standaard binair zoekalgoritme; vandaar dat het sneller opzoeken, invoegen en verwijderen van knooppunten mogelijk maakt. Dit maakt het programma erg snel en nauwkeurig.
In deze handleiding Gegevensstructuur leert u:
- Wat is een binaire zoekboom?
- Kenmerken van binaire zoekboom
- Waarom hebben we een binaire zoekboom nodig?
- Soorten binaire bomen
- Hoe werkt de binaire zoekboom?
- Belangrijke voorwaarden
Kenmerken van binaire zoekboom
Een BST is gemaakt van meerdere knooppunten en bestaat uit de volgende attributen:
- Knooppunten van de boom worden weergegeven in een ouder-kindrelatie
- Elk bovenliggend knooppunt kan nul onderliggende knooppunten hebben of maximaal twee subknooppunten of substructuren aan de linker- en rechterkant.
- Elke subboom, ook wel een binaire zoekboom genoemd, heeft links en rechts subvertakkingen.
- Alle knooppunten zijn verbonden met sleutel-waardeparen.
- De sleutels van de knooppunten op de linker substructuur zijn kleiner dan de sleutels van hun bovenliggende knooppunt
- Evenzo hebben de sleutels van de linker subboomknooppunten lagere waarden dan de sleutels van hun bovenliggende knooppunt.
- Er is het hoofdknooppunt of het bovenliggende niveau 11. Daaronder bevinden zich linker- en rechterknooppunten / takken met hun eigen sleutelwaarden
- De rechter subboom heeft sleutelwaarden die groter zijn dan het bovenliggende knooppunt
- De linker subboom heeft waarden dan het bovenliggende knooppunt
Waarom hebben we een binaire zoekboom nodig?
- De twee belangrijkste factoren die van de binaire zoekboom een optimale oplossing maken voor echte problemen, zijn snelheid en nauwkeurigheid.
- Vanwege het feit dat de binaire zoekopdracht in een branch-achtig formaat is met ouder-kind relaties, weet het algoritme op welke locatie van de boom de elementen moeten worden doorzocht. Dit vermindert het aantal sleutel-waarde-vergelijkingen dat het programma moet maken om het gewenste element te lokaliseren.
- Bovendien, in het geval dat het te doorzoeken element groter of kleiner is dan het bovenliggende knooppunt, weet het knooppunt naar welke boomzijde er moet worden gezocht. De reden hiervoor is dat de linker subboom altijd kleiner is dan het bovenliggende knooppunt, en de rechter subboom waarden heeft die altijd gelijk zijn aan of groter zijn dan het bovenliggende knooppunt.
- BST wordt vaak gebruikt om complexe zoekopdrachten, robuuste spellogica, automatisch aanvullen van activiteiten en afbeeldingen te implementeren.
- Het algoritme ondersteunt op efficiënte wijze bewerkingen zoals zoeken, invoegen en verwijderen.
Soorten binaire bomen
Drie soorten binaire bomen zijn:
- Volledige binaire boom: alle niveaus in de bomen staan vol met mogelijke uitzonderingen op het laatste niveau. Evenzo zijn alle knooppunten vol, waardoor uiterst links wordt geleid.
- Volledige binaire boom: alle knooppunten hebben 2 onderliggende knooppunten behalve het blad.
- Evenwichtige of perfecte binaire boom: in de boom hebben alle knooppunten twee kinderen. Bovendien is er voor elk subknooppunt hetzelfde niveau.
Hoe werkt de binaire zoekboom?
De boom heeft altijd een hoofdknooppunt en verdere onderliggende knooppunten, zowel links als rechts. Het algoritme voert alle bewerkingen uit door de waarden dienovereenkomstig te vergelijken met de wortel en zijn verdere onderliggende knooppunten in de linker of rechter subboom.
Afhankelijk van het element dat moet worden ingevoegd, gezocht of verwijderd, kan het algoritme na de vergelijking gemakkelijk de linker of rechter substructuur van het hoofdknooppunt verwijderen.
BST biedt voornamelijk de volgende drie soorten bewerkingen voor uw gebruik:
- Zoeken: zoekt het element uit de binaire structuur
- Invoegen: voegt een element toe aan de binaire structuur
- Verwijderen: verwijder het element uit een binaire boom
Elke bewerking heeft zijn eigen structuur en methode van uitvoering / analyse, maar de meest complexe is de bewerking Verwijderen.
Zoekoperatie
Start altijd de analyseboom bij het hoofdknooppunt en ga dan verder naar de rechter of linker substructuur van het hoofdknooppunt, afhankelijk van het element dat moet worden gelokaliseerd of kleiner of groter is dan de wortel.
- Het te zoeken element is 10
- Vergelijk het element met de root node 12, 10 <12, dus ga je naar de linker substructuur. Het is niet nodig om de juiste substructuur te analyseren
- Vergelijk nu 10 met knooppunt 7, 10> 7, dus ga naar de rechter substructuur
- Vergelijk dan 10 met het volgende knooppunt, dat is 9, 10> 9, kijk in het rechter onderliggende boomonderdeel
- 10 overeenkomsten met de waarde in het knooppunt, 10 = 10, retourneren de waarde aan de gebruiker.
Plaats operatie
Dit is een zeer ongecompliceerde operatie. Eerst wordt het hoofdknooppunt ingevoegd, en vervolgens wordt de volgende waarde vergeleken met het hoofdknooppunt. Als de waarde groter is dan de wortel, wordt deze toegevoegd aan de rechter substructuur, en als deze kleiner is dan de wortel, wordt deze toegevoegd aan de linker substructuur.
- Er is een lijst met 6 elementen die van links naar rechts in een BST moeten worden ingevoegd
- Voeg 12 in als het hoofdknooppunt en vergelijk de volgende waarden 7 en 9 om ze dienovereenkomstig in de rechter en linker substructuur in te voegen
- Vergelijk de resterende waarden 19, 5 en 10 met het rootknooppunt 12 en plaats ze dienovereenkomstig. 19> 12 plaats het als het rechterkind van 12, 5 <12 & 5 <7, dus plaats het als het linkerkind van 7.
- Vergelijk nu 10, 10 is <12 en 10 is> 7 en 10 is> 9, plaats 10 als rechter substructuur van 9.
Bewerkingen verwijderen
Verwijderen is de meest geavanceerde en complexe van alle andere bewerkingen. Er zijn meerdere gevallen afgehandeld voor verwijdering in de BST.
- Geval 1- Knooppunt met nul kinderen: dit is de gemakkelijkste situatie, u hoeft alleen het knooppunt te verwijderen dat geen verdere kinderen aan de rechter- of linkerkant heeft.
- Geval 2 - Knooppunt met één kind: zodra u het knooppunt verwijdert, verbindt u eenvoudig het onderliggende knooppunt met het bovenliggende knooppunt van de verwijderde waarde.
- Geval 3 Knooppunt met twee kinderen: dit is de moeilijkste situatie en het werkt volgens de volgende twee regels
- 3a - In volgorde voorganger: u moet het knooppunt met twee kinderen verwijderen en het vervangen door de grootste waarde aan de linkerkant van het verwijderde knooppunt
- 3b - In volgorde opvolger: u moet het knooppunt met twee kinderen verwijderen en het vervangen door de grootste waarde aan de rechterkant van het verwijderde knooppunt
- Dit is het eerste geval van verwijdering waarbij u een knooppunt verwijdert dat geen kinderen heeft. Zoals je in het diagram kunt zien, hebben 19, 10 en 5 geen kinderen. Maar we zullen 19 verwijderen.
- Verwijder de waarde 19 en verwijder de link van het knooppunt.
- Bekijk de nieuwe structuur van de BST zonder 19
- Dit is het tweede geval van verwijdering waarbij u een knoop verwijdert die 1 kind heeft, zoals u in het diagram kunt zien dat 9 één kind heeft.
- Verwijder het knooppunt 9 en vervang het door het onderliggende 10 en voeg een link van 7 tot 10 toe
- Bekijk de nieuwe structuur van de BST zonder 9
- Hier verwijdert u het knooppunt 12 met twee kinderen
- Het verwijderen van het knooppunt zal plaatsvinden op basis van de in orde voorgangerregel, wat betekent dat het grootste element aan de linker substructuur van 12 het zal vervangen.
- Verwijder het knooppunt 12 en vervang het door 10 aangezien dit de grootste waarde in de linker substructuur is
- Bekijk de nieuwe structuur van de BST na het verwijderen 12
- 1 Verwijder een knooppunt 12 dat twee kinderen heeft
- 2 Het verwijderen van het knooppunt vindt plaats op basis van de regel In volgorde opvolger, wat betekent dat het grootste element op de rechtersubboom van 12 het zal vervangen
- 3 Verwijder het knooppunt 12 en vervang het door 19 aangezien dit de grootste waarde op de rechter substructuur is
- 4 Bekijk de nieuwe structuur van de BST na het verwijderen 12
Belangrijke voorwaarden
- Invoegen - Voegt een element in een boomstructuur in / maakt een boomstructuur.
- Zoeken - Zoekt een element in een boomstructuur.
- Preorder Traversal - Doorloopt een boom op een pre-order manier.
- In volgorde doorlopen - Doorkruist een boom op een in de juiste volgorde.
- Postordertraversal - Doorloopt een boom op een postordermanier.
Overzicht
- BST is een algoritme op geavanceerd niveau dat verschillende bewerkingen uitvoert op basis van de vergelijking van knooppuntwaarden met het hoofdknooppunt.
- Elk van de punten in een bovenliggende / onderliggende hiërarchie vertegenwoordigt het knooppunt. Ten minste één bovenliggend knooppunt of hoofdknooppunt blijft altijd aanwezig.
- Er is een linker substructuur en een rechter substructuur. De linker substructuur bevat waarden die kleiner zijn dan het hoofdknooppunt. De rechter substructuur bevat echter een waarde die groter is dan het hoofdknooppunt.
- Elk knooppunt kan nul, één of twee kinderen hebben.
- Een binaire zoekboom vereenvoudigt primaire bewerkingen zoals zoeken, invoegen en verwijderen.
- Delete is de meest complexe en heeft meerdere gevallen, bijvoorbeeld een knooppunt zonder kind, een knooppunt met één kind en een knooppunt met twee kinderen.
- Het algoritme wordt gebruikt in real-world oplossingen zoals games, automatisch aanvullen van gegevens en afbeeldingen.