Menu

Binaire zoekboom C ++: BST-implementatie en bewerkingen met voorbeelden

  • Hoofd
  • Andere
  • Binaire zoekboom C ++: BST-implementatie en bewerkingen met voorbeelden

binary search tree c

Probeer Ons Instrument Voor Het Oplossen Van Problemen

Gedetailleerde zelfstudie over binaire zoekboom (BST) in C ++ inclusief bewerkingen, C ++ -implementatie, voordelen en voorbeeldprogramma's:

Een binaire zoekboom of BST zoals deze in de volksmond wordt genoemd, is een binaire zoekboom die aan de volgende voorwaarden voldoet:

  1. De knooppunten die kleiner zijn dan de hoofdknoop die als linkerkinderen van de BST wordt geplaatst.
  2. De knooppunten die groter zijn dan het hoofdknooppunt dat is geplaatst als de rechterkinderen van de BST.
  3. De linker en rechter substructuren zijn op hun beurt de binaire zoekbomen.

Door deze rangschikking van de toetsen in een bepaalde volgorde kan de programmeur bewerkingen zoals zoeken, invoegen, verwijderen, enz. Efficiënter uitvoeren. Als de knooppunten niet zijn geordend, moeten we mogelijk elk knooppunt vergelijken voordat we het bewerkingsresultaat kunnen krijgen.

​ Bekijk hier de complete C ++ trainingsserie.

Binaire zoekboom in C ++

Wat je leert:

Binaire zoekboom C ++

Een voorbeeld van BST wordt hieronder weergegeven.

Voorbeeld BST

Binaire zoekbomen worden ook wel 'geordende binaire bomen' genoemd vanwege deze specifieke volgorde van knooppunten.

Uit de bovenstaande BST kunnen we zien dat de linker substructuur knooppunten heeft die kleiner zijn dan de wortel, d.w.z. 45, terwijl de rechter substructuur de knooppunten heeft die groter zijn dan 45.

Laten we nu enkele basisbewerkingen van BST bespreken.

Basisbewerkingen

# 1) Invoegen

Invoegbewerking voegt een nieuw knooppunt toe aan een binaire zoekboom.

Het algoritme voor het invoegen van de binaire zoekboom wordt hieronder gegeven.

hoe je een Java-applicatie maakt in Eclipse
​

Zoals blijkt uit het bovenstaande algoritme, moeten we ervoor zorgen dat het knooppunt op de juiste positie wordt geplaatst, zodat we de BST-volgorde niet overtreden.

Voeg bewerking in BST in

Zoals we in de bovenstaande reeks diagrammen zien, maken we een reeks invoegbewerkingen. Na vergelijking van de in te voegen sleutel met de hoofdknoop, wordt de linker of rechter substructuur gekozen voor de sleutel die moet worden ingevoegd als een bladknoop op de juiste positie.

# 2) Verwijderen

Met de verwijderbewerking wordt een knooppunt verwijderd dat overeenkomt met de opgegeven sleutel uit BST. Ook bij deze bewerking moeten we de resterende knooppunten herpositioneren na verwijdering, zodat de BST-volgorde niet wordt geschonden.

Daarom hebben we, afhankelijk van welk knooppunt we moeten verwijderen, de volgende gevallen voor verwijdering in BST:

# 1) Wanneer het knooppunt een Leaf Node is

Als het te verwijderen knooppunt een bladknooppunt is, verwijderen we het knooppunt direct.

Knooppunt is een bladknooppunt

# 2) Als het knooppunt slechts één kind heeft

Als het te verwijderen knooppunt slechts één kind heeft, kopiëren we het kind naar het knooppunt en verwijderen we het kind.

Node heeft slechts één kind

# 3) Als het knooppunt twee kinderen heeft

Als het te verwijderen knooppunt twee kinderen heeft, zoeken we de involgorde opvolger voor het knooppunt en kopiëren vervolgens de in volgorde opvolger naar het knooppunt. Later verwijderen we de volgende opvolger.

Node heeft twee kinderen

In de bovenstaande structuur om het knooppunt 6 met twee kinderen te verwijderen, vinden we eerst de in volgorde opvolger voor dat knooppunt dat moet worden verwijderd. We vinden de opvolger in volgorde door de minimumwaarde in de rechter substructuur te vinden. In het bovenstaande geval is de minimumwaarde 7 in de rechter substructuur. We kopiëren het naar het te verwijderen knooppunt en verwijderen vervolgens de volgende opvolger.

# 3) Zoeken

De zoekbewerking van BST zoekt naar een bepaald item dat in de BST als 'sleutel' is geïdentificeerd. Het voordeel van het zoeken naar een item in BST is dat we niet de hele boom hoeven te doorzoeken. In plaats daarvan vergelijken we vanwege de volgorde in BST de sleutel met de root.

Als de sleutel hetzelfde is als root, retourneren we root. Als de sleutel geen root is, dan vergelijken we deze met de root om te bepalen of we in de linker of rechter substructuur moeten zoeken. Zodra we de substructuur hebben gevonden, moeten we de sleutel in zoeken, en we zoeken er recursief naar in een van de substructuren.

Hieronder volgt het algoritme voor een zoekbewerking in BST.

​

Zoekbewerking in BST

