[MIZIK jwe] Doug Lloyd: Se konsa, nou ve yo te inching pi pre ak pi pre ki grail apa pou Bondye nan done estrikti, youn ke nou ka insert an, efase soti nan, epi gade moute nan tan konstan. Dwa. Sa a sòt de objektif la. Nou vle pou kapab fè bagay trè, trè byen vit. 

Fè nou jwenn li isit la lè nou ap pale de ap eseye? Oke, kite la pran yon gade. Se konsa, nou te wè plizyè estrikti done diferan ki okipe kat la sa yo rele pè kle-valè, gewografik kèk moso nan done nan kèk lòt moso nan done konsa nou konnen ki kote yo jwenn enfòmasyon ki nan estrikti an. 

Se konsa, pou etalaj, pou egzanp, nan kle a se endèks la eleman oswa etalaj kote 0 oswa etalaj 1 ak sou sa. Ak valè a se done yo ki egziste nan moman sa kote. Se konsa, sa se ki estoke nan etalaj 0? Ki sa ki se ki estoke nan etalaj 1 kont jis 0 ak 1, ki ta dwe kle yo. 

Avèk yon tab regle li a sòt de lide a menm. Avèk yon tab regle, nou gen sa a hash fonksyon ki jenere kòd regle. Se konsa, kle a se kòd la regle nan done yo. Ak valè a, patikilyèman nou te pale de Anchènman nan videyo a sou tab regle, se ke lis lye nan done ki achaj ak sa yo ki hashcode. Dwa. Ki sa ki sou yon lòt apwòch metòd sa a, menm si? Ki sa ki sou yon metòd kote a kle se garanti yo dwe inik, kontrèman ak yon tab regle, kote nou te kapab fini ak de moso nan done gen menm hashcode la. Lè sa a, nou gen fè fas ak ki swa pa sonde oswa plis de preferans Anchènman ranje ki pwoblèm. 

Se konsa, kounye a nou ka garanti ke kle nou yo pral inik. Ak sa ki si valè nou an te jis yon bagay tankou fasil kòm vre ak fo ki di nou si wi ou non oswa ou pa ki moso nan enfòmasyon egziste nan estrikti a? Yon Boolean ta ka kòm senp tankou yon ti jan. Pli reyèlman li la pwobableman yon multiple plis chans pase yon ti jan. Men, sa a yon anpil pi piti pase estoke petèt yon fisèl 50-karaktè, pa egzanp. 

Se konsa, ap eseye, menm jan ak Hash tab, ki konbine ranje ak lis lye, ap eseye konbine ranje, estrikti, ak endikasyon ansanm nan magazen done nan yon fason ki enteresan sa a, se bèl diferan de anyen nou te wè byen lwen tèlman. Koulye a, nou sèvi ak done yo kòm yon plan navige sa a estrikti done. Men, si nou ka swiv plan an, si nou kapab swiv done ki nan kòmanse nan fen, nou pral konnen si ke done egziste nan trye la. 

Men, si nou pa ka swiv kat jeyografik la soti nan sa vle di nan fen nan tout, done yo pa ka egziste. Yon fwa ankò, kle yo isit la yo se garanti yo dwe inik. Se konsa, kontrèman ak yon tab regle, nou pral pa janm gen fè fas ak kolizyon isit la. E pa gen de moso nan done gen ekzakteman menm bagay la plan sof si ke done se ki idantik. 

Si nou Insert Jan, Lè sa a, nou rechèch pou Jan. Sa a de moso ki idantik nan done, dwa, nou ap chèche a. Men, otreman, nenpòt de moso nan telefòn nan garanti yo gen kat woutyè inik nan sa a estrikti done. Epi nou ap ale nan pran yon gade nan yon vizyèl nan sa a nan jis yon moman. 

Nou pral fè sa a pa ap eseye kreye yon nouvo estrikti done, gewografik valè kle pè sa yo. Nan ka sa a, nou pa ap ale nan sèvi ak yon bagay kòm senp tankou yon Boolean. Nou aktyèlman pral estoke fisèl la. Epi sa fisèl ki pral gen non an nan yon inivèsite. 

