Esimene sügavus vs laius esimene otsing

Kui olete võtnud mis tahes kuju või vormi koodi uurimiseks aega, olete tõenäoliselt kohanud andmestruktuure. Andmestruktuurid koosnevad paljudest võimalustest andmete säilitamiseks, korraldamiseks ja manipuleerimiseks. Mõned populaarsemad neist hõlmavad massiive, lingitud loendeid, pinu, järjekordi ja binaarseid otsingupuid. Selle artikli huvides keskendume kahele erinevale viisile puude liikumisele lähenemisel: sügavuse esimene otsing ja laiuse esimene otsing.

Mis on puu?

Puu on andmestruktuur, mis koosneb sõlmedest, mis sisaldavad viiteid teistele sõlmedele. Erinevalt päriselus olevatest puudest (või võib-olla on need kuskil olemas) on andmepuu tagurpidi. Põhimõtteliselt on juur ülaosas ja lehed allosas.

Murdkem diagramm.

Igal puul on üks juursõlm, mis on ülaosas (antud juhul tase 0). Siis näeme, et järgmisel tasemel on juursõlmel A noodid sõlmedele B ja C. Samamoodi on sõlmedel B ja C nood noolega A. Selles olukorras on sõlme A algsõlm ning sõlmed B ja C on selle lapsed. Lisaks peetakse sõlmi B ja C õdedeks-vendadeks.

Teil võib tekkida küsimus, kas sõlmel on võimalik saada rohkem kui 2 last. Vastus on jah! See konkreetne kujundus on binaarsest puust, mille saab iga lapsevanema jaoks määrata maksimaalselt kahe lapsesõlmega.

Puukood

Kohustustest loobumine: kasutan Javascripti lihtsa puu loomiseks!

Esiteks peame looma sõlmeklassi:

Sõlme klassi loomisel anname sellele väärtuse või andmed, millest saab sõlme andmeomand. Meil on ka vanemate ja laste atribuudid, mis on nüüd null ja tühi massiiv. Lõpuks osutab vanema atribuut konkreetse sõlme vanemale ja laste atribuut osutab sõlme lastele.

Seejärel loome puuklassi:

Puuklass sisaldab ühte atribuuti juur, mis on alguses null. Puud sisaldavad prototüüpmeetodeid, nagu sisaldab (), sisestage () ja eemaldage (), kuid need salvestame vihmaseks päevaks!

Otsitakse!

Nii sügavus-esimene kui ka laius-esimene otsing on puuklassi prototüüpmeetodid, mida kasutatakse, et teha kindlaks, kas puus on konkreetseid andmeid sisaldavaid konkreetseid sõlme. Allpool toodud pilt näitab kahte erinevat otsimisprotseduuri.

Sügavus-esimene lähenemine

Esimene sügavusmeetod algab juursõlmest ja liigub kõige vasakpoolsema sõlme poole. Kui see on jõudnud kõige vasakpoolsemasse sõlme, liigub see puu tagasi juure ja seejärel kõige parempoolsemasse sõlme. Kui see tabab lastega sõlme, läbib see selle sõlme lapsi vasakult paremale ja jätkub siis paremale.

Otsimisjärjestus: [10, 4, 1, 9, 17, 12, 18]

Kood

Esimene sügavusotsing võtab väärtusena argumendina väärtuse, mida otsime puust. Kuna soovime liikuda sõlmedest vasakult paremale, seadsime juure virna, kuna tahame kasutada viimast sisse-välja lähenemist. Seejärel teostame mõne aja silmuse, mis jätkub seni, kuni virn sisaldab elemente. Samal ajal kui aas, eemaldame esimese elemendi virnast või kutsume massiivi vahetusmeetodi () ja seome selle võrdseks sõlmega. Võrdleme selle sõlme andmeid argumendi väärtusega ja kui need vastavad, siis vastab funktsioon tõele. Kui see pole nii, lisab see sõlme lapsed virna ette või kutsub välja massiivi tõmbamise () meetodi ja jätkab uute andmete otsimist. Kui konkreetset väärtust puus ei eksisteeri, tagastab funktsioon vale.

Laiuse esimene lähenemisviis

Laius-esimene lähenemisviis algab juursõlmest ja kulgeb läbi iga järgneva taseme soovitud sõlme otsimiseks. Sarnaselt esimese sügavuse lähenemisviisile loetakse sõlmi igal tasandil vasakult paremale.

Otsingukorraldus: [10, 4, 17, 1, 9, 12, 18]

