Binaarne otsingupuu (BST) koos näitega

Mis on binaarne otsingupuu?

Binaarotsingupuu on täiustatud algoritm, mida kasutatakse sõlme, selle vasaku ja parema haru analüüsimiseks, mis on modelleeritud puustruktuuris, ja väärtuse tagastamiseks. BST on loodud lihtsa binaarotsingu algoritmi arhitektuuril; seega võimaldab see kiiremaid otsinguid, sõlmede lisamist ja eemaldamist. See muudab programmi tõeliselt kiireks ja täpseks.

Binaarse otsingupuu atribuudid

BST koosneb mitmest sõlmest ja koosneb järgmistest atribuutidest:

• Puu sõlmed on esindatud vanema-lapse suhtes.
• Igal ülemsõlmel võib vasakul ja paremal küljel olla null alamsõlme või maksimaalselt kaks alamsõlme või alampuud.
• Igal alampuul, mida tuntakse ka binaarse otsingupuuna, on alamharud endast paremal ja vasakul.
• Kõik sõlmed on seotud võtme-väärtuste paaridega.
• Vasakpoolses alampuus asuvate sõlmede võtmed on väiksemad kui nende vanema sõlme võtmed.
• Samamoodi on paremal alampuul asuvate sõlmede võtmed suuremad kui nende vanema sõlme võtmed.

1. Seal on peamine sõlm ehk vanemtase 11. Selle all on vasak- ja parempoolsed sõlmed/harud oma võtmeväärtustega.
2. Parempoolsel alampuul on võtmeväärtused, mis on suuremad kui ülemsõlmel.
3. Vasakpoolsel alampuul on võtmeväärtused väiksemad kui ülemsõlmel.

Miks me vajame binaarset otsingupuud?

• Kaks peamist tegurit, mis muudavad binaarse otsingupuu optimaalseks lahenduseks mis tahes reaalse maailma probleemile, on kiirus ja täpsus.
• Tänu sellele, et binaarne otsing on harulaadses vormingus vanem-lapssuhetega, teab algoritm, millises puu asukohas elemente tuleb otsida. See vähendab võtme-väärtuste võrdluste arvu, mida programm peab soovitud elemendi leidmiseks tegema.
• Lisaks, kui otsitav element on suurem või väiksem kui ülemsõlm, teab sõlm, millisel puu poolel otsida. Põhjus on selles, et vasakpoolne alampuu on alati väiksem kui ülemsõlm ja parempoolse alampuu väärtused on alati võrdsed või suuremad kui ülemsõlm.
• BST-d kasutatakse tavaliselt keerukate otsingute, tugeva mänguloogika, automaatse täitmise ja graafika rakendamiseks.
• Algoritm toetab tõhusalt selliseid toiminguid nagu otsing, sisestamine ja kustutamine.

Binaarpuude tüübid

Kolme tüüpi kahendpuid on:

• Täielik binaarpuu: Kõik puu tasemed on täis, võimaliku erandiga viimasel tasemel. Samamoodi on täis kõik sõlmed, mis suunavad kõige vasakule.
• Täielik binaarpuu: Kõigil sõlmedel, välja arvatud lehel, on 2 alamsõlme.
• Tasakaalustatud ehk täiuslik binaarpuu: Puus on kõigil sõlmedel kaks last. Lisaks on igal alamsõlmel sama tase.

Lisateave Binaarne puu andmestruktuuris kui olete huvitatud.

Kuidas binaarne otsingupuu töötab?

Puul on alati juursõlm ja teised alamsõlmed, olgu siis vasakul või paremal. Algoritm sooritab kõik toimingud, võrreldes väärtusi juure ja selle edasiste alamsõlmedega vasakpoolses või paremas alampuus.

Sõltuvalt sisestatavast, otsitavast või kustutatavast elemendist saab algoritm pärast võrdlemist juursõlme vasaku või parema alampuu hõlpsalt eemaldada.

BST pakub teie kasutamiseks peamiselt järgmist kolme tüüpi toimingut:

• Otsing: otsib elementi binaarpuust.
• Lisa: lisab binaarpuule elemendi.
• Kustuta: kustutab elemendi binaarpuust.

Igal toimingul on oma struktuur ja täitmis-/analüüsimeetod, kuid kõige keerulisem on operatsioon Kustuta.

Otsing Operamine

Alusta puu analüüsimist alati juursõlmest ja liigu seejärel edasi juursõlme paremasse või vasakusse alampuusse, olenevalt sellest, kas otsitav element on juurest väiksem või suurem.

