Binaire zoekboom in Java

binary search tree java implementation code examples

Probeer Ons Instrument Voor Het Oplossen Van Problemen

Selecteer Het Besturingssysteem Kies Een Projectieprogramma (Optioneel)

Beschrijf Uw Probleem

Deze tutorial behandelt de binaire zoekboom in Java. Je leert een BST maken, een element invoegen, verwijderen en zoeken, een BST doorkruisen en implementeren in Java:

Een binaire zoekboom (hierna BST genoemd) is een soort binaire boom. Het kan ook worden gedefinieerd als een op knooppunten gebaseerde binaire boom. BST wordt ook wel ‘Ordered Binary Tree’ genoemd. In BST hebben alle knooppunten in de linker substructuur waarden die kleiner zijn dan de waarde van het hoofdknooppunt.

Evenzo hebben alle knooppunten van de rechter substructuur van de BST waarden die groter zijn dan de waarde van het hoofdknooppunt. Deze volgorde van knooppunten moet ook gelden voor de respectievelijke substructuren.

 Bezoek hier voor de exclusieve Java Training Tutorial Series.

Wat je leert:

Binaire zoekboom in Java
Gevolgtrekking
- Aanbevolen literatuur

Een BST staat geen dubbele knooppunten toe.

Het onderstaande diagram toont een BST-weergave:

Hierboven ziet u een voorbeeld van BST. We zien dat 20 het hoofdknooppunt van deze boom is. De linker substructuur heeft alle knooppuntwaarden die kleiner zijn dan 20. De rechter substructuur heeft alle knooppunten die groter zijn dan 20. We kunnen zeggen dat de bovenstaande boom voldoet aan de BST-eigenschappen.

De BST-gegevensstructuur wordt als zeer efficiënt beschouwd in vergelijking met arrays en gekoppelde lijsten als het gaat om het invoegen / verwijderen en zoeken van items.

BST heeft O (log n) tijd nodig om naar een element te zoeken. Als elementen worden geordend, wordt de helft van de substructuur bij elke stap weggegooid tijdens het zoeken naar een element. Dit wordt mogelijk doordat we eenvoudig de grove locatie van het te zoeken element kunnen bepalen.

Evenzo zijn invoeg- en verwijderingsbewerkingen efficiënter in BST. Als we een nieuw element willen invoegen, weten we ongeveer in welke substructuur (links of rechts) we het element zullen invoegen.

Een binaire zoekboom (BST) maken

Gegeven een reeks elementen, moeten we een BST construeren.

Laten we dit doen zoals hieronder wordt weergegeven:

Gegeven array: 45, 10, 7, 90, 12, 50, 13, 39, 57

Laten we eerst het bovenste element, d.w.z. 45, beschouwen als het hoofdknooppunt. Vanaf hier gaan we door met het maken van de BST door de reeds besproken eigenschappen in overweging te nemen.

Om een boomstructuur te maken, vergelijken we elk element in de array met de wortel. Vervolgens plaatsen we het element op een geschikte plek in de boom.

Het volledige aanmaakproces voor BST wordt hieronder weergegeven.

BST voltooid

Binaire zoekboombewerkingen

BST ondersteunt verschillende operaties. De volgende tabel toont de methoden die door BST in Java worden ondersteund. We zullen elk van deze methoden afzonderlijk bespreken.

Werkwijze / werking	Omschrijving
Invoegen	Voeg een element toe aan de BST door de BST-eigenschappen niet te schenden.
Verwijderen	Verwijder een bepaald knooppunt uit de BST. Het knooppunt kan het hoofdknooppunt, niet-blad- of bladknooppunt zijn.
Zoeken	Zoek de locatie van het gegeven element in de BST. Deze bewerking controleert of de boom de opgegeven sleutel bevat.

Voeg een element in BST in

Een element wordt altijd als leaf-node in BST ingevoegd.

Hieronder staan de stappen voor het invoegen van een element.

Begin bij de wortel.
Vergelijk het in te voegen element met het hoofdknooppunt. Als het kleiner is dan root, doorloop dan de linker substructuur of door de rechter substructuur.
Doorloop de substructuur tot het einde van de gewenste substructuur. Voeg het knooppunt in de juiste substructuur in als een bladknooppunt.

Laten we eens kijken naar een illustratie van de invoegbewerking van BST.

Beschouw de volgende BST en laten we element 2 in de boom invoegen.

Figuur 1

Figuur 2

De invoegbewerking voor BST wordt hierboven weergegeven. In figuur (1) tonen we het pad dat we doorlopen om element 2 in de BST in te voegen. We hebben ook de voorwaarden laten zien die bij elk knooppunt worden gecontroleerd. Als resultaat van de recursieve vergelijking wordt element 2 ingevoegd als het rechterkind van 1 zoals weergegeven in figuur (2).

Zoekbewerking in BST