Kood

Laiuse esimene otsing on koodis sarnane esimese sügavuse otsinguga. Argumendina tuleb leida väärtus. Erinevus seisneb selles, et virna kasutamise asemel tahame kasutada järjekorda, et saaksime kasutada lähenemist esimesena välja. Samal ajal kui aas, tahame sarnaselt esimese sügavuse otsinguga kasutada massiivi () massiivi, et järjekorra esimene element sõlmena eemaldada. Kui sõlme andmed ei ole soovitud väärtusega samad, kasutame sõlme laste nihutamise asemel nupu () massiivi meetodil laste lisamiseks järjekorra lõppu. See võimaldab meil kontrollida iga taseme sõlme enne järgmise taseme sõlmedest läbimist. Ja kui väärtust ei leita, tagastatakse funktsioon täpselt nagu esimene otsimine, kui väärtust ei leita, vale väärtus.

Mida ma kasutan?

Ehkki nii sügavus-esimene (DFS) kui ka laius-esimene (BFS) otsingud on õigustatud lähenemisviisid ja nende põhjal saab jõuda samadele järeldustele, eelistatakse neid teatud tingimustes mõlemat. Kuid sageli pole selge, kumb neist kahest on tõhusam.

Kohustustest loobumine: Need on üldised juhised! Kindlasti mitte alati kõige optimaalsemad lähenemisviisid.

DFS: Üldiselt eelistatakse, kui puu on väga sügav ja soovitud väärtused või andmed esinevad harva.

BFS: üldiselt eelistatakse madalates puudes, mis pole liiga laiad. Kasutatakse ka siis, kui on teada, et soovitud sõlm on juurtasemele lähemal.

Isegi kui teil on kindel, milliseid meetodeid kasutada, on kahtlemata parem proovida mõlemat meetodit ja vaadata, milline neist on tõhusam.

Näiteks oletame, et kasutate ülaltoodud puud ja otsite sõlme, mis sisaldab 8. Puu pole nii sügav, nii et võite arvata, et parem oleks kasutada BFS-i. Kuid tegelikult oleks tõhusam kasutada DFS-i.

Võrrelgem kahte meetodit ja seda, millistest sõlmedest on üle käidud:

DFS: 1, 2, 4, 8

BFS: 1, 2, 3, 4, 5, 6, 7, 8

Juba näeme, et lai otsing esimeses osas läbib rohkem sõlme ja vajab seetõttu juurdepääsu rohkem mälu.

Veelgi enam, kui oleme leidnud sõlme 8, oleks DFS-i virn [8, 9, 5, 3], samas kui BFS-i järjekord oleks [8, 9, 10, 11, 13, 14]. BFS-i järjekord sisaldab veel 2 sõlme, mis ei näi selles näites kuigi palju võrdsustavat, kuid mälu osas kasutab see siiski suuremat kogust. Seetõttu oleks DFS selles konkreetses olukorras tõhusam kui BFS.

Kuigi see näide on lihtne ja arusaadav, on olukordades, kus puud on sügavamad ja laiemad, kindlasti optimaalsema kindlaksmääramine. Parim viis parema meetodi dikteerimiseks on proovida mõlemat.

Keerukus

Aja ja ruumi keerukus nii DFS-i kui ka BFS-i jaoks on üsna sirgjooneline. Kuna räägime puu liikumisest, peame puu otsimiseks väärtuse või andmete kindlakstegemiseks külastama iga sõlme. Iga sõlme külastamine ühel ajal tähendab, et aja keerukus nii DFS kui ka BFS jaoks on O (n) või lineaarne. Kui mõtleme puudele kui sorteeritud massiividele, peaksime ainult ühe aja läbi tegema, et teha kindlaks, kas väärtus vastab otsitavale väärtusele või mitte. Samamoodi on ruumi keerukuse osas DFS O (h) ja BFS on O (w). DFS-i puhul tähistab „h” kõrgust, kuna see, kui palju ruumi funktsioon võtab, sõltub sellest, kui palju sõlme puus on. Samamoodi tähistab BFS-i puhul „w” laiust, kuna ruum sõltub sellest, kui lai puu on. Muidugi muutuvad need suured O märked sõltuvalt andmestruktuurist, kuid puude huvides on aja ja ruumi keerukus sama.

Täname, et leidsite aega selle artikli lugemiseks! Kui teil on tagasisidet või küsimusi, andke mulle sellest teada! Loodan, et sul on hea päev!