Mis on binaarne otsingupuu?

Binaarne otsingupuu on üks erinevatest andmestruktuuridest, mis aitab meil andmeid korrastada ja sortida. See on tõhus viis andmete hierarhias salvestamiseks ja väga paindlik.

Selles artiklis vaatleme üksikasjalikumalt selle toimimist, selle omadusi ja rakendusi.

Mis on binaarne otsingupuu?

Binaarne otsingupuu on andmestruktuur, mis koosneb sõlmedest – sarnaselt lingitud loendiga. Sõlme võib olla kahte tüüpi: vanem ja laps. Juursõlm on struktuuri alguspunkt, mis hargneb kaheks alamsõlmeks, mida nimetatakse vasak- ja paremsõlmeks.

Igale sõlmele saab viidata ainult selle ülem ja me saame puu sõlmedest sõltuvalt suunast läbida. Binaarsel otsingupuul on kolm peamist atribuuti:

1. Vasak sõlm on väiksem kui selle ülem.
2. Parem sõlm on suurem kui selle ülem.
3. Vasak ja parem alampuud peavad olema binaarsed otsingupuud.

Täiuslik binaarne otsingupuu saavutatakse, kui kõik tasemed on täidetud ja igal sõlmel on vasak ja parem alamsõlm.

Seotud: Andmeteaduse raamatukogud Pythoni jaoks, mida peaks kasutama iga andmeteadlane

Binaarse otsingupuu põhitoimingud

Nüüd on teil binaarne otsingupuu parem ülevaade, saame vaadata selle põhitoiminguid allpool.

1. Otsinguoperatsioon

Otsing võimaldab meil leida puus oleva konkreetse väärtuse. Saame kasutada kahte tüüpi otsinguid: laiuseotsing (BFS) ja sügavus-eesotsing (DFS). Laiuseotsing on otsingualgoritm, mis algab juursõlmest ja liigub horisontaalselt, küljelt küljele, kuni eesmärk on leitud. Iga sõlme külastatakse selle otsingu jooksul üks kord.

Sügavus-esimene otsing seevastu läbib puu vertikaalselt – alustades juursõlmest ja liikudes ühe haru võrra alla. Kui eesmärk on leitud, operatsioon lõpeb. Aga kui ei, siis see ja otsib teisi sõlme.

2. Sisestamise toiming

Lisamisoperatsioon kasutab otsingutoimingut, et määrata asukoht, kuhu uus sõlm tuleks sisestada. Protsess algab juursõlmest ja otsing algab kuni sihtkohani jõutakse. Sisestamisel tuleb arvestada kolme juhtumiga.

• 1. juhtum: kui sõlme pole olemas. Sisestatavast sõlmest saab juursõlm.

• Juhtum 2: lapsi pole. Sel juhul võrreldakse sõlme juursõlmega. Kui see on suurem, saab sellest õige laps; vastasel juhul saab sellest vasak laps.

• Juhtum 3: kui juur ja selle lapsed on kohal. Uut sõlme võrreldakse iga selle teekonna sõlmega, et teha kindlaks, millist sõlme see järgmisena külastab. Kui sõlm on suurem kui juursõlm, liigub see mööda parempoolset alampuud alla või siis vasakule. Samamoodi tehakse igal tasandil võrdlusi, et teha kindlaks, kas see liigub sihtkohta jõudmiseni paremale või vasakule.

3. Kustutamisoperatsioon

Kustutustoimingut kasutatakse puu konkreetse sõlme eemaldamiseks. Kustutamist peetakse keeruliseks, kuna pärast sõlme eemaldamist tuleb puu vastavalt ümber korraldada. Arvesse tuleb võtta kolme peamist juhtumit:

• 1. juhtum: lehesõlme kustutamine. Lehesõlm on sõlm, kus pole lapsi. Seda on kõige lihtsam eemaldada, kuna see ei mõjuta ühtegi teist sõlme; me lihtsalt läbime puu, kuni jõuame selleni ja kustutame selle.

