Binaire zoekboom (BST) met voorbeeld

Kenmerken van binaire zoekboom

Een BST bestaat uit meerdere knooppunten en bestaat uit de volgende kenmerken:

• 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.

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 complexe zoekopdrachten, robuuste spellogica, automatisch aanvullen van activiteiten en grafische weergaven te implementeren.
• Het algoritme ondersteunt efficiënt 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 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 root node en verdere child nodes, of deze nu links of rechts zijn. Het algoritme voert alle bewerkingen uit door waarden te vergelijken met de root en zijn verdere child nodes in de linker of rechter sub-tree.

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 biedt u voornamelijk de volgende drie soorten bewerkingen aan:

• 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 bewerking heeft zijn eigen structuur en uitvoerings-/analysemethode, maar de meest complexe is de Delete-bewerking.

Zoek 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.

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 zoeken 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 een heel eenvoudige handeling. Eerst wordt de root node ingevoegd, dan wordt de volgende waarde vergeleken met de root node. Als de waarde groter is dan de root, wordt deze toegevoegd aan de rechter subtree, en als deze kleiner is dan de root, wordt deze toegevoegd aan de linker subtree.

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 node willen verwijderen, dan kunnen we die gewoon verwijderen, maar als we een root willen verwijderen, moeten we de rootwaarde vervangen door een andere node. Laten we het volgende voorbeeld nemen:

• 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 volgens de volgende 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

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

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

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

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.

Samenvatting

• BST is een geavanceerd algoritme dat verschillende bewerkingen uitvoert op basis van 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 primaire bewerkingen zoals zoeken, invoegen en verwijderen.
• Omdat Delete het meest complex is, zijn er meerdere gevallen mogelijk, bijvoorbeeld een knooppunt zonder onderliggend element, een knooppunt met één onderliggend element en een knooppunt met twee onderliggend elementen.
• Het algoritme wordt gebruikt in oplossingen uit de echte wereld, zoals games, gegevens voor automatisch aanvullen en afbeeldingen.