Apre sa, kle a a pwal ane a lè yo te ki inivèsite te fonde. Tout ane pou inivèsite yo pral yo dwe kat chif. Se konsa, nou pral sèvi ak moun kat chif navige nan estrikti sa a done. Epitou, n ap wè, ankò, ki jan nou fè sa nan jis yon dezyèm fwa. 

Nan fen chemen an, nou pral wè non an nan inivèsite a ki koresponn ak sa yo ki kle, sa yo ki kat chif. Lide a debaz dèyè yon trye se nou gen yon wout santral la. Se konsa, panse sou li tankou yon pyebwa. Lè sa a se menm jan an nan òtograf ak nan konsèp nan yon pye bwa. Anjeneral lè nou panse osijè de pye bwa nan mond reyèl la, yo gen yon rasin sa a, se nan la tè ak yo grandi anwo epi yo gen branch epi yo gen fèy bwa. Ak fondamantalman lide a nan yon trye se egzakteman menm bagay la, eksepte se ke rasin mare yon kote nan syèl la. Ak fèy yo se nan pati anba nan. 

Se konsa, li kalite tankou pran yon pye bwa ak jis ranvèrsan l 'bouch anba. Men, gen toujou branch yo. Ak moun ki ta dwe opsyon nou an, moun yo pral koneksyon nou an soti nan rasin nan fèy yo. Nan ka sa a, sa yo ki chemen, moun branch yo ki make ak chif ki di nou ki fason yo ale soti nan kote nou ye. 

Si nou wè yon 0, n 'al jwenn desann branch sa a, si nou wè yon 1, n 'al jwenn desann branch sa a, e konsa ak sou sa. Oke, ki sa sa a vle di? Oke, ki vle di ke nan chak pwen junction ak tout ne nan la mwayen ak tout branch, gen 10 posib kote ke nou ka ale. Se konsa, gen 10 endikasyon soti nan tout kote. 

Lè sa a se kote ap eseye ka jwenn yon ti jan entimidasyon pou yon moun ki moun ki nan pa gen yon anpil nan eksperyans nan syans òdinatè anvan. Men, ap eseye yo se reyèlman bèl pè. Men, si ou gen nan chans travay avèk yo epi w ap vle fouye-an ak eksperyans ak yo, yo ap reyèlman trè enteresan estrikti done nan travay avèk yo. Si nou vle insert yon eleman nan trye a, tout sa nou bezwen fè se bati chemen ki kòrèk la soti nan rasin nan fèy la. Men sa chak etap ansanm wout la ta ka sanble. Nou pral defini yon done nouvo estrikti pou yon nouvo ne rele yon trye. 

Apre sa, andedan nan ke done estrikti ki te gen de moso. Nou pral nan magazen an non nan yon inivèsite. Epi nou ap ale nan magazen yon etalaj de pwent nan lòt nœuds nan kalite la menm. Se konsa, ankò, sa a se ki sòt nan konsèp nan tout kote nou yo, nou nan 10 posib kote nou ka ale. Si nou wè yon 0, n 'al jwenn desann branch sa a. Si nou wè yon 1, branch sa a, ak sou sa ak sou sa ak sou sa. Si nou di 9, n 'al jwenn desann branch sa a. Se konsa, nan chak pwen junction, nou ka ale 10 kote posib. Se konsa, chak ne gen a ki genyen 10 endikasyon nan lòt nœuds, nan 10 lòt nœuds. 

Apre sa, done yo nou ap estoke se jis non an nan inivèsite a. Se konsa nou bati yon trye. Se pou yo insert yon koup nan atik nan trye nou an. Se konsa, nan tèt la anpil, sa a se ne rasin nou an. Sa a se pwobableman pral yo dwe yon bagay w ap ale nan globalman deklare. Apre sa, w ap ale nan kenbe globalman yon konsèy sa a ne toujou. 

