[Powered by Google Translate] [Cuardaigh Dénártha] [Patrick Schmid - Ollscoil Harvard] Is é [seo CS50. - CS50.TV] 

Má thug mé tú le liosta ainmneacha carachtar Disney in ord aibítre agus d'iarr tú a fháil Mickey Luiche, conas a théann faoi é seo a dhéanamh? Slí amháin soiléir a bheith a scanadh ar an liosta ó thús agus seiceáil gach ainm a fheiceáil má tá sé Mickey. Ach mar a léann tú Aladdin, Alice, Ariel, agus mar sin de, go mbainfidh tú realize tapa nach tosú ag an tosaigh an liosta a bhí ag smaoineamh maith. Maith go leor, b'fhéidir ba chóir duit tosú ag obair ar gcúl ó dheireadh an liosta. Anois, léigh tú Tarzan, Stitch, Snow White, agus mar sin de. Fós, ní hionann sin is cosúil mhaith an bealach is fearr chun dul faoi. 

Bhuel, tá ar bhealach eile gur féidir leat dul faoi é seo a dhéanamh chun iarracht a caol síos liosta ainmneacha na go bhfuil tú chun breathnú ar. Ós rud é a fhios agat go bhfuil siad in ord aibítre, d'fhéadfaí tú ach breathnú ar na hainmneacha i lár an liosta agus seiceáil má tá Mickey Mouse roimh nó tar éis an ainm seo. Ag Breathnú ar an t-ainm deireanach sa dara colún gur mhaith leat a thuiscint go M haghaidh Mickey thagann i ndiaidh J le haghaidh Jasmine, ionas gur mhaith leat neamhaird a dhéanamh ach an chéad leath den liosta. Ansin gur mhaith leat breathnú is dócha ag barr an cholún deireanach agus a fheiceáil go dtosaíonn sé le Rapunzel. Mickey thagann roimh Rapunzel; Breathnaíonn an nós féidir linn neamhaird a dhéanamh den cholún deireanach chomh maith. Ag leanúint leis an straitéis cuardaigh, feicfidh tú go tapa go Mickey Is é sa chéad leath de liosta eile na n-ainmneacha agus a fháil ar deireadh Mickey bhfolach idir Merlin agus Minnie. 

Bhí Cad a rinne tú díreach search bunúsach dénártha. Mar Ciallaíonn an t-ainm, a chomhlíonann sé a straitéis a chuardach i ní dénártha. Cad a chiallaíonn sé seo? Bhuel, tugtar liosta de na míreanna sórtáilte, cuireann an algartam cuardaigh dénártha cinneadh dénártha - chlé nó ceart, níos mó ná nó níos lú ná, in ord aibítre roimh nó tar éis - ag gach pointe. Anois go bhfuil muid ainm a théann in éineacht leis an algartam cuardaigh, ligean ar breathnú ar shampla eile, ach an uair seo le liosta de uimhreacha curtha in eagar. Abair táimid ag lorg an uimhir 144 sa liosta d'uimhreacha in eagar. Díreach mar a bhíodh, feicimid an uimhir sin i lár - atá sa chás seo 13 - agus a fheiceáil má tá níos mó ná 144 nó níos lú ná 13. Ós rud é go bhfuil sé soiléir níos mó ná 13, is féidir linn neamhaird a dhéanamh gach rud go bhfuil 13 nó níos lú agus díriú ach ar an leath eile. Ós rud é go bhfuil muid anois ar líon na n-ítimí ar chlé, fiú, táimid a roghnú ach roinnt atá in aice leis an lár. Sa chás seo roghnaigh muid 55. D'fhéadfadh muid a bheith chomh héasca céanna roghnaithe 89. Maith go leor. Arís, tá 144 níos mó ná 55, mar sin againn dul go dtí an ceart. Fortunately dúinn, is é an uimhir lár chéad 144, an ceann táimid ag lorg. Mar sin, chun teacht ar 144 ag baint úsáide as cuardaigh dénártha, tá muid in ann a aimsiú i ach 3 céimeanna. Má ba mhaith linn a úsáid cuardaigh líneach anseo, bheadh ​​sé tar éis dúinn 12 céimeanna. Mar ábhar na fírinne, ós rud é leatha an modh cuardaigh líon na míreanna tá sé chun breathnú ar ag gach céim, beidh sé teacht ar an mír go bhfuil sé ag lorg i thart ar an logáil isteach ar líon na míreanna ar an liosta. Anois go atá feicthe againn 2 samplaí, a ligean ar ghlacadh le breathnú ar roinnt pseudocode maidir le feidhm athchúrsach go gcuireann cuardaigh dénártha. Ag tosú ag an mbarr, a fheicimid go bhfuil muid a aimsiú feidhm a thógann 4 hargóintí: eochair, eagar, min, agus uas. Is í an eochair an líon go bhfuil muid ag lorg, mar sin 144 sa sampla roimhe seo. Is é Eagar liosta na huimhreacha go bhfuil muid ag cuardach. Tá Min agus uas na hinnéacsanna de na poist íosta agus uasta go bhfuil muid ag lorg faoi láthair ag. Mar sin, nuair a thosaíonn muid, beidh min nialas agus beidh uas bheidh an t-innéacs is mó ar an eagar. Mar againn caol an chuardaigh síos, beidh muid thabhairt cothrom le dáta min agus uas a bheith go díreach ar an réimse go bhfuil muid ag lorg fós ag isteach 