Om te zoeken of een element aanwezig is in de BST, beginnen we opnieuw bij de wortel en gaan dan door de linker of rechter substructuur, afhankelijk van of het te doorzoeken element kleiner of groter is dan de wortel.

Hieronder staan de stappen vermeld die we moeten volgen.

Vergelijk het element dat moet worden doorzocht met het hoofdknooppunt.
Als de sleutel (te doorzoeken element) = root, retourneer root node.
Anders als de sleutel
Anders doorkruis de rechter substructuur.
Vergelijk substructuurelementen herhaaldelijk totdat de sleutel is gevonden of het einde van de boomstructuur is bereikt.

Laten we de zoekbewerking illustreren met een voorbeeld. Bedenk dat we de sleutel = 12 moeten zoeken.

In de onderstaande afbeelding zullen we het pad volgen dat we volgen om naar dit element te zoeken.

Zoals te zien is in de bovenstaande afbeelding, vergelijken we eerst de sleutel met root. Omdat de sleutel groter is, doorlopen we de rechter substructuur. In de rechter substructuur vergelijken we de sleutel opnieuw met het eerste knooppunt in de rechter substructuur.

We vinden dat de sleutel kleiner is dan 15. We gaan dus naar de linker substructuur van knooppunt 15. Het onmiddellijk linkse knooppunt van 15 is 12 dat overeenkomt met de sleutel. Op dit punt stoppen we met zoeken en retourneren we het resultaat.

Element verwijderen uit de BST

Wanneer we een knooppunt uit de BST verwijderen, zijn er drie mogelijkheden zoals hieronder besproken:

Knooppunt is een bladknooppunt

Als een te verwijderen knoop een bladknooppunt is, kunnen we dit knooppunt direct verwijderen omdat het geen onderliggende knooppunten heeft. Dit wordt weergegeven in de onderstaande afbeelding.

Zoals hierboven getoond, is het knooppunt 12 een bladknooppunt en kan het meteen worden verwijderd.

Knooppunt heeft slechts één kind

Wanneer we het knooppunt met één kind moeten verwijderen, kopiëren we de waarde van het kind in het knooppunt en verwijderen we vervolgens het kind.

In het bovenstaande diagram willen we knooppunt 90 verwijderen dat één kind 50 heeft. Dus we ruilen de waarde 50 met 90 en verwijderen vervolgens knooppunt 90 dat nu een kindknooppunt is.

Node heeft twee kinderen

Als een te verwijderen knoop twee kinderen heeft, dan vervangen we het knooppunt door de in volgorde (links-wortel-rechts) opvolger van het knooppunt of zeggen we simpelweg het minimumknooppunt in de rechter substructuur als de rechter substructuur van het knooppunt niet leeg is. We vervangen het knooppunt door dit minimumknooppunt en verwijderen het knooppunt.

In het bovenstaande diagram willen we knooppunt 45 verwijderen, het hoofdknooppunt van BST. We vinden dat de juiste substructuur van dit knooppunt niet leeg is. Vervolgens doorlopen we de rechter substructuur en vinden dat knooppunt 50 hier het minimumknooppunt is. Dus we vervangen deze waarde in plaats van 45 en verwijderen vervolgens 45.

Als we de boom controleren, zien we dat deze voldoet aan de eigenschappen van een BST. De knooppuntvervanging was dus correct.

Implementatie van binaire zoekboom (BST) in Java

Het volgende programma in Java biedt een demonstratie van alle bovenstaande BST-bewerkingen met behulp van dezelfde structuur die in de illustratie als voorbeeld wordt gebruikt.

hoe u een json-bestand uitvoert

Uitgang:

Binaire zoekboom (BST) Traversal in Java

Een boom is een hiërarchische structuur, dus we kunnen er niet lineair doorheen lopen zoals andere datastructuren zoals arrays. Elk type boom moet op een speciale manier worden doorlopen, zodat al zijn substructuren en knooppunten minstens één keer worden bezocht.

Afhankelijk van de volgorde waarin de hoofdknoop, de linker substructuur en de rechter substructuur in een boom worden doorlopen, zijn er bepaalde traversals zoals hieronder getoond:

In volgorde doorlopen
Traversal reserveren
PostOrder Traversal

Alle bovenstaande traversalen gebruiken de diepte eerst techniek, d.w.z. de boom wordt in de diepte doorlopen.

De bomen gebruiken ook de breedte-eerst-techniek voor doorkruisen. De benadering met behulp van deze techniek wordt genoemd 'Level Order' traversal.

In deze sectie zullen we elk van de traversals demonstreren aan de hand van de volgende BST als voorbeeld.

Met de BST zoals weergegeven in het bovenstaande diagram, is de doorloop van de niveauvolgorde voor de bovenstaande boom:

Level Order Traversal: 10 6 12 4 8

In volgorde doorlopen

