Binaarotsingupuu (BST) koos näitega

Mis on binaarne otsingupuu?

Binaarotsingupuu on arenenud algoritm, mida kasutatakse sõlme, selle vasaku ja parema haru analüüsimiseks, mis on modelleeritud puu struktuuris ja tagastab väärtuse. BST on välja töötatud binaarse otsingu algoritmi arhitektuuril; seega võimaldab see kiiremat otsimist, sisestamist ja sõlmede eemaldamist. See muudab programmi tõeliselt kiireks ja täpseks.

Selles andmestruktuuri õpetuses saate teada:

• Mis on binaarne otsingupuu?
• Binaarse otsingupuu atribuudid
• Miks me vajame binaarset otsingupuud?
• Binaarpuude tüübid
• Kuidas binaarne otsingupuu töötab?
• Olulised tingimused

Binaarse otsingupuu atribuudid

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

• Puu sõlmed on esindatud vanema ja lapse suhetes
• Igal vanemsõlmel võib olla null alamsõlme või vasakul ja paremal küljel maksimaalselt kaks alamsõlme või alampuud.
• Igal alampuul, mida nimetatakse ka binaarseks otsingupuuks, on endast paremal ja vasakul alamharud.
• Kõik sõlmed on seotud võtme-väärtuse paaridega.
• Vasakul alampuul olevate sõlmede võtmed on väiksemad kui nende vanemasõlme võtmed
• Samamoodi on vasakpoolsete alampuu sõlmede võtmetel väiksemad väärtused kui nende vanemsõlme võtmetel.

1. Seal on põhisõlm või vanemtase 11. Selle all on vasakpoolsed ja paremad sõlmed / harud, millel on oma võtmeväärtused
2. Parema alampuu võtmeväärtused on suuremad kui vanemasõlmel
3. Vasakul alampuul on väärtused kui vanemasõlmel

Miks me vajame binaarset otsingupuud?

• Kaks peamist tegurit, mis muudavad binaarse otsingupuu optimaalseks lahenduseks reaalsetes probleemides, on kiirus ja täpsus.
• Tulenevalt asjaolust, et binaarotsing on vanema ja lapse suhetega haru-laadses formaadis, teab algoritm, millises puu asukohas on elemente vaja otsida. See vähendab võtmeväärtuste võrdluste arvu, mida programm peab tegema soovitud elemendi leidmiseks.
• Lisaks, kui otsitav element on suurem või väiksem kui vanemasõlm, teab sõlm, millist puupoolt otsida. Põhjus on see, et vasak alampuu on alati väiksem kui vanemasõlm ja parempoolse alampuu väärtused on alati võrdsed või suuremad kui vanemasõlm.
• BST-d kasutatakse tavaliselt keerukate otsingute, usaldusväärse mänguloogika, automaatse lõpuleviimise ja graafika rakendamiseks.
• Algoritm toetab tõhusalt selliseid toiminguid nagu otsing, sisestamine ja kustutamine.

Binaarpuude tüübid

Kolme tüüpi binaarseid puid 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 vasakpoolset.
• Täisbinaarne puu: kõigil sõlmpunktidel on 2 lapsesõlme, välja arvatud leht.
• Tasakaalus või täiuslik kahendpuu: puus on kõigil sõlmedel kaks last. Pealegi on igas alamsõlmes sama tase.

Kuidas binaarne otsingupuu töötab?

Puus on alati juuresõlm ja edasised lapse sõlmed, kas vasakul või paremal. Algoritm täidab kõik toimingud, võrreldes väärtusi vastavalt juurega ja selle edasiste allsõlmedega vasakus või paremas alampuus.

Sõltuvalt lisatavast, otsitavast või kustutatavast elemendist saab algoritm pärast võrdlust hõlpsasti juursõlme vasaku või parema alampuu langetada.

BST pakub teie kasutuseks peamiselt kolme tüüpi toiminguid:

• Otsing: otsib elementi binaarpuust
• Insert: lisab binaarpuule elemendi
• Kustuta: elemendi kustutamine binaarpuust

Igal toimingul on oma ülesehitus ja teostamis- / analüüsimeetod, kuid kõige keerulisem on Kustuta operatsioon.

Otsinguoperatsioon

Alustage puu analüüsimine alati juuresõlmes ja seejärel liikuge edasi kas juursõlme paremale või vasakule alampuule sõltuvalt sellest, kas paiknev 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. Nüüd võrrelge 10 sõlmega 7, 10> 7, seega minge paremale alampuule
4. Seejärel võrrelge 10 järgmise sõlmega, milleks on 9, 10> 9, otsige paremast alampuu lapsest
5. 10 vastab sõlmes olevale väärtusele, 10 = 10, tagastab kasutajale väärtuse.

Sisesta toiming

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 paremale alampuule ja kui see on väiksem kui juur, lisatakse see vasakule alampuule.

1. Seal on nimekiri 6 elemendist, mis tuleb BST-sse lisada vasakult paremale järjestuses
2. Sisestage juursõlmeks 12 ja võrrelge järgmisi väärtusi 7 ja 9 vastavalt paremale ja vasakule alampuule
3. Võrrelge ülejäänud väärtusi 19, 5 ja 10 juursõlmega 12 ja asetage need vastavalt. 19> 12 asetage see 12-aastase lapse parema, 5 <12 & 5 <7-aastase lapsena, seega asetage see 7-aastase vasaku lapsena.
   1. Nüüd võrrelge 10, 10 on <12 ja 10 on> 7 ja 10 on> 9, asetage 10 paremale alampuuks 9.

Kustuta toimingud

Kustutamine on kõigi teiste toimingute seas kõige arenenum ja keerulisem. BST-is on kustutamiseks mitu juhtumit.

• Juhtum 1 - sõlm, kus on null last: see on kõige lihtsam olukord, peate lihtsalt kustutama sõlme, millel pole enam lapsi paremal ega vasakul.
• 2. juhtum - sõlm ühe lapsega: kui olete sõlme kustutanud, ühendage selle alamsõlm lihtsalt kustutatud väärtuse vanemasõlmega.
• Juhtum 3 Kahe lapsega sõlm: see on kõige keerulisem olukord ja see töötab järgmise kahe reegli järgi
  • 3a - tellimuses Eelkäija: peate kustutama kahe lapsega sõlme ja asendama selle suurima väärtusega kustutatud sõlme vasakul alampuul
  • 3b - tellimusjärglases: peate kustutama kahe lapsega sõlme ja asendama selle suurima väärtusega kustutatud sõlme parempoolsel alampuul

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

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

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 vasakpoolse alampuu 12 suurim element asendab selle.
3. Kustutage sõlm 12 ja asendage see 10-ga, kuna see on vasaku alampuu suurim väärtus
4. Vaadake BST-i uut struktuuri pärast 12 kustutamist

1. 1 Kustutage sõlm 12, millel on kaks last
2. 2 Sõlme kustutamine toimub reeglis In Order Successor, mis tähendab, et parempoolse 12 alampuu suurim element asendab selle
3. 3 Kustutage sõlm 12 ja asendage see 19-ga, kuna see on parempoolse alampuu suurim väärtus
4. 4 Vaadake BST-i uut struktuuri pärast 12 kustutamist

Olulised tingimused

• Lisa - lisab puu elemendi / loob puu.
• Otsi - otsib puust elementi.
• Ettetellimise läbimine - läbib puu ettetellimisel.
• Inorder Traversal - läbib puu järjekorras.
• Postorder Traversal - läbib puu järeltellimusel.

Kokkuvõte

• BST on kõrgtasemel algoritm, mis teeb erinevaid toiminguid, lähtudes sõlme väärtuste võrdlemisest juursõlmega.
• Ükskõik milline vanema ja lapse hierarhia punktidest tähistab sõlme. Vähemalt üks vanem- või juursõlm jääb kogu aeg kohal olema.
• Seal on vasak ja parem alampuu. Vasak 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, ühe lapsega sõlm ja kahe lapsega sõlm.
• Algoritmi kasutatakse reaalsetes lahendustes nagu mängud, automaatse täitmise andmed ja graafika.