A ligean ar skip to an chuid suimiúil ar dtús. Is é an chéad rud a dhéanann muid ag teacht ar an lárphointe, an t-innéacs go bhfuil leath bealaigh idir an min agus uas ar an réimse go bhfuil muid ag smaoineamh go fóill. Ansin muid ag breathnú ar luach an eagar ag an suíomh lárphointe agus a fheiceáil má tá an uimhir go bhfuil muid ag lorg ar feadh níos lú ná an eochair. Má tá an líon ag an suíomh níos lú, ansin ciallaíonn sé go bhfuil an eochair níos mó ná na huimhreacha ar an taobh clé an phoist sin. Mar sin, is féidir linn a glaoch fheidhm cuardaigh dénártha arís, ach an uair seo cothrom le dáta an min agus paraiméadair max a léamh ach an leath is é sin níos mó ná nó cothrom le luach fhéach muid díreach ar. Ar an láimh eile, má tá an eochair níos lú ná an uimhir ag an lárphointe reatha an eagar, ba mhaith linn dul ar chlé agus na huimhreacha go bhfuil níos mó neamhaird a dhéanamh. Arís, tugaimid cuardaigh dhénártha ach an uair seo leis an réimse de min agus uas Nuashonraithe a chur san áireamh ach an leath níos ísle. Má tá an luach ag an lárphointe reatha sa réimse nach níos mó ná ná níos lú ná an eochair, ansin caithfidh sé a bheith comhionann leis an eochair. Dá bhrí sin, is féidir linn ar ais ach an t-innéacs lárphointe atá ann faoi láthair, agus táimid ag déanamh. Ar deireadh, tá an seic anseo le haghaidh an cás go bhfuil an líon nach bhfuil i ndáiríre i sraith de uimhreacha muid ag cuardach. Más rud é an t-innéacs is mó ar an raon go bhfuil muid ag lorg Tá riamh níos lú ná an t-íosmhéid, ciallaíonn sé sin go againn imithe i bhfad ró. Ós rud é nach raibh an uimhir sa sraith ionchur, ar ais dúinn -1 Fuarthas go raibh a chur in iúl go bhfuil aon rud. 

