Dýpt-fyrst vs breidd-fyrsta leit

Ef þú hefur tekið þér tíma til að kynna þér kóða í hvaða formi sem sem er eða í hvaða formi, hefurðu líklega rekist á gagnaskipulag. Uppbygging gagna samanstendur af fjölda möguleika til að geyma, skipuleggja og vinna með gögn. Sumir af þeim vinsælli eru fylki, tengd listar, staflar, biðraðir og tvöfaldar leitatré. Í þágu þessarar greinar munum við einbeita okkur að tveimur mismunandi leiðum til að nálgast trjágöng: dýptar-fyrsta leit og breiddar-fyrstu leit.

Hvað er tré?

Tré er gagnaskipulag sem samanstendur af hnútum, sem innihalda ábendingar til annarra hnúta. Ólíkt trjám í raunveruleikanum (eða kannski að þau séu til einhvers staðar) er gagnatréð á hvolfi. Í meginatriðum er rótin efst og laufin eru neðst.

Við skulum sundurliða skýringarmyndina.

Hvert tré hefur einn rótarhnút sem er á efsta stigi (í þessu tilfelli, stig 0). Þá sjáum við að á næsta stigi hefur rótarhnúturinn A ábendingar um hnútana B og C. Sömuleiðis hafa hnútarnir B og C ábendingar að hnútnum A. Í þessum aðstæðum er hnúturinn A foreldrihnútinn og hnútarnir B og C eru börn þess. Ennfremur eru hnútar B og C talin systkini.

Þú gætir verið að spá í hvort það sé mögulegt fyrir hnút að eiga fleiri en 2 börn. Svarið er já! Þessi sérstaka lýsing er af tvíundartré sem hægt er að ákvarða að hámarki tveimur barnamótum fyrir hvert foreldri.

Trékóði

Fyrirvari: Ég mun nota Javascript til að búa til einfalt tré!

Í fyrsta lagi verðum við að búa til hnútaflokk:

Þegar við búum til hnútaflokk þá gefum við það gildi, eða gögn, sem verður gagnaeining hnútins. Við erum líka með foreldra og börn sem eru núll og tóm fylki í bili. Að lokum mun foreldrieignin vísa til foreldris viðkomandi hnút og eignir barna benda á börn hnútins.

Síðan búum við til trjáflokkinn:

Tréflokkurinn inniheldur eina eign, rót, sem er upphaflega engin. Tré innihalda frumgerð aðferðir eins og inniheldur (), setja inn () og fjarlægja (), en við munum spara þær fyrir rigningardag!

Leita!

Bæði dýptar-fyrst og breidd-fyrsta leit eru frumgerð aðferða í tréflokknum sem notaðar eru til að ákvarða hvort tiltekinn hnút sem inniheldur sérstök gögn sé til í tré. Skýringin hér að neðan sýnir mismunandi leitaraðferðir.

Dýpt-fyrsta nálgun

Fyrsta dýptaraðferðin byrjar við rótarhnútinn og færist í átt að hnútinn vinstra megin. Þegar það smellir á vinstri hnútinn fer það upp tréð aftur að rótinni og síðan til hægri hnútsins. Ef það lendir í hnút með börnum mun það fara um börn þess hnút frá vinstri til hægri og halda síðan áfram til hægri.

Leitaröð: [10, 4, 1, 9, 17, 12, 18]

Kóði

Fyrsta dýptarleit tekur gildi sem rök sem er gildi sem við erum að leita að í trénu. Þar sem við viljum fara yfir hnútana frá vinstri til hægri setjum við rótina sem stafla af því að við viljum taka síðustu í fyrstu aðferð. Þá gerum við stundarlykkju sem heldur áfram svo lengi sem stafla inniheldur þætti. Innan tíma lykkjunnar fjarlægjum við fyrsta þáttinn í staflinum, eða köllum vaktaraðferðina () og setjum það jafnt og hnút. Við berum saman gögn þess hnút við rökgildið og ef þau passa saman skilar aðgerðin gildi. Ef þetta er ekki tilfellið bætir það börnum hnútins framan við stafla, eða kallar unshift () fylkisaðferðina og heldur áfram að leita í gegnum nýju gögnin. Ef tiltekna gildið er ekki til í trénu skilar aðgerðin ósönn.

Breidd - fyrsta nálgun

Fyrsta breidd aðferðin byrjar við rótarhnútinn og fer í gegnum hvert stig í röð til að leita að viðeigandi hnút. Á sama hátt og fyrstu dýptaraðferðina eru hnútarnir lesnir frá vinstri til hægri á hverju stigi.

Leitaröð: [10, 4, 17, 1, 9, 12, 18]