W ap ale nan di, rasin egal, epi w ap ale nan malok tèt ou trye ne. Epi ou pa janm ap ale manyen rasin ankò. Chak fwa ou vle kòmanse navige nan, ou mete yon lòt konsèy egal a rasin, tankou Trav, ki se egzanp I itilize nan anpil nan videyo mwen an isit la sou pil ak ke moun kap kriye e li bay lis lyen ak sou sa. 

Ou mete yon lòt konsèy rele Trav pou parcourt. Apre sa, ou itilize Trav navige a estrikti nan done. Se konsa, kite a wè ki jan sa a ta ka gade. Se konsa, kounye a, ki sa yon ne sanble? Oke, menm jan done nou an estrikti deklarasyon endike, nou gen yon fisèl, ki nan ka sa a se vid. Pa gen anyen isit la. 

Apre sa, yon etalaj de 10 endikasyon. E yo gen dwa kounye a, nou sèlman gen 1 ne nan trye sa a. Pa gen anyen lòt bagay nan li. Se konsa, tout 10 nan tout sa yo endikasyon pwen A ak nil. Sa a ki sa wouj la endike. 

Se pou nou Insert fisèl la Harvard. Se pou nou Insert University of Harvard nan trye sa a, ki te fonde nan ane a 1636. Nou vle yo sèvi ak kle a, 1636, fè nou konnen ki kote nou ap ale nan magazen an Harvard trye la. Koulye a, ki jan ta ka nou fè sa? 

Li ta ka sanble yon bagay tankou sa a. Nou kòmanse nan rasin lan. Epi nou gen sa yo 10 kote nou ka ale. Rasin an se jis tankou nenpòt ki lòt ne nan trye la. Gen 10 kote nou ka ale soti isit la. 

Ki kote èske nou pwobableman vle yo ale si kle a se 1636? Genyen vrèman de opsyon. Dwa. Nou ka bati kle a soti nan dwa kite ak kòmanse ak 6. Oubyen èske nou ta ka bati kle a soti nan gòch a dwat epi yo kòmanse ak 1. 

Li pwobableman plis entwisyon kòm yon moun yo konprann nou pral Jis ale gòch a dwat. Se konsa, si mwen vle insert Harvard nan trye sa a, Mwen pwobableman vle kòmanse pa kòmanse nan rasin lan, gade nan 10 opsyon mwen nan devan m ', yo t'ap di konsa Mwen vle ale desann chemen an 1. OK. 

Koulye a, 1 chemen se kounye a nil. Se konsa, si mwen vle kontinye desann sou menm chemen insert eleman sa a nan trye a, Mwen gen yo malok yon nouvo ne, gen 1 pwen a, ak Lè sa a mwen se bon yo ale. 

Se konsa, mwen menm ki fondamantalman nan yon pwen kote mwen kanpe nan rasin lan nan pye bwa a oswa nan trye e gen 10 branch yo. Men, chak branch gen yon pòtay lavil la devan li. Dwa. Paske gen nan pa gen anyen lòt gen nan. Pa gen pasaj ki an sekirite. Sa vle di ke pa gen anyen desann nenpòt nan moun sa branch yo. Si m 'vle kòmanse bilding yon bagay, mwen vle yo retire pòtay lavil la. Mwen vle retire pòtay lavil la nan devan nimewo 1. Apre sa, mwen vle mache desann sa. Apre sa, mwen vle bati yon lòt kote pou m 'yo ale. 

Epi sa a, sa m 'te fè isit la. Se konsa, 1 pa gen okenn ankò lonje dwèt nan nil. Mwen te di li nan san danje yo ale desann isit la kounye a. Mwen bati yon lòt ne. Lè m 'jwenn ak sa yo ki ne, mwen gen yon lòt desizyon fè. Ki kote mwen pral ale soti isit la? 

Oke, mwen te deja ale desann 1 an. Se konsa, koulye a, mwen pwobableman vle desann ale 6 la. Dwa. Yon fwa ankò, mwen gen 10 kote mwen kapab chwazi. Se konsa, kite a kounye a desann nimewo 6. Se konsa, mwen klè pòtay lavil la nan devan nimewo 6. Apre sa, mwen mache desann la. Apre sa, mwen bati yon lòt ne. Apre sa, mwen te rive nan yon lòt pwen junction. 