Féadfaidh tú faoi deara gur le haghaidh an algartam a bheith ag obair, Tá an liosta d'uimhreacha a shórtáil. I bhfocail eile, is féidir linn a fháil ach 144 ag baint úsáide as cuardaigh dénártha má chomhlíontar na huimhreacha ordú ó ísle is airde. Más rud é nach raibh seo an cás, ní bheadh ​​muid in ann a eisiamh leath de na huimhreacha ag gach céim. Mar sin, ní mór dúinn 2 rogha. Amháin nó is féidir linn a ghlacadh liosta neamhshórtáilte agus é a shórtáil roimh úsáid a bhaint as cuardaigh dhénártha, nó is féidir linn a dhéanamh cinnte go bhfuil an liosta d'uimhreacha curtha in eagar agus muid ag uimhreacha a chur air. Dá bhrí sin, in ionad a shórtáil ach nuair atá againn chun cuardach a dhéanamh, cén fáth nach a choinneáil ar an liosta a shórtáil i gcónaí? 

Bhealach amháin a choimeád liosta d'uimhreacha curtha in eagar a ligean ag an am céanna amháin a chur leis nó bogadh uimhreacha ón liosta seo Is trí úsáid a bhaint as rud ar a dtugtar crann cuardaigh dénártha. Is éard is crann cuardaigh dénártha struchtúr sonraí go bhfuil 3 airíonna. Gcéad dul síos, tá subtree chlé ar aon nód luachanna amháin go bhfuil níos lú ná nó is comhionann leis an nód luach. Dara, tá subtree ceart nód amháin luachanna atá níos mó ná nó is comhionann leis an nód luach. Agus, ar deireadh, idir na subtrees chlé agus ar dheis gach nód Tá crainn cuardaigh dénártha. Ligean ar breathnú ar shampla leis an líon céanna a úsáid againn níos luaithe. Mar sin de tú riamh a bhfuil le feiceáil crann eolaíocht ríomhaireachta roimh, in iúl dom tosú ag rá leat go bhfuil a fhásann crann eolaíocht ríomhaireachta síos. Sea, murab ionann agus crainn tú i dtaithí ar, Is é an fhréamh an chrainn eolaíocht ríomhaireachta ag an mbarr, agus tá na duilleoga ag bun an leathanaigh. Tá gach bosca beag ar a dtugtar nód, agus na nóid ceangailte le chéile, trí imill. Dá bhrí sin tá an fhréamh an crann luach nód le luach 13, a bhfuil 2 nóid leanaí leis na luachanna 5 agus 34. Tá subtree an crann go bhfuil déanta ach ag féachaint ar fho-alt de na crainn ar fad. 

Mar shampla, is é an subtree clé den 3 nód an crann cruthaithe ag an nóid 0, 1, agus 2. Mar sin, má théann muid ar ais go dtí na hairíonna de crann cuardaigh dénártha, feicimid go gcloíonn gach nód i an chrainn go dtí na 3 maoin, is é sin, an subtree chlé bhfuil ach na luachanna atá níos lú ná nó cothrom leis an nód ar luach; an subtree ceart gach nód ach tá na luachanna atá níos mó ná nó cothrom leis an nód luach; agus Tá subtrees araon chlé agus ar dheis gach nód freisin crainn cuardaigh dénártha. Cé go Breathnaíonn an crann éagsúla, tá sé seo le crann cuardaigh bailí dhénártha an tsraith chéanna uimhreacha. Mar ábhar na fírinne, tá bealaí is féidir go leor gur féidir leat a chruthú crann cuardaigh bailí dhénártha ó na huimhreacha seo. Bhuel, a ligean ar dul ar ais chuig an chéad cheann cruthaithe againn. Mar sin, cad is féidir linn a dhéanamh leis na crainn? Bhuel, is féidir linn an-simplí a fháil ar na luachanna íosta agus uasta. Is féidir na luachanna íosta a fháil ag dul i gcónaí ar an taobh clé go dtí go bhfuil nóid níos mó chun cuairt a thabhairt. Os a choinne sin, chun teacht ar an gceann is mó a théann ach amháin síos go dtí an ceart ag gach uair. 

