Binaire zoekboom (BST) met voorbeeld

Wat is een binaire zoekboom?

De binaire zoekboom is een geavanceerd algoritme dat wordt gebruikt voor het analyseren van het knooppunt en de linker- en rechtertakken ervan, die in een boomstructuur zijn gemodelleerd en de waarde retourneren. De BST is bedacht op de archistructuur van een basis binair zoekalgoritme; vandaar dat het snellere zoekopdrachten, invoegingen en verwijderingen van knooppunten mogelijk maakt. Dit maakt het programma erg snel en nauwkeurig.

Kenmerken van binaire zoekboom

Een BST bestaat uit meerdere knooppunten en bestaat uit de following attributen:

  • Knooppunten van de boom worden weergegeven in een ouder-kindrelatie
  • Elk ouderknooppunt kan nul onderliggende knooppunten hebben of maximaal twee subknooppunten of subbomen aan de linker- en rechterkant.
  • Elke subboom, ook wel een binaire zoekboom genoemd, heeft rechts en links van zichzelf subtakken.
  • Alle knooppunten zijn verbonden met sleutel-waardeparen.
  • De sleutels van de knooppunten in de linker subboom zijn kleiner dan de sleutels van hun bovenliggende knooppunt
  • Op dezelfde manier hebben de sleutels van de knooppunten in de linkersubboom lagere waarden dan de sleutels van hun bovenliggende knooppunt.

Kenmerken van binaire zoekboom

  1. Er is het hoofdknooppunt of ouderniveau 11. Daaronder bevinden zich linker- en rechterknooppunten/takken met hun eigen sleutelwaarden
  2. De rechter subboom heeft sleutelwaarden die groter zijn dan het bovenliggende knooppunt
  3. De linker subboom heeft waarden dan het bovenliggende knooppunt

Waarom hebben we een binaire zoekboom nodig?

  • De twee belangrijkste factoren die de binaire zoekboom tot een optimale oplossing maken voor echte problemen zijn snelheid en nauwkeurigheid.
  • Omdat de binaire zoekopdracht een vertakkingsachtig formaat heeft met ouder-kindrelaties, weet het algoritme op welke locatie van de boom de elementen moeten worden doorzocht. Dit vermindert het aantal sleutel-waardevergelijkingen dat het programma moet maken om het gewenste element te lokaliseren.
  • Bovendien weet het knooppunt, in het geval dat het te doorzoeken element groter of kleiner is dan het bovenliggende knooppunt, naar welke boomzijde moet worden gezocht. De reden hiervoor is dat de linker subboom altijd kleiner is dan het bovenliggende knooppunt, en dat de rechter subboom altijd waarden heeft die gelijk zijn aan of groter zijn dan het bovenliggende knooppunt.
  • BST wordt vaak gebruikt om com te implementerenplex zoekopdrachten, robuuste spellogica, activiteiten voor automatisch aanvullen en afbeeldingen.
  • Het algoritme ondersteunt efficiënt operafuncties 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 van het laatste niveau. Op dezelfde manier zijn alle knooppunten vol en wijzen ze uiterst links.
  • Volledige binaire boom: Alle knooppunten hebben 2 onderliggende knooppunten, behalve het blad.
  • Gebalanceerde of perfecte binaire boom: In de boom hebben alle knooppunten twee kinderen. Bovendien is er hetzelfde niveau van elk subknooppunt.

Lees verder over Binaire boom in gegevensstructuur als je geïnteresseerd bent.

Hoe werkt de binaire zoekboom?

De boom heeft altijd een hoofdknooppunt en verdere onderliggende knooppunten, zowel links als rechts. Het algoritme voert alle operadoor waarden te vergelijken met de wortel en de 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 rechtersubboom van het hoofdknooppunt laten vallen.

BST primarily biedt het volgendewing drie soorten operaties voor uw gebruik:

  • Zoeken: zoekt naar het element uit de binaire boom
  • Invoegen: voegt een element toe aan de binaire boom
  • Verwijderen: verwijder het element uit een binaire boom

Elke operaHet programma heeft zijn eigen structuur en methode van uitvoering/analyse, maar de meest complex van alles is de Verwijdering operatie.

Ontdek Operatie

Begin altijd met het analyseren van de boom bij het hoofdknooppunt en ga dan verder naar de rechter of linker subboom van het hoofdknooppunt, afhankelijk van het te lokaliseren element dat kleiner of groter is dan de wortel.

Ontdek Operatie

  1. Het te zoeken element is 10
  2. Vergelijk het element met het hoofdknooppunt 12, 10 < 12, dus je gaat naar de linker subboom. Het is niet nodig om de rechtersubboom te analyseren
  3. Vergelijk nu 10 met knooppunt 7, 10 > 7, dus ga naar de rechter-subboom
  4. Vergelijk vervolgens 10 met het volgende knooppunt, dat is 9, 10 > 9, kijk in het rechter subboomkind
  5. 10 komt overeen met de waarde in het knooppunt, 10 = 10, retourneert de waarde aan de gebruiker.

Pseudocode voor Searching in BST

search(element, root)
     if !root
    	return -1
     if root.value == element
    	return 1
     if root.value < element
    	search(element, root.right)
      else
    	search(element, root.left)

Invoegen Operatie

Dit is heel eenvoudig operatie. Eerst wordt het hoofdknooppunt ingevoegd en vervolgens wordt de volgende waarde vergeleken met het hoofdknooppunt. Als de waarde groter is dan de root, wordt deze toegevoegd aan de rechter subboom, en als deze kleiner is dan de root, wordt deze toegevoegd aan de linker subboom.