Yon fwa ankò, mwen gen 10 chwa pou ki kote mwen ka ale. Mwen te te deplase soti nan 1 rive nan 6. Se konsa, koulye a, mwen pwobableman vle pou yo ale nan 3. 3, gen nan okenn kote mwen ka ale. Se konsa, mwen gen klè wout la ak bati tèt mwen yon espas nouvo. Lè sa a, soti nan 3, kote pou m vle ale? Mwen vle ale desann 6. 

Epi, ankò, mwen te gen klè wout la fè li. Se konsa, kounye mwen te itilize kle mwen an Insert kreye nœuds epi yo kòmanse bati trye sa a. Mwen te te kòmanse nan rasin lan. Mwen te ale desann 1636. Epi, koulye a mwen se nan pati anba a gen sou sa ne. Epi ou ka kapab wè l 'sou ekran an. 

Li nan make nan jòn. Sa a kote mwen kounye a ye vre. Se kle mwen fè. Mwen te fin itilize chak pozisyon nan kle m 'yo. Se konsa, mwen pa ka ale nenpòt ki pi lwen. Se konsa, nan pwen sa a, tout mwen reyèlman bezwen fè se di, OK. Li nan kalite renmen kap desann nan tè a, si w ap vizyon tèt ou kòm sa a sòt de chemen ak koneksyon diferan. Sòt de kap desann ak sòt de espre pentire Harvard sou tè a. Sa a non an nan sa a. Konnen sa a, se sa ki nan nan kote sa a. Si nou kòmanse nan rasin lan e nou desann 1 ak Lè sa a 6 ak Lè sa a 3 ak Lè sa a, 6, kote nou ye? Oke si nou gade desann epi nou wè Harvard, lè sa a nou konnen ke Harvard te te fonde an 1636 ki baze sou wout la nou ap mete ann aplikasyon sa a estrikti done. Se konsa, sa ki te èspere ke senp. Nou ap pral fè de plis parusyon. Ak èspere ke li pral ede yo wè sa a fè de fwa plis. 

Koulye a, kite a Insert yon lòt inivèsite. Se pou nou Insert Yale nan trye sa a. Yale te fonde an 1701. Se konsa, nou pral kòmanse nan la rasin, menm jan nou toujou fè. Epi nou mete yon konsèy parcourt. Nou pral sèvi ak sa pou avanse pou pi nan. Premye bagay nou vle fè se ale desann chemen an 1. Sa a chif nan premye nan kle nou an. Erezman, menm si, nou pa fè sa dwe fè nenpòt ki travay tan sa a. Chemen an te 1 deja te otorize. Mwen otorize li deja lè mwen te mete Harvard nan 1636. Se konsa, mwen ka san danje deplase desann 1 ak jis ale la. Si ka deplase desann 1 an. 

Koulye a, menm si, mwen vle pou yo ale nan 7. Mwen otorize fason a nan 6. Mwen konnen mwen kapab san danje kontinye desann chemen an 6. Men, mwen bezwen kontinye sou chemen an 7. Se konsa, sa mwen bezwen fè? Oke, jis tankou anvan, mwen jis bezwen klè pòtay lavil la, jwenn soti nan wout la, ak bati yon nouvo ne soti nan chemen an 7. Jis tankou sa a. 

Se konsa, koulye a, mwen te deplase 1 ak Lè sa a 7. Epi, koulye a remake, mwen se sòt a sou nouvo subbranch sa a. Dwa. Tout lòt bagay soti nan 16 sou li a, Mwen pa pran swen sou yo. Mwen pa fè 16 anyen. M ap fè 17 bagay. 

Se konsa, kounye soti nan 17 sou li a, mwen gen yo sòt de flanm santye nouvo isit la. Pwochen chif kle a mwen an se 0. Mwen byen klè pa ka jwenn nenpòt kote. Mwen jis bati ne sa a. Se konsa, mwen konnen gen nan pa gen chemen pou pi devan soti isit la. Se konsa, mwen gen fè yon sèl tèt mwen. 

