Binaarne otsingupuu (BST) koos näitega

Binaarse otsingupuu atribuudid

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

• Puu sõlmed on esindatud vanema ja lapse suhetes
• 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 olevate sõlmede võtmed on väiksemad kui nende emasõlme võtmed
• Samamoodi on vasakpoolsete alampuu sõlmede võtmetel väiksemad väärtused kui nende emasõlme võtmetel.

1. Seal on põhisõlm ehk vanemtase 11. Selle all on vasak ja parem sõlm/harud oma võtmeväärtustega
2. Parempoolse alampuu võtmeväärtused on suuremad kui emasõlmel
3. Vasakpoolsel alampuul on väärtused kui emasõlmel

Miks me vajame binaarset otsingupuud?

• Kaks peamist tegurit, mis muudavad binaarse otsingupuu optimaalseks lahenduseks mis tahes reaalmaailma probleemidele, 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 emasõlm, teab sõlm, millist puu poolt otsida. Põhjus on selles, et vasakpoolne alampuu on alati väiksem kui emasõlm ja parempoolsel alampuul on väärtused, mis on alati võrdsed või suuremad kui emasõlme.
• 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 kahendpuu: kõik puude tasemed on täis viimase taseme võimalikke erandeid. Samamoodi on kõik sõlmed täis, suunates vasakpoolsesse serva.
• Täielik kahendpuu: kõigil sõlmedel on 2 alamsõlme, välja arvatud leht.
• Tasakaalustatud või täiuslik kahendpuu: puu kõigil sõlmedel on 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.

Olenevalt lisatavast, otsitavast või kustutatavast elemendist võib algoritm pärast võrdlust juursõlme vasaku või parema alampuu hõlpsalt maha jätta.

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

• Otsi: otsib elementi binaarpuust
• Sisesta: lisab elemendi kahendpuusse
• Kustuta: elemendi kustutamine binaarpuust

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

Otsing Operamine

Alustage puu analüüsimist alati juursõlmest ja liikuge seejärel juursõlme parempoolsesse või vasakpoolsesse alampuusse, sõltuvalt sellest, kas asuv element on juurest väiksem või suurem.

1. Otsitav element on 10
2. Võrrelge elementi juursõlmega 12, 10 < 12, seega liigute vasakule alampuule. Parempoolset alampuud pole vaja analüüsida
3. Võrrelge nüüd 10 sõlmega 7, 10 > 7, nii et liikuge parempoolsesse alampuusse
4. Seejärel võrrelge 10 järgmise sõlmega, mis on 9, 10 > 9, vaadake parempoolset alampuu alampuud
5. 10 kattub sõlme väärtusega, 10 = 10, tagastab väärtuse kasutajale.

Pseudokood 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 sirgjooneline operatsioon. Esiteks sisestatakse juursõlm, seejärel võrreldakse järgmist väärtust juursõlmega. Kui väärtus on suurem kui juur, lisatakse see parempoolsesse alampuusse ja kui see on väiksem kui juur, lisatakse see vasakpoolsesse alampuusse.

1. Seal on 6 elemendi loend, mis tuleb BST-sse sisestada vasakult paremale
2. Sisestage juursõlmeks 12 ja võrrelge järgmisi väärtusi 7 ja 9, et sisestada vastavalt parem- ja vasakpoolsesse alampuusse
3. Võrrelge ülejäänud väärtusi 19, 5 ja 10 juursõlmega 12 ja asetage need vastavalt. 19 > 12 asetage see 12 parema lapsena, 5 < 12 & 5 < 7, seega asetage see 7. vasaku lapsena. Nüüd võrrelge 10, 10 on < 12 ja 10 on > 7 ja 10 on > 9, koht 10 9 parempoolse alampuuna.

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

Sõlme kustutamiseks BST-st on teatud juhtumeid, st juure või lehesõlme kustutamine. Samuti peame pärast juure kustutamist mõtlema 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 – sõlm nulli lapsega: see on kõige lihtsam olukord, peate lihtsalt kustutama sõlm, millel ei ole rohkem lapsi paremal ega vasakul.
• Juhtum 2 – sõlm ühe alamsõlmega: pärast sõlme kustutamist ühendage selle alamsõlm lihtsalt kustutatud väärtuse emasõlmega.
• Juhtum 3 Sõlm kahe lapsega: see on kõige keerulisem olukord ja see toimib kahe järgmise reegli alusel
• 3a – järjekorras eelkäija: peate kustutama kahe lapsega sõlme ja asendama selle kustutatud sõlme vasakpoolse alampuu suurima väärtusega
• 3b – Järjekorra järglane: peate kustutama kahe lapsega sõlme ja asendama selle kustutatud sõlme parempoolse alampuu suurima väärtusega

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

1. See on teine ​​kustutamise juhtum, kus kustutate sõlme, millel on 1 laps, nagu näete diagrammil, et 9-l on üks laps.
2. Kustutage sõlm 9 ja asendage see alamnumbriga 10 ning lisage link vahemikus 7 kuni 10
3. Vaadake BST uut struktuuri ilma 9

1. Siin kustutate sõlme 12, millel on kaks last
2. Sõlme kustutamine toimub järjekorras eelkäija reegli alusel, mis tähendab, et selle asendab suurim element vasakul alampuul 12.
3. Kustutage sõlm 12 ja asendage see 10-ga, kuna see on vasakpoolse alampuu suurim väärtus
4. Pärast 12 kustutamist vaadake BST uut struktuuri

1. 1 Kustutage sõlm 12, millel on kaks last
2. 2 Sõlme kustutamine toimub järjekorras järglase reegli alusel, mis tähendab, et parempoolse alampuu suurim element 12 asendab selle
3. 3 Kustutage sõlm 12 ja asendage see 19-ga, kuna see on parempoolse alampuu suurim väärtus
4. 4 Pärast 12 kustutamist vaadake BST uut struktuuri

Pseudokood 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 to the root #we're deleting the successor
    	free(newNode)
    else
    	free(y)

Olulised tingimused

• Sisesta: lisab puusse elemendi/loo puu.
• Otsi: otsib puust elementi.
• Ettetellimise läbimine: läbib puu ettetellimisel.
• Inorder Traversal: läbib puu õiges järjekorras.
• Postorder Traversal: läbib puu tellimisjärgselt.

kokkuvõte

• BST on täiustatud taseme algoritm, mis teostab erinevaid toiminguid, mis põhinevad sõlme väärtuste võrdlemisel juursõlmega.
• Ükskõik milline punkt vanem-laps-hierarhias esindab sõlme. Vähemalt üks ülem- või juursõlm jääb kogu aeg kohal olema.
• Seal on vasak alampuu ja parem alampuu. Vasakpoolne alampuu sisaldab väärtusi, mis on väiksemad kui juursõlm. Parempoolne alampuu sisaldab aga väärtust, mis on suurem kui juursõlm.
• Igal sõlmel võib olla kas null, üks või kaks last.
• Binaarne otsingupuu hõlbustab peamisi toiminguid, nagu otsing, sisestamine ja kustutamine.
• Kustutamisel on kõige keerulisem mitu juhtumit, näiteks sõlm ilma lapseta, sõlm ühe lapsega ja sõlm kahe lapsega.
• Algoritmi kasutatakse reaalsetes lahendustes, nagu mängud, automaatse täitmise andmed ja graafika.