Kóði

Fyrsta breiddarleit er svipuð í kóða og fyrstu dýptarleit. Það tekur inn gildi sem finnast sem rök. Munurinn hér er sá að í stað þess að nota stafla viljum við nota biðröð til að geta tekið fyrstu í fyrstu aðferð. Í meðan lykkjunni, á svipaðan hátt og fyrstu dýptarleitina, viljum við nota vaktunaraðferðina () fyrir að fjarlægja fyrsta þáttinn í biðröðinni sem hnút. Hins vegar, ef hnútargögnin eru ekki þau sömu og gildið sem óskað er eftir, í stað þess að taka börn hnút frá, notum við ýta () fylkisaðferðina til að bæta börnunum við lok biðröðarinnar. Þetta gerir okkur kleift að athuga hvern hnút í stigi áður en farið er um hnútana á næsta stig. Að lokum, rétt eins og fyrstu dýptarleit, ef gildið er ekki að finna skilar aðgerðin ósönn.

Hvaða nota ég?

Þó að bæði dýptar-fyrst (DFS) og breidd-fyrst (BFS) leit séu réttmætar aðferðir og geta komist að sömu niðurstöðum, er hverjum og einum ívilnað undir vissum kringumstæðum. Hins vegar er ekki oft augljóst hver sá er skilvirkari af þessum tveimur.

Fyrirvari: Þetta eru almennar leiðbeiningar! Örugglega ekki alltaf ákjósanlegustu aðferðirnar.

DFS: Almennt valinn þegar tréð er mjög djúpt og æskilegt gildi eða gögn koma sjaldan fyrir.

BFS: Almennt valinn á grunnum trjám sem eru ekki of breiðar. Einnig notað ef vitað er að viðkomandi hnút er nær rótarstigi.

Jafnvel þó að það séu almennar ákvarðanir þegar þú ákveður hvaða aðferð á að nota, ef þú ert ekki viss, þá er það líklega betra að prófa báðar aðferðirnar og sjá hvaða aðferð er skilvirkari.

Við skulum til dæmis segja að þú notir tréð hér að ofan og þú ert að leita að hnútnum sem inniheldur 8. Trén er ekki svo djúpt svo þú gætir haldið að það væri betra að nota BFS. Hins vegar væri í raun skilvirkara að nota DFS.

Við skulum bera saman þessar tvær aðferðir og hvaða hnúður hafa farið yfir:

DFS: 1, 2, 4, 8

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

Nú þegar getum við séð að fyrstu breidd leit fer í gegnum fleiri hnúta og þarf því aðgang að meira minni.

Enn fremur, þegar við staðsetjum hnút 8, væri DFS stafla [8, 9, 5, 3] meðan BFS biðröðin væri [8, 9, 10, 11, 13, 14]. BFS biðröðin inniheldur 2 hnúta til viðbótar, sem virðast ekki jafnast mikið á við í þessu dæmi, en hvað varðar minni, þá notar hann ennþá meira magn. Þess vegna, í þessu tiltekna ástandi, væri DFS skilvirkara en BFS.

Þó að þetta dæmi sé einfalt og beint, við aðstæður þar sem tré eru dýpri og breiðari, þá er það örugglega miklu erfiðara að ákvarða hver er best. Besta leiðin til að fyrirmæla betri aðferð er að reyna hvort tveggja.

Flækjustig

Tími og rúm flækjustig bæði DFS og BFS eru nokkuð einföld. Þar sem við erum að tala um trjágöngum, verðum við að heimsækja hvern hnút til að ákvarða hvort gildi eða gögn séu til í trénu. Að heimsækja hvern hnút í einu þýðir að tímaflækjan bæði fyrir DFS og BFS er O (n) eða línuleg. Ef við hugsum um tré sem flokkaða fylki, þá þyrftum við aðeins að fara í gegnum einn tíma til að ákvarða hvort gildi samsvari gildinu sem við erum að leita að. Að sama skapi hvað varðar plássflækjustig er DFS O (h) og BFS O (w). Fyrir DFS stendur 'h' fyrir hæð þar sem hversu mikið pláss aðgerðin tekur, fer eftir því hve margir hnútar djúpt tréð er. Sömuleiðis, fyrir BFS, stendur 'w' fyrir breidd, þar sem rými fer eftir því hversu breitt tréð er. Auðvitað breytast þessar stóru O-merkingar eftir gögnum, en fyrir tré verður tíminn og plássin margbrotin.

Þakka þér fyrir að gefa þér tíma til að lesa þessa grein! Ef þú hefur einhverjar athugasemdir eða spurningar, láttu mig vita! Vona að þú hafir frábæran dag!