Binaire zoekboom (BST) met voorbeeld

Wat is een binaire zoekboom?

De binaire zoekboom (BST) is een geavanceerd algoritme dat wordt gebruikt om een ​​knooppunt en de bijbehorende linker- en rechtertakken te analyseren. Deze takken zijn gemodelleerd als een boomstructuur, waarna de bijbehorende waarde wordt geretourneerd. De BST is gebaseerd op de architectuur van een eenvoudig binair zoekalgoritme, waardoor het sneller is om knooppunten op te zoeken, in te voegen of te verwijderen. Dit maakt het programma zeer snel en nauwkeurig.

Kenmerken van binaire zoekboom

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

• De 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 zijn de sleutels van de knooppunten in de rechter subboom groter 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 sleutelwaarden in de rechter subboom zijn groter dan die van het bovenliggende knooppunt.
3. De linker subboom heeft sleutelwaarden die kleiner zijn dan die van het bovenliggende knooppunt.

Waarom hebben we een binaire zoekboom nodig?

• De twee belangrijkste factoren die een binaire zoekboom tot een optimale oplossing voor elk probleem in de praktijk maken, 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, als het gezochte element groter of kleiner is dan het bovenliggende knooppunt, aan welke kant van de boom het moet zoeken. De reden hiervoor is dat de linker subboom altijd kleiner is dan het bovenliggende knooppunt, en de rechter subboom altijd waarden bevat 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 boom zijn gevuld, met mogelijk een uitzondering op het laatste niveau. Evenzo zijn alle knooppunten gevuld, die zich helemaal links bevinden.
• Volledige binaire boom: Alle knooppunten hebben 2 kindknooppunten, behalve het bladknooppunt.
• Evenwichtige of perfecte binaire boom: In de boomstructuur heeft elk knooppunt twee kinderen. Bovendien heeft elk subknooppunt hetzelfde niveau.

Meer informatie over de 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 eenvoudig de linker- of rechterdeelboom van het wortelknooppunt verwijderen.

BST biedt u voornamelijk de volgende drie soorten bewerkingen aan:

• Zoeken: Zoekt het element in de binaire boom.
• Plaats: voegt een element toe aan de binaire boom.
• Verwijderen: Verwijdert het element uit een binaire boom.

Elke bewerking heeft zijn eigen structuur en uitvoerings-/analysemethode, maar de meest complexe is de Delete-bewerking.

Zoeken Operatie

Begin de analyse van de boom altijd bij het wortelknooppunt en ga vervolgens verder naar de rechter- of linkerdeelboom van het wortelknooppunt, afhankelijk van of het te lokaliseren element kleiner of groter is dan het wortelknooppunt.

1. Het te zoeken element is 10.
2. Vergelijk het element met het wortelknooppunt 12; 10 < 12, dus ga je naar de linker subboom. Je hoeft de rechter subboom niet te analyseren.
3. Vergelijk nu knooppunt 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 kindknooppunt rechts van de subboom.
5. 10 komt overeen met de waarde in het knooppunt, 10 = 10, retourneert de waarde aan de gebruiker.

Pseudo Code 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 zeer eenvoudige bewerking. Eerst wordt het wortelknooppunt ingevoegd, vervolgens wordt de volgende waarde vergeleken met het wortelknooppunt. Als de waarde groter is dan de wortel, wordt deze toegevoegd aan de rechter subboom, en als deze kleiner is dan de wortel, wordt deze toegevoegd aan de linker subboom.

1. Er is een lijst met 6 elementen die van links naar rechts in een binaire zoekboom (BST) moeten worden ingevoegd.
2. Voeg 12 in als wortelknooppunt en vergelijk de volgende waarden 7 en 9 om ze respectievelijk in de rechter en linker subboom in te voegen.
3. Vergelijk de overgebleven waarden 19, 5 en 10 met het wortelknooppunt 12 en plaats ze dienovereenkomstig. 19 > 12, plaats het als rechterkind van 12; 5 < 12 en 5 < 7, plaats het dus als linkerkind van 7. Vergelijk nu 10: 10 is < 12 en 10 is > 7 en 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

Verwijdering Operaties

Bij het verwijderen van een knooppunt uit een binaire zoekboom zijn er verschillende mogelijkheden, bijvoorbeeld het verwijderen van de wortel of een bladknooppunt. Na het verwijderen van de wortel moeten we ook nadenken over wat er met het wortelknooppunt gebeurt.

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 eenvoudigste situatie: je hoeft alleen maar het knooppunt te verwijderen dat geen kinderen meer heeft aan de rechter- of linkerkant.
• Geval 2 – Knooppunt met één kind: Nadat je het knooppunt hebt verwijderd, verbind je het onderliggende knooppunt eenvoudigweg met het bovenliggende knooppunt van de verwijderde waarde.
• Geval 3 – Knooppunt met twee kinderen: Dit is de moeilijkste situatie, en die werkt volgens de volgende twee regels:
  • 3a – Voorganger in de juiste volgorde: Je moet het knooppunt met twee kinderen verwijderen en vervangen door de grootste waarde in de linker subboom van het verwijderde knooppunt.
  • 3b – Opvolger in de juiste volgorde: Je moet het knooppunt met twee kinderen verwijderen en vervangen door de kleinste waarde in de rechterdeelboom van het verwijderde knooppunt.

1. Dit is het eerste geval van verwijdering, waarbij je 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 je een knooppunt verwijdert dat 1 kindknooppunt heeft. Zoals je in het diagram kunt zien, heeft 9 één kindknooppunt.
2. Verwijder knooppunt 9 en vervang het door het kindknooppunt 10, en voeg een link toe van 7 naar 10.
3. Bekijk de nieuwe structuur van de BST zonder 9.

1. Hier ga je knooppunt 12 verwijderen, dat twee kinderen heeft.
2. De verwijdering 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 van 12.

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

Pseudo Code 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, delete the successor
        free(newNode)
    else
        free(y)

Belangrijke voorwaarden

• Plaats: Voegt een element in een boomstructuur in / creëert een boomstructuur.
• Zoeken: Zoekt naar een element in een boomstructuur.
• Preorder Traversal: Beweegt zich op een vooraf bepaalde manier door een boom.
• Inorder doorkruisen: Doorloopt een boom op een ordelijke manier.
• Postorder Traversal: Doorkruist een boomstructuur op een postorder-manier.

Veelgestelde vragen