De inorder traversal benadering doorkruiste de BST in de volgorde, Linker substructuur => RootNode => Rechter substructuur Het in volgorde doorlopen biedt een afnemende reeks knooppunten van een BST.

Het algoritme InOrder (bstTree) voor InOrder Traversal wordt hieronder gegeven.

Doorkruis de linker substructuur met InOrder (left_subtree)
Bezoek het hoofdknooppunt.
Doorkruis de rechter substructuur met InOrder (right_subtree)

De volgorde waarin de bovenstaande boom wordt doorlopen is:

4 6 8 10 12

Zoals te zien is, is de volgorde van de knooppunten als gevolg van het in volgorde doorlopen in afnemende volgorde.

Traversal reserveren

Bij pre-order traversal wordt eerst de root bezocht, gevolgd door de linker substructuur en de rechter substructuur. Pre-order traversal maakt een kopie van de stamboom. Het kan ook worden gebruikt in expressiebomen om een voorvoegseluitdrukking te verkrijgen.

Het algoritme voor PreOrder (bst_tree) traversal wordt hieronder gegeven:

Bezoek het hoofdknooppunt
Doorloop de linker substructuur met PreOrder (left_subtree).
Doorkruis de rechter substructuur met PreOrder (right_subtree).

De preorder-traversal voor de BST hierboven gegeven is:

10 6 4 8 12

PostOrder Traversal

De postOrder traversal doorloopt de BST in de volgorde: Linker substructuur-> Rechter substructuur-> Root node PostOrder traversal wordt gebruikt om de boomstructuur te verwijderen of om de postfix-uitdrukking te verkrijgen in het geval van uitdrukkingsbomen.

Het algoritme voor postOrder (bst_tree) traversal is als volgt:

Doorloop de linker substructuur met postOrder (left_subtree).
Doorloop de rechter substructuur met postOrder (right_subtree).
Bezoek het hoofdknooppunt

De postOrder-traversal voor het bovenstaande voorbeeld BST is:

4 8 6 12 10

Vervolgens zullen we deze traversals implementeren met behulp van de depth-first-techniek in een Java-implementatie.

Uitgang:

Veel Gestelde Vragen

V # 1) Waarom hebben we een binaire zoekboom nodig?

Antwoord : De manier waarop we zoeken naar elementen in de lineaire datastructuur zoals arrays met behulp van een binaire zoektechniek, waarbij de boom een hiërarchische structuur is, hebben we een structuur nodig die kan worden gebruikt om elementen in een boom te lokaliseren.

Dit is waar de binaire zoekboom komt die ons helpt bij het efficiënt zoeken van elementen in de afbeelding.

Q # 2) Wat zijn de eigenschappen van een binaire zoekboom?

Antwoord Een binaire zoekboom die tot de categorie binaire boom behoort, heeft de volgende eigenschappen:

De gegevens die zijn opgeslagen in een binaire zoekboom, zijn uniek. Het staat geen dubbele waarden toe.
De knooppunten van de linker substructuur zijn kleiner dan het hoofdknooppunt.
De knooppunten van de rechter substructuur zijn groter dan het hoofdknooppunt.

V # 3) Wat zijn de toepassingen van een binaire zoekboom?

Antwoord : We kunnen binaire zoekbomen gebruiken om enkele continue functies in de wiskunde op te lossen. Het doorzoeken van gegevens in hiërarchische structuren wordt efficiënter met binaire zoekbomen. Bij elke stap verminderen we de zoekopdracht met de helft van de substructuur.

V # 4) Wat is het verschil tussen een binaire zoekboom en een binaire zoekboom?

Antwoord: Een binaire boom is een hiërarchische boomstructuur waarin elk knooppunt dat bekend staat als de ouder maximaal twee kinderen kan hebben. Een binaire zoekboom voldoet aan alle eigenschappen van de binaire boom en heeft ook zijn unieke eigenschappen.

In een binaire zoekboom bevatten de linker substructuren knooppunten die kleiner zijn dan of gelijk zijn aan het hoofdknooppunt en de rechter substructuur heeft knooppunten die groter zijn dan het hoofdknooppunt.

V # 5) Is de binaire zoekboom uniek?

Antwoord : Een binaire zoekboom behoort tot een binaire boomcategorie. Het is uniek in de zin dat het geen dubbele waarden toestaat en ook al zijn elementen zijn geordend volgens een specifieke volgorde.

Gevolgtrekking

Binaire zoekbomen maken deel uit van de binaire boomcategorie en worden voornamelijk gebruikt voor het zoeken in hiërarchische gegevens. Het wordt ook gebruikt om een aantal wiskundige problemen op te lossen.

In deze tutorial hebben we de implementatie van een binaire zoekboom gezien. We hebben ook verschillende bewerkingen op BST met hun illustratie gezien en ook de traversals voor BST onderzocht.

 Bekijk hier de eenvoudige Java-trainingsserie.

Binaire zoekboom in Java - Implementatie en codevoorbeelden