Se konsa, mwen malok yon nouvo ne epi yo gen 0 pwen la. Lè sa a, yon lòt fwa ankò, mwen malok yon nouvo ne epi yo gen yon pwen la. Yon fwa ankò, mwen te fin itilize kle mwen, 1701. Se konsa, mwen gade desann ak mwen espre penti Yale. Sa a non an nan ne sa a. 

Se konsa, kounye a si mwen janm bezwen wè si Yale se nan trye sa a, mwen kòmanse nan rasin lan, M 'desann 1701, epi gade desann. Men, si mwen wè Yale espre pentire sou tè a, lè sa a Mwen konnen Yale egziste nan trye sa a. Se pou yo fè yon sèl plis. Se pou nou Insert Dartmouth nan sa a trye, ki te fonde nan 1769. 

Kòmanse nan rasin lan ankò. Chif premye fwa mwen nan kle mwen an se 1. Mwen ka san danje deplase desann ki chemen. Ki deja egziste. Chif nan pwochen nan kle mwen an se 7. Mwen ka san danje deplase desann ki chemen. Li egziste kòm byen. 

Pwochen mwen se 6. Soti isit la, ki soti nan kote mwen kounye a menm ki nan jòn gen la nan ki ne presegondè, 6 se kounye a fèmen nan. Si m 'vle ale desann sou menm chemen, Mwen gen yo bati l 'tèt mwen. Se konsa, mwen pral malok yon nouvo ne epi yo gen 6 pwen a. Lè sa a,, ankò, mwen se tou limen an santye nouvo isit la. 

Se konsa, mwen malok yon nouvo ne Se konsa, depi ke nimewo chemen node-- 9-- Lè sa a, kounye a ak si mwen vwayaje 1769, e mwen gade desann. Pa gen anyen kounye a espre pentire a. Mwen ka ekri Dartmouth. Apre sa, mwen te antre DARTMOUTH nan trye la. 

Se konsa, sa a, se mete bagay sa yo nan trye la. Koulye a, nou vle pou fè rechèch pou bagay sa yo. Ki jan nou fè rechèch pou bagay sa yo nan trye a? Oke, li nan bèl anpil lide nan menm. Koulye a, nou jis itilize chif yo nan kle a yo wè si nou ka navige soti nan rasin lan nan kote nou vle ale nan trye la. 

Si nou frape yon fen mouri nan nenpòt ki pwen, lè sa a nou konnen ke ki eleman pa ka egziste oswa lòt moun ke chemen ta te deja te otorize. Si nou fè l 'tout wout la nan fen a, tout sa nou bezwen fè se gade desann ak wè si sa a, se eleman nan nou ap chèche pou. Si li se, siksè. Si li nan pa, febli. 

Se konsa nou fè rechèch pou Harvard nan trye sa a. Nou kòmanse nan rasin lan. Epi, ankò, nou ap ale nan kreye yon konsèy parcourt fè mouvman nou an pou nou. Soti nan rasin lan nou konnen ke nan premye plas nou bezwen ale se 1, nou ka fè sa? Wi, nou kapab. Si san danje egziste. Nou ka ale la. 

Koulye a, plas la pwochen nou bezwen ale se 6. Chemen an 6 egziste soti isit la? Yeah, li fè sa. Nou ka ale desann chemen an 6. Apre sa, nou fini isit la. 

Èske nou ka ale desann chemen an 3 soti isit la? Bon, kòm li vire soti, repons lan se wi, ki egziste tou. Epi yo ka nou jwenn sou wout la 6 soti isit la? Wi, nou kapab. 

Nou pa t 'byen reponn kesyon an ankò. Genyen toujou yon sèl plis etap, ki se kounye a nou bezwen gade desann ak wè si sa a, se aktyèlman si nou ap chèche pou Harvard, se ke ki sa nou jwenn apre nou itilize kle a? Nan egzanp lan nou ap lè l sèvi avèk isit la, ane yo yo toujou kat chif. Men, ou ta ka lè l sèvi avèk egzanp lan kote w ap estoke yon diksyonè nan mo yo. 