1. Otsitav element on 10.
2. Võrdle elementi juursõlmega 12, 10 < 12, seega liigud vasakpoolsesse alampuusse. Parempoolset alampuud pole vaja analüüsida.
3. Nüüd võrdle 10 sõlmega 7, 10 > 7, seega liigu paremale alampuule.
4. Seejärel võrdle 10 järgmise sõlmega, mis on 9, 10 > 9, vaata paremat alampuu last.
5. 10 kattub sõlme väärtusega, 10 = 10, tagastab väärtuse kasutajale.

Pseudo Code BST-s otsimiseks

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)

Sisesta Operamine

See on väga lihtne toiming. Esmalt lisatakse juursõlm ja seejärel võrreldakse järgmist väärtust juursõlmega. Kui väärtus on suurem kui juur, lisatakse see paremale alampuule ja kui see on väiksem kui juur, lisatakse see vasakule alampuule.

1. BST-sse tuleb vasakult paremale sisestada 6 elementi.
2. Sisesta juursõlmeks 12 ja võrdle järgmisi väärtusi 7 ja 9, et need vastavalt paremasse ja vasakusse alampuusse sisestada.
3. Võrdle ülejäänud väärtusi 19, 5 ja 10 juursõlmega 12 ja paiguta need vastavalt. Kui 19 > 12, aseta see 12 paremale lapsele; kui 5 < 12 ja 5 < 7, aseta see 7 vasakule lapsele. Nüüd võrdle 10 – 10 on < 12 ja 10 on > 7 ning 10 on > 9, aseta 10 9 paremale alampuule.

Pseudokood sõlme sisestamiseks BST-s

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

kustutama Operamine

BST-st sõlme kustutamiseks on mõned juhud, nt juure või lehe sõlme kustutamine. Pärast juure kustutamist peame mõtlema ka juursõlmele.

Oletame, et tahame kustutada lehesõlme, saame selle lihtsalt kustutada, aga kui tahame juurt kustutada, peame asendama juure väärtuse teise sõlmega. Võtame järgmise näite:

• Juhtum 1 – null lapsega sõlm: See on kõige lihtsam olukord, peate lihtsalt kustutama sõlme, millel pole paremal ega vasakul rohkem lapsi.
• Juhtum 2 – ühe lapsega sõlm: Kui olete sõlme kustutanud, ühendage selle alamsõlm lihtsalt kustutatud väärtuse vanemsõlmega.
• Juhtum 3 – Kahe lapsega sõlm: See on kõige keerulisem olukord ja see toimib järgmiste kahe reegli alusel:
  • 3a – Eelkäija järjekorras: Peate kustutama kahe lapsega sõlme ja asendama selle kustutatud sõlme vasakpoolses alampuus oleva suurima väärtusega.
  • 3b – Järeljärjekorras olev järglane: Peate kustutama kahe lapsega sõlme ja asendama selle kustutatud sõlme parempoolses alampuus asuva väikseima väärtusega.

1. See on esimene kustutamise juhtum, kus kustutatakse sõlm, millel pole lapsi. Nagu diagrammil näha, pole sõlmedel 19, 10 ja 5 lapsi. Kuid me kustutame sõlme 19.
2. Kustutage väärtus 19 ja eemaldage link sõlmest.
3. Vaadake BST uut struktuuri ilma 19-ta.

1. See on kustutamise teine ​​juhtum, kus kustutate sõlme, millel on üks laps. Nagu diagrammil näha, on sõlmel 9 üks laps.
2. Kustuta sõlm 9 ja asenda see selle alamsõlmega 10 ning lisa link 7-lt 10-le.
3. Vaadake BST uut struktuuri ilma 9-ta.

1. Siin kustutate sõlme 12, millel on kaks last.
2. Sõlme kustutamine toimub eelkäija reegli alusel, mis tähendab, et vasakpoolse 12-st koosneva alampuu suurim element asendab selle.
3. Kustuta sõlm 12 ja asenda see arvuga 10, kuna see on vasakpoolse alampuu suurim väärtus.
4. Vaadake BST uut struktuuri pärast 12 kustutamist.

1. Kustuta sõlm 12, millel on kaks last.
2. Sõlme kustutamine toimub järjekorrajärgse reegli alusel, mis tähendab, et parempoolse alampuu väikseim element 12-st asendab selle.
3. Kustuta sõlm 12 ja asenda see numbriga 19, kuna see on parempoolse alampuu väikseim väärtus.
4. Vaadake BST uut struktuuri pärast 12 kustutamist.

Pseudo Code sõlme kustutamiseks

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)

Olulised tingimused

• Lisa: Lisab puusse elemendi / loob puu.
• Otsing: Otsib elementi puust.
• Läbipääsu ettetellimine: Liigub puust mööda ettetellimisel.
• Sisejärjekorra läbimine: Liigub puu ümber kindlas järjekorras.
• Järeltellimuse läbimine: Liigub puu järeljärjekorras.

KKK