Ag Lorg aon uimhir eile nach bhfuil an t-íosmhéid nó an uasmhéid Is é díreach chomh furasta. Abair táimid ag lorg an uimhir 89. Táimid ag seiceáil ach an luach gach nód agus téigh go dtí an taobh clé nó ceart, ag brath ar cibé an bhfuil an nód ar luach níos lú ná nó níos mó ná an ceann táimid ag lorg. Mar sin, ag tosú ar an fhréamh 13, linn a fheiceáil go bhfuil 89 níos mó, agus mar sin táimid ag dul go dtí an ceart. Ansin linn a fheiceáil an nód le haghaidh 34, agus arís muid ag dul go dtí an ceart. 89 tá sé fós níos mó ná 55, mar sin againn leanúint ag dul go dtí an ceart. Táimid ag teacht ansin suas le nód le luach 144 agus téigh go dtí an taobh clé. Lo agus behold, 89 tá ceart ann. 

Tá rud eile gur féidir linn a dhéanamh phriontáil amach na huimhreacha ag comhlíonadh an traversal inorder. An traversal inorder ciallaíonn rud a phriontáil amach sa subtree chlé le leanúint ag priontáil an nód féin agus leanúint ansin le priontáil gach rud amach sa subtree ceart. Mar shampla, a ligean ar chur ar ár crann cuardaigh is fearr leat dhénártha agus a phriontáil amach na huimhreacha in ord sórtáilte. Tús a chur againn ar an fhréamh 13, ach roimh priontáil 13 ní mór dúinn a phriontáil amach gach rud sa subtree chlé. Mar sin, táimid ag dul go dtí 5. Tá fós ag dul níos doimhne síos sa crann go dtí go bhfaighidh muid an nód clé an chuid is mó, atá nialas. Tar éis an priontáil náid, théann muid ar ais suas go dtí an 1 agus a phriontáil sin amach. Ansin againn dul go dtí an subtree ceart, a bhfuil 2, agus go amach a phriontáil. Anois go bhfuil muid ag déanamh leis an subtree, is féidir linn dul ar ais suas go dtí an 3 agus í a phriontáil amach. Leanúint ar ais ar bun, a phriontáil againn ar an 5 agus ansin an 8. Anois go bhfuil muid i gcrích an iomlán d'fhág subtree, is féidir linn a phriontáil amach 13 agus tosú ag obair ar an subtree ceart. Hap againn síos go dtí 34, ach roimh priontáil 34 ní mór dúinn a phriontáil amach a subtree chlé. Mar sin, linn a phriontáil amach 21; ansin a fháil againn a phriontáil amach 34 agus a subtree cheart cuairt a thabhairt. Ós rud é go bhfuil 55 aon subtree chlé, ní mór dúinn é a phriontáil amach agus a lean ar aghaidh go dtí a subtree ceart. 144 Tá subtree chlé, agus mar sin linn a phriontáil amach an 89, le leanúint ag an 144, agus ar deireadh an nód ceart-chuid is mó de 233. Tá tú é; na huimhreacha go léir i gcló amach in ord ó ísle is airde. 

Nuair a chuirfear rud éigin chun an crann is réasúnta painless chomh maith. Gach ní mór dúinn a dhéanamh ná a chinntiú go leanaimid 3 airíonna dhénártha crann cuardaigh agus cuir isteach ansin an luacha sa chás go bhfuil spás. Ligean le rá ba mhaith linn a chur isteach ar an luach de 7. Ós rud é go 7 níos lú ná 13, ní mór dúinn dul go dtí an taobh clé. Ach tá sé níos mó ná 5, mar sin againn trasna na láimhe deise. Ós rud é go bhfuil sé níos lú ná mar atá 8 agus 8 nód duille, cuir muid 7 leis an leanbh taobh clé de 8. Voila! Táimid tar éis Chuir roinnt dár crann cuardaigh dénártha. 