Invoegen Operatie

  1. Er is een lijst met 6 elementen die in een BST moeten worden ingevoegd, van links naar rechts
  2. Voeg 12 in als het hoofdknooppunt en vergelijk de volgende waarden 7 en 9 om dienovereenkomstig in de rechter en linker subboom in te voegen
  3. Vergelijk de resterende waarden 19, 5 en 10 met het hoofdknooppunt 12 en plaats ze dienovereenkomstig. 19 > 12 plaats het als rechterkind van 12, 5 < 12 & 5 < 7, plaats het dus als linkerkind van 7. Vergelijk nu 10, 10 is < 12 & 10 is > 7 & 10 is > 9, plaats 10 als rechterdeelboom van 9.

Pseudocode voor het invoegen van een knooppunt in BST

insert (element, root)
    Node x = root
    Node y = NULL
    while x:
    	y = x
    if x.value < element.value
        x = x.right
    else
        x = x.left
    if y.value < element
    	y.right = element
    else
    	y.left = element

Verwijder Operaties

Er zijn enkele gevallen voor het verwijderen van een knooppunt uit een BST, bijvoorbeeld het verwijderen van een root of het verwijderen van een leaf-knooppunt. Na het verwijderen van een root moeten we ook nadenken over het rootknooppunt.

Stel dat we een leaf-knooppunt willen verwijderen, dan kunnen we het gewoon verwijderen, maar als we een root willen verwijderen, moeten we de waarde van de root vervangen door een ander knooppunt. Laten we het volgende nemenwing voorbeeld:

  • Geval 1 – Knooppunt met nul kinderen: dit is de gemakkelijkste situatie. U hoeft alleen maar het knooppunt te verwijderen dat rechts of links geen kinderen meer heeft.
  • Geval 2 – Knooppunt met één kind: zodra u het knooppunt verwijdert, verbindt u eenvoudigweg 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 op de volgende manierwing twee regels
  • 3a – In volgorde voorganger: u moet het knooppunt met twee kinderen verwijderen en vervangen door de grootste waarde in de linkersubboom van het verwijderde knooppunt
  • 3b – In volgordeopvolger: u moet het knooppunt met twee onderliggende knooppunten verwijderen en vervangen door de grootste waarde in de rechtersubboom van het verwijderde knooppunt

Verwijder Operaties

  1. 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.
  2. Verwijder de waarde 19 en verwijder de link van het knooppunt.
  3. Bekijk de nieuwe structuur van de BST zonder 19

Verwijder Operaties

  1. Dit is het tweede geval van verwijdering waarbij u een knooppunt verwijdert dat 1 kind heeft, zoals u in het diagram kunt zien dat 9 één kind heeft.
  2. Verwijder knooppunt 9 en vervang het door het onderliggende knooppunt 10 en voeg een link toe van 7 naar 10
  3. Bekijk de nieuwe structuur van de BST zonder 9

Verwijder Operaties

  1. Hier verwijdert u knooppunt 12 dat twee kinderen heeft
  2. Het verwijderen van het knooppunt zal plaatsvinden op basis van de in-order-voorgangerregel, wat betekent dat het grootste element in de linker subboom van 12 het zal vervangen.
  3. Verwijder knooppunt 12 en vervang het door 10, aangezien dit de grootste waarde in de linker subboom is
  4. Bekijk de nieuwe structuur van de BST na het verwijderen 12

Verwijder Operaties

  1. 1 Verwijder een knooppunt 12 dat twee kinderen heeft
  2. 2 De verwijdering van het knooppunt zal plaatsvinden op basis van de In Order Successor-regel, wat betekent dat het grootste element in de rechter subboom van 12 dit zal vervangen
  3. 3 Verwijder knooppunt 12 en vervang het door 19, aangezien dit de grootste waarde in de rechter subboom is
  4. 4 Bekijk de nieuwe structuur van de BST na het verwijderen 12

Pseudocode voor het verwijderen van een knooppunt

delete (value, root):
    Node x = root
    Node y = NULL
# searching the node
    while x:
    	y = x
    if x.value < value
        x = x.right
    else if x.value > value
        x = x.left
    else if value == x
        break
# if the node is not null, then replace it with successor
    if y.left or y.right:
    	newNode = GetInOrderSuccessor(y)
    	root.value = newNode.value
# After copying the value of successor to the root #we're deleting the successor
    	free(newNode)
    else
    	free(y)

Belangrijke voorwaarden

  • Invoegen: Voegt een element in een boom in/maakt een boom.
  • Zoeken: Zoekt een element in een boom.
  • Pre-order Traversal: doorkruist een boom op een pre-order manier.
  • Inorder Traversal: Doorkruist een boom op een niet-geordende manier.
  • Postorder Traversal: Doorkruist een boom op een postorder manier.

Samengevat

  • BST is een geavanceerd algoritme dat verschillende functies uitvoert operagebaseerd op de vergelijking van knooppuntwaarden met het hoofdknooppunt.
  • Elk van de punten in een ouder-kindhiërarchie vertegenwoordigt het knooppunt. Er blijft altijd minstens één ouder- of hoofdknooppunt aanwezig.
  • Er is een linker subboom en een rechter subboom. De linker subboom bevat waarden die kleiner zijn dan het hoofdknooppunt. De rechter subboom bevat echter een waarde die groter is dan het hoofdknooppunt.
  • Elk knooppunt kan nul, één of twee kinderen hebben.
  • Een binaire zoekboom vergemakkelijkt het primair zoeken operafuncties zoals zoeken, invoegen en verwijderen.
  • Verwijderen is de meest complex meerdere gevallen hebben, bijvoorbeeld een knooppunt zonder kind, een knooppunt met één kind en een knooppunt met twee kinderen.
  • Het algoritme wordt gebruikt in oplossingen uit de echte wereld, zoals games, gegevens voor automatisch aanvullen en afbeeldingen.