Se konsa, olye pou yo gen 10 endikasyon ki kote mwen, ou ta ka genyen 26. Yonn pou chak lèt ​​nan alfabè a. Apre sa, yo se kèk mo tankou baton, ki se yon sou nan pakèt, pou egzanp. Se konsa, menm si ou jwenn yo nan nan fen kle a epi ou gade l 'atè, ou pa ta ka wè sa ki w ap chèche pou. 

Se konsa, ou toujou gen Traverse chemen an tout antye ak Lè sa a si ou te avèk siksè kapab Traverse chemen an antye, gade desann ak fè yon sèl konfimasyon final la. Eske se sa ke sa m ap chèche pou? Bon, mwen gade desann apre yo fin kòmanse nan tèt la ak ale 1636. Mwen gade desann. Mwen wè Harvard. Se konsa, repons lan se wi, mwen nan plas. E si sa m ap chèche pou se pa nan trye a, menm si. E si M 'ap chache Princeton, ki te fonde nan 1746. Se konsa, 1746 vin kle mwen navige nan trye la. Bon, mwen kòmanse nan rasin lan. Apre sa, plas an premye Mwen vle ale desann chemen an 1. Èske mwen ka fè li? Wi, mwen kapab. 

Èske mwen ka ale desann chemen an 7 soti nan la? Yeah, mwen kapab. Ki egziste tou. Men, ka m 'desann 4 chemen an soti isit la? Sa a tankou mande kesyon an, kapab Mwen kontinye desann sou menm ti kras kare ke mwen te make nan jòn? Pa gen anyen la. Dwa. 

Gen nan pa gen fason pou pi devan desann chemen an 4. Si Princeton te nan trye sa a, ki 4 ta yo te otorize pou nou deja. Se konsa, nan pwen sa a nou te rive jwenn yon fen mouri. Nou pa ka ale nenpòt ki pi lwen. Se konsa, nou ka di, définitivement, pa gen. Princeton pa egziste nan trye sa a. 

Se konsa, sa sa a tout vle di? Dwa. Genyen yon anpil ale sou isit la. Genyen endikasyon sou tout plas la. Epi, menm jan ou ka wè jis nan dyagram lan, gen nan yon anpil nan nœuds ki yo kalite vole alantou. Men, remake chak fwa nou te vle si wi ou non yon bagay te tcheke nan trye a, nou sèlman te fè 4 se. 

Chak fwa nou te vle Insert yon bagay nan trye a, nou gen fè 4 deplase, petèt mallocing kèk bagay sou wout la. Men, jan nou te wè lè nou antre DARTMOUTH nan trye a, pafwa kèk nan chemen an ta ka deja rete kò mounn pou nou. Se konsa, kòm trye nou an ap vin pi gwo ak pi gwo, nou gen fè mwens travay chak fwa insert nouvo bagay paske nou te deja bati yon anpil nan entèmedyè a branch sou wout la. Si nou sèlman janm genyen fè yon gade nan 4 bagay sa yo, 4 se jis yon konstan. Nou vrèman yo kalite apwoche konstan ensèsyon tan ak konstan Passage tan. Arbitraj la, nan kou, ke yo te ke trye sa a, kòm ou ka pwobableman di, se gwo. Chak youn nan sa yo nœuds pran moute yon anpil nan espas. 

Men, sa a arbitraj la. Si nou vle reyèlman rapid ensèsyon, sipresyon reyèlman rapid, ak Passage reyèlman rapid, nou dwe gen yon anpil nan done vole alantou. Nou dwe mete sou kote yon anpil nan espas ak memwa pou sa estrikti done egziste. 

Se konsa, sa a, se arbitraj la. Men, li sanble tankou nou ta ka yo jwenn li. Nou ka yo te jwenn ke grail apa pou Bondye nan estrikti done ak ensèsyon rapid, sipresyon, ak Passage. E petèt sa a pral yon estrikti done ki apwopriye yo sèvi ak pou kèlkeswa enfòmasyon nou ap eseye magazen. Mwen se Doug Lloyd, sa a se CS50.