Más féidir linn rudaí a chur, ní mór dúinn a bheith níos fearr in ann rudaí a scriosadh chomh maith. Ar an drochuair dúinn, is é a scriosadh le beagán níos casta - nach bhfuil i bhfad, ach amháin le beagán. Tá 3 cásanna difriúla atá againn a mheas nuair eilimintí scriosadh ó chrainn cuardaigh dénártha. An chéad, is é an cás éasca go bhfuil gné nód duille. Sa chás seo, táimid ag scriosadh ach é agus dul ar aghaidh leis an ár ngnó. Abair ba mhaith linn a scriosadh le linn na 7 gur chuir muid díreach. Bhuel, linn a fháil ach é, é a bhaint di, agus go bhfuil sé. Is é an chéad chás eile má tá an nód ach 1 leanbh ann. Anseo, is féidir linn a scriosadh an nód, ach ní mór dúinn an chéad a dhéanamh cinnte go a cheangal ar an subtree go bhfuil fágtha anois parentless le tuismitheoir an nód a scriosadh againn ach. Abair ba mhaith linn a scriosadh 3 as ár crann. Glacann muid an eilimint leanbh an nód agus é ag gabháil leis an tuismitheoir an nód. Sa chás seo, tá muid ag gabháil anois 1 a ghabhann 5. Oibríonn sé seo gan fadhb mar a fhios againn, de réir an dénártha maoine cuardaigh crann, go raibh gach rud sa subtree na láimhe clé den 3 níos lú ná 5. Anois go bhfuil 3 ar subtree a glacadh de chúram, is féidir linn a scriosadh é. Is é an tríú cás agus deiridh na cinn is casta. Is é seo an cás nuair a bhíonn an nód ba mhaith linn a scriosadh 2 leanbh. D'fhonn é seo a dhéanamh, ní mór dúinn an chéad a fháil ar an nód go bhfuil an luach is mó, babhtála an dá, agus ansin an nód atá i gceist a scriosadh. Fógra an nód go bhfuil nach féidir an luach eile is mó a bheith 2 leanbh féin ós rud é go mbeadh ar a leanbh chlé iarrthóir níos fearr do na is mó atá romhainn. Dá bhrí sin, méideanna a scriosadh nód le 2 leanbh a swapping de 2 nóid, agus ansin a scriosadh láimhseáil ag 1 de 2 rialacha thuasluaite. Mar shampla, a rá a ligean ar mhaith linn a scriosadh an nód fréimhe, 13. Is é an chéad rud a dhéanann muid linn teacht ar an luach eile is mó sa crann atá, sa chás seo, is é 21. Táimid ag babhtála ansin an 2 nóid, a dhéanamh 13 le duille agus 21 an nód ghrúpa lárnach. Anois is féidir linn a scriosadh ach 13. 

Mar a léiríodh níos luaithe, tá bealaí is féidir go leor a dhéanamh crann cuardaigh bailí dénártha. Ar an drochuair dúinn, tá roinnt níos measa ná a chéile. Mar shampla, cad a tharlaíonn nuair a thógáil againn crann cuardaigh dénártha ó liosta sórtáilte, uimhreacha? Na huimhreacha a leanas ach an ceart ag gach céim. Nuair a ba mhaith linn a chuardach le haghaidh roinnt, ní mór dúinn aon rogha ach amháin chun breathnú ar an ceart ag gach céim. Ní hé seo níos fearr ná cuardach líneach ar chor ar bith. Cé nach mbeidh muid iad a chlúdach anseo, tá eile, níos casta, struchtúir sonraí a chinntiú nach dtarlaíonn sé seo. Mar sin féin, tá rud amháin simplí féidir a dhéanamh chun seo a sheachaint go dtí díreach Suaitheadh ​​randamach na luachanna ionchuir. Tá sé an-dócha go bhfuil de sheans randamach liosta shuffled de uimhreacha curtha in eagar. Má bhí seo an cás, ní bheadh ​​casinos fanacht sa ghnó le fada. 

Tá tú é. Tá a fhios agat anois faoi chuardach dhénártha agus crainn cuardaigh dénártha. Tá mé Patrick Schmid, agus tá sé seo CS50. [CS50.TV] Slí amháin soiléir a bheith a scanadh ar an liosta ó ... [bíp] ... Líon na míreanna ... yep [Gáirí] ... Post nód de 234 ... augh. >> Yay! Go raibh -