Als we een sleutel met waarde 6 in de bovenstaande boom willen zoeken, dan vergelijken we eerst de sleutel met het wortelknooppunt, d.w.z. if (6 == 7) => Nee if (6<7) =Yes; this means that we will omit the right subtree and search for the key in the left subtree.

Vervolgens dalen we af naar de linker onderboom. Als (6 == 5) => Nee.

If (6 Nee; dit betekent 6> 5 en we moeten naar rechts.

If (6 == 6) => Ja; de sleutel is gevonden.

# 4) Doorkruisen

We hebben de traversals voor de binaire boom al besproken. Ook in het geval van BST kunnen we de boom doorkruisen om in de volgorde van de bestelling, pre-order of postorder te komen. Als we de BST doorlopen in de volgorde Inorder01, krijgen we in feite de gesorteerde volgorde.

We hebben dit aangetoond in de onderstaande illustratie.

traversals

De traversals voor de bovenstaande boom zijn als volgt:

In volgorde doorlopen (lnr): 3 5 6 7 8 9 10
Preorder traversal (nlr): 7 5 3 6 9 8 10
PostOrder traversal (lrn): 3 6 5 8 10 9 7

Illustratie

Laten we een binaire zoekboom construeren uit de onderstaande gegevens.

45 30 60 65 70

Laten we het eerste element als het hoofdknooppunt nemen.

# 1) 45

root-knooppunt

In de volgende stappen zullen we de gegevens plaatsen volgens de definitie van de binaire zoekboom, dwz als de gegevens kleiner zijn dan het bovenliggende knooppunt, dan wordt deze bij het linkerkind geplaatst en als de gegevens groter zijn dan het bovenliggende knooppunt, zal het juiste kind zijn.

Deze stappen worden hieronder weergegeven.

aparte ketting hashtabel c ++

# 2) 30

Binaire zoekboom Stap 1 30

# 3) 60

Binaire zoekboom Stap 2 60

# 4) 65

11 Binaire zoekboom stap 3

# 5) 70

Binaire zoekboom stap 4

Wanneer we de volgorde doorlopen op de bovenstaande BST die we zojuist hebben geconstrueerd, is de volgorde als volgt.

Volgorde doorlopen

We kunnen zien dat de traversale reeks elementen heeft die in oplopende volgorde zijn gerangschikt.

Implementatie van binaire zoekboom C ++

Laten we BST en zijn bewerkingen demonstreren met behulp van C ++ -implementatie.

​

Uitgang:

Binaire zoekboom gemaakt (in volgorde doorlopen):

30 40 60 65 70

Verwijder knooppunt 40

In volgorde doorlopen voor de gewijzigde binaire zoekboom:

30 60 65 70

In het bovenstaande programma voeren we de BST uit voor in volgorde doorlopen.

Voordelen van BST

# 1) Zoeken is zeer efficiënt

We hebben alle knooppunten van BST in een specifieke volgorde, dus het zoeken naar een bepaald item is erg efficiënt en sneller. Dit komt omdat we niet de hele boom hoeven te doorzoeken en alle knooppunten moeten vergelijken.

We hoeven alleen de root-node te vergelijken met het item dat we zoeken en dan beslissen we of we in de linker of rechter substructuur moeten zoeken.

# 2) Efficiënt werken in vergelijking met arrays en gekoppelde lijsten

Wanneer we een item zoeken in het geval van BST, verwijderen we bij elke stap de helft van de linker of rechter substructuur, waardoor de prestaties van de zoekbewerking worden verbeterd. Dit in tegenstelling tot arrays of gekoppelde lijsten waarin we alle items opeenvolgend moeten vergelijken om een ​​bepaald item te zoeken.

# 3) Invoegen en verwijderen gaat sneller

Invoeg- en verwijderbewerkingen zijn ook sneller in vergelijking met andere datastructuren zoals gekoppelde lijsten en arrays.

Toepassingen van BST

Enkele van de belangrijkste toepassingen van BST zijn:

  • BST wordt gebruikt om indexering op meerdere niveaus in databasetoepassingen te implementeren.
  • BST wordt ook gebruikt om constructies als een woordenboek te implementeren.
  • BST kan worden gebruikt om verschillende efficiënte zoekalgoritmen te implementeren.
  • BST wordt ook gebruikt in toepassingen die een gesorteerde lijst als invoer nodig hebben, zoals de online winkels.
  • BST's worden ook gebruikt om de expressie te evalueren met behulp van expressiebomen.

Gevolgtrekking

Binaire zoekbomen (BST) zijn een variatie op de binaire boom en worden veel gebruikt op softwaregebied. Ze worden ook wel geordende binaire bomen genoemd, aangezien elk knooppunt in BST volgens een specifieke volgorde wordt geplaatst.

In volgorde doorlopen van BST geeft ons de gesorteerde volgorde van items in oplopende volgorde. Wanneer BST's worden gebruikt om te zoeken, is dit zeer efficiënt en binnen de kortste keren gedaan. BST's worden ook gebruikt voor een verscheidenheid aan toepassingen, zoals Huffmans codering, indexering op meerdere niveaus in databases, enz.

​ Lees hier de populaire C ++ trainingsserie.

Aanbevolen literatuur

^