• 2. juhtum: sõlme kustutamine ühe lapsega. Ühe sõlmega vanema kustutamisel võtab laps oma positsiooni ja kõik järgnevad sõlmed liiguvad taseme võrra kõrgemale. Alampuude struktuuris muudatusi ei toimu.

• 3. juhtum: kahe lapsega sõlme kustutamine. Kui peame eemaldama kahe lapsega sõlme, peame esmalt leidma järgmise sõlme, mis suudab oma positsiooni võtta. Kaks sõlme võivad asendada eemaldatud sõlme, järjestikuse järglase või eelkäija. Järjekorra järglane on parempoolse alampuu vasakpoolseim alam ja järjestuse eelkäija on vasaku alampuu parempoolseim alam. Kopeerime järglase/eelkäija sisu sõlme ja kustutame järjestikuse järglase/eelkäija.

Seotud: Kuidas luua andmestruktuure JavaScripti ES6 klassidega

Kuidas läbida binaarset otsingupuud

Läbimine on protsess, mille kaudu me binaarses otsingupuus navigeerime. Seda tehakse konkreetse üksuse asukoha leidmiseks või puu kontuuri printimiseks. Alustame alati juursõlmest ja teistesse sõlmedesse jõudmiseks peame järgima servi. Iga sõlme tuleks käsitleda alampuuna ja protsessi korratakse, kuni kõik sõlmed on külastatud.

• Tellimuses läbimine: Järjekorras läbimine loob kaardi kasvavas järjekorras. Selle meetodi puhul alustame vasakpoolsest alampuust ja jätkame juure ja parema alampuuga.

• Ettetellimise läbimine: Selle meetodi puhul külastatakse kõigepealt juursõlme, seejärel vasakpoolset alampuud ja paremat alampuud.

• Tellimusjärgne läbimine: See läbimine hõlmab juursõlme külastamist viimasena. Alustame vasakpoolsest alampuust, siis paremast alampuust ja seejärel juursõlmest.

Reaalmaailma rakendused

Niisiis, kuidas kasutada binaarseid otsingupuu algoritme? Nagu arvata võib, on need otsimisel ja sortimisel ülimalt tõhusad. Kahekordsete puude suurim tugevus on nende organiseeritud struktuur. See võimaldab otsingut teha märkimisväärse kiirusega, vähendades ühe läbimise kohta analüüsitavate andmete hulka poole võrra.

Binaarsed otsingupuud võimaldavad meil tõhusalt hallata dünaamiliselt muutuvat andmekogumit organiseeritud kujul. Rakenduste jaoks, millesse andmeid sageli sisestatakse ja eemaldatakse, on need väga kasulikud. Videomängumootorid kasutavad binaarse ruumipartitsioonina tuntud puudel põhinevat algoritmi, mis aitab objektide korrastada. Microsoft Excel ja enamik arvutustabelitarkvarasid kasutavad põhiandmestruktuurina binaarpuid.

Võite olla üllatunud, kui teate, et morsekood kasutab andmete kodeerimiseks binaarset otsingupuud. Teine silmapaistev põhjus, miks binaarsed otsingupuud on nii kasulikud, on nende mitmed variatsioonid. Nende paindlikkus on viinud selleni, et igasuguste probleemide lahendamiseks on loodud arvukalt variante. Õige kasutamise korral on binaarsed otsingupuud suurepärane väärtus.

Binaarsed otsingupuud: ideaalne lähtepunkt

Üks peamisi viise inseneri teadmiste hindamiseks on nende teadmised ja andmestruktuuride rakendamine. Andmestruktuurid on abiks ja võivad aidata luua tõhusamat süsteemi. Binaarsed otsingupuud on suurepärane sissejuhatus andmestruktuuridesse igale alustavale arendajale.

15 JavaScripti massiivi meetodit, mida peaksite juba täna valdama

Kas soovite JavaScripti massiive mõista, kuid ei saa nendega hakkama? Juhiste saamiseks vaadake meie JavaScripti massiivi näiteid.

Loe edasi

Autori kohta