1 00:00:00,000 --> 00:00:02,994 >> [Ag seinm ceoil] 2 00:00:02,994 --> 00:00:05,426 3 00:00:05,426 --> 00:00:08,550 DOUG LLOYD: Mar sin, tá muid ag inching níos gaire agus níos dlúithe go iomaíocht don duais mhór de shonraí 4 00:00:08,550 --> 00:00:13,050 struchtúir, ceann gur féidir linn a chur isteach isteach, scriosadh as, agus breathnú suas 5 00:00:13,050 --> 00:00:15,440 in am tairiseach. 6 00:00:15,440 --> 00:00:16,270 Ceart. 7 00:00:16,270 --> 00:00:17,280 Sin saghas an sprioc. 8 00:00:17,280 --> 00:00:19,720 Is mian linn a bheith in ann a dhéanamh rudaí an-, go han-tapa. 9 00:00:19,720 --> 00:00:22,580 >> An bhfuil fuair muid anseo nuair muid ag caint faoi iarracht? 10 00:00:22,580 --> 00:00:23,670 Bhuel, a ligean ar ghlacadh le breathnú. 11 00:00:23,670 --> 00:00:25,628 Mar sin, againn le feiceáil roinnt struchtúir éagsúla sonraí 12 00:00:25,628 --> 00:00:28,680 a láimhseáil an mhapáil mar a thugtar air péirí eochair-luach, 13 00:00:28,680 --> 00:00:32,080 mapáil roinnt píosa sonraí go píosa éigin eile de shonraí 14 00:00:32,080 --> 00:00:36,020 mar sin tá a fhios againn nuair a aimsiú faisnéis i struchtúr. 15 00:00:36,020 --> 00:00:40,060 >> Mar sin, le haghaidh eagar, mar shampla, an Is eochair an t-innéacs eilimint nó sraith 16 00:00:40,060 --> 00:00:42,600 suíomh 0 nó sraith 1 agus mar sin de. 17 00:00:42,600 --> 00:00:46,140 Agus is é an luach na sonraí atá ann ag an suíomh sin. 18 00:00:46,140 --> 00:00:48,550 Mar sin, cad é a stóráil i sraith 0? 19 00:00:48,550 --> 00:00:54,290 Cad atá stóráilte i sraith 1 versus díreach 0 agus 1, a bheadh ​​na heochracha. 20 00:00:54,290 --> 00:00:56,360 >> Le tábla hash tá sé saghas an smaoineamh céanna. 21 00:00:56,360 --> 00:01:00,690 Le tábla hash, ní mór dúinn an hash fheidhm a ghineann cóid hash. 22 00:01:00,690 --> 00:01:03,670 Mar sin, is é an eochair an cód hash na sonraí. 23 00:01:03,670 --> 00:01:06,530 Agus an luach, go háirithe Labhair linn faoi shlabhrú 24 00:01:06,530 --> 00:01:10,590 san fhíseán ar tháblaí hash, Is liosta sin nasctha sonraí 25 00:01:10,590 --> 00:01:12,550 go hashes leis hashcode. 26 00:01:12,550 --> 00:01:14,050 Ceart. 27 00:01:14,050 --> 00:01:16,050 Cad mar gheall ar an gcur chuige eile an modh seo, cé? 28 00:01:16,050 --> 00:01:21,000 Cad mar gheall ar mhodh i gcás an eochair ráthaithe a bheith ar leith, 29 00:01:21,000 --> 00:01:25,410 murab ionann agus tábla hash, i gcás ina d'fhéadfadh muid deireadh suas le dhá phíosa sonraí 30 00:01:25,410 --> 00:01:27,200 a bhfuil an hashcode céanna. 31 00:01:27,200 --> 00:01:30,020 Agus ansin ní mór dúinn chun déileáil leis go bhfuil ag ceachtar deacra nó níos mó 32 00:01:30,020 --> 00:01:33,340 b'fhearr shlabhrú a shocrú go fhadhb. 33 00:01:33,340 --> 00:01:37,520 >> Mar sin, anois is féidir linn a chinntiú go mbeidh ár eochair a bheith ar leith. 34 00:01:37,520 --> 00:01:39,690 Agus cad má bhí ár n-luach ach rud éigin chomh héasca 35 00:01:39,690 --> 00:01:44,080 chomh fíor nó bréagach a insíonn dúinn cé acu nó nach bhfuil píosa eolais 36 00:01:44,080 --> 00:01:45,610 ann i struchtúr? 37 00:01:45,610 --> 00:01:48,180 D'fhéadfadh Boole a bheith chomh simplí agus is le beagán. 38 00:01:48,180 --> 00:01:52,660 Go réalaíoch is dócha Beart níos dóchúla ná le beagán. 39 00:01:52,660 --> 00:01:55,410 Ach tá go bhfuil a lán níos lú ná mar a stóráil b'fhéidir teaghrán 50-charachtar, 40 00:01:55,410 --> 00:01:57,360 mar shampla. 41 00:01:57,360 --> 00:02:02,210 >> Mar sin, iarracht, cosúil le táblaí hash, a chur le chéile arrays agus liosta nasctha, 42 00:02:02,210 --> 00:02:05,790 iarracht a chur le chéile arrays, Struchtúir, agus leideanna 43 00:02:05,790 --> 00:02:08,509 le chéile chun sonraí a stóráil i ar bhealach suimiúil go bhfuil 44 00:02:08,509 --> 00:02:11,550 deas difriúil ó rud ar bith againn le feiceáil go dtí seo. 45 00:02:11,550 --> 00:02:16,750 Anois táimid ag úsáid as na sonraí mar treochlár le nascleanúint a struchtúr seo sonraí. 46 00:02:16,750 --> 00:02:18,710 Agus más féidir linn leanúint an treochlár, más féidir linn a 47 00:02:18,710 --> 00:02:22,390 lean na sonraí ó ag tosú ar deireadh, beidh muid a 48 00:02:22,390 --> 00:02:24,945 Tá a fhios an bhfuil na sonraí sin ann sa Trie. 49 00:02:24,945 --> 00:02:28,310 >> Agus más rud é nach féidir linn leanúint ar an léarscáil ó a chiallaíonn go deireadh ar chor ar bith, 50 00:02:28,310 --> 00:02:30,600 nach féidir na sonraí ann. 51 00:02:30,600 --> 00:02:32,890 Arís, is iad na heochracha anseo ráthaithe a bheith ar leith. 52 00:02:32,890 --> 00:02:36,020 Agus mar sin murab ionann agus tábla hash, ní beidh orainn ag déileáil le imbhuailtí anseo. 53 00:02:36,020 --> 00:02:39,090 Agus gan aon dhá phíosa sonraí tá díreach mar an gcéanna treochlár 54 00:02:39,090 --> 00:02:40,530 ach amháin má tá na sonraí sin comhionann. 55 00:02:40,530 --> 00:02:44,580 >> Má táimid Seán cuir isteach, ansin táimid ag cuardach do John. 56 00:02:44,580 --> 00:02:47,430 Sin dhá phíosa comhionann de sonraí, ceart, tá muid ag lorg trí. 57 00:02:47,430 --> 00:02:49,880 Ach a mhalairt, aon Tá dhá phíosa sonraí 58 00:02:49,880 --> 00:02:52,750 ráthaithe a bheith acu treochláir uathúil trí struchtúr seo sonraí. 59 00:02:52,750 --> 00:02:56,210 Agus táimid ag dul a chur le breathnú ar a amhairc an i nóiméad ach. 60 00:02:56,210 --> 00:02:58,810 >> Beidh muid é seo a dhéanamh trí iarraidh a struchtúr sonraí nua a chruthú, 61 00:02:58,810 --> 00:03:00,564 mapáil an eochair péirí luach leanas. 62 00:03:00,564 --> 00:03:03,480 Sa chás seo, ní táimid ag dul a úsáid rud chomh simplí mar Boole. 63 00:03:03,480 --> 00:03:06,200 Beidh muid a stóráil i ndáiríre an teaghrán. 64 00:03:06,200 --> 00:03:08,690 Agus is é sin teaghrán ag dul go dtí bheith ar an t-ainm ollscoil. 65 00:03:08,690 --> 00:03:12,140 >> Agus is é an eochair ag dul a bheith an bhliain nuair a bhí a bunaíodh an ollscoil sin. 66 00:03:12,140 --> 00:03:15,380 Gach blianta d'ollscoileanna ag dul a bheith ceithre dhigit. 67 00:03:15,380 --> 00:03:19,840 Agus mar sin beidh orainn a úsáid na ceithre digití nascleanúint a dhéanamh tríd an struchtúr seo sonraí. 68 00:03:19,840 --> 00:03:22,270 Agus beidh orainn a fheiceáil, arís, conas dhéanaimid sin i díreach an dara. 69 00:03:22,270 --> 00:03:25,110 >> Ag deireadh an cosán, beidh orainn a fheiceáil ar an t-ainm 70 00:03:25,110 --> 00:03:30,250 na hollscoile a fhreagraíonn leis sin eochair, iad siúd ceithre dhigit. 71 00:03:30,250 --> 00:03:34,390 An smaoineamh bunúsach taobh thiar de Trie Is mór dúinn a bealach lárnach. 72 00:03:34,390 --> 00:03:35,640 Mar sin, smaoineamh ar é mar a bheadh ​​crann. 73 00:03:35,640 --> 00:03:39,211 Agus tá sé seo den chineál céanna i litriú agus i gcoincheap le crann. 74 00:03:39,211 --> 00:03:41,460 Go ginearálta nuair a cheapann againn faoi crainn ar fud an domhain fíor, 75 00:03:41,460 --> 00:03:44,090 tá siad ar fhréamh go sa talamh agus iad ag fás aníos 76 00:03:44,090 --> 00:03:46,830 agus tá siad brainsí agus tá siad duilleoga. 77 00:03:46,830 --> 00:03:49,450 Agus go bunúsach an smaoineamh Is Trie díreach mar an gcéanna, 78 00:03:49,450 --> 00:03:51,755 ach amháin go bhfuil an fhréamh ancaire áit éigin sa spéir. 79 00:03:51,755 --> 00:03:53,130 Agus tá na duilleoga ag bun an leathanaigh. 80 00:03:53,130 --> 00:03:55,750 >> Mar sin, tá sé de chineál cosúil le cur crann agus díreach flipping sé bun os cionn. 81 00:03:55,750 --> 00:03:56,880 Ach fós tá brainsí. 82 00:03:56,880 --> 00:03:59,463 Agus bheadh ​​na a bheith ar ár conairí, beidh na a bheith ar ár naisc 83 00:03:59,463 --> 00:04:02,220 ó na fréamhacha go dtí na duilleoga. 84 00:04:02,220 --> 00:04:04,200 Sa chás seo, iad siúd cosáin, na brainsí 85 00:04:04,200 --> 00:04:08,490 bhfuil an lipéadú le digití a insint dúinn cén bealach chun dul ó áit a bhfuil muid. 86 00:04:08,490 --> 00:04:11,800 >> Má fheiceann muid 0, théann muid síos an brainse, má fheiceann muid 1, théann muid síos an brainse, 87 00:04:11,800 --> 00:04:12,900 agus mar sin de agus mar sin de. 88 00:04:12,900 --> 00:04:14,060 Bhuel, cad a chiallaíonn sé? 89 00:04:14,060 --> 00:04:16,519 Bhuel, ciallaíonn sé sin go ag gach pointe acomhal 90 00:04:16,519 --> 00:04:19,260 agus gach nód sa lár agus gach brainse, 91 00:04:19,260 --> 00:04:23,020 tá 10 agus is féidir áiteanna gur féidir linn dul. 92 00:04:23,020 --> 00:04:27,690 Mar sin, tá 10 leideanna ó gach suíomh. 93 00:04:27,690 --> 00:04:30,610 >> Agus é seo i gcás inar féidir iarracht a fháil ar beag giotán imeaglaithe do dhuine éigin 94 00:04:30,610 --> 00:04:34,460 nach bhfuil a lán de tá taithí san eolaíocht ríomhaireachta roimhe. 95 00:04:34,460 --> 00:04:35,960 Ach tá iarracht i ndáiríre uamhnach go leor. 96 00:04:35,960 --> 00:04:37,793 Agus má tá tú ar an deis a bheith ag obair leo 97 00:04:37,793 --> 00:04:40,420 agus an bhfuil tú sásta a tochailt-i agus turgnamh leo, 98 00:04:40,420 --> 00:04:44,234 tá siad i ndáiríre suimiúil go leor struchtúir sonraí a bheith ag obair leis. 99 00:04:44,234 --> 00:04:46,900 Más mian linn a chur isteach gné isteach sa Trie, go léir is gá dúinn a dhéanamh 100 00:04:46,900 --> 00:04:51,360 Tá a thógáil ar an cosán ceart ó na fréamhacha go dtí an duilleog. 101 00:04:51,360 --> 00:04:55,390 Seo an méid gach céim chomh D'fhéadfadh an mbealach cuma mhaith. 102 00:04:55,390 --> 00:04:59,660 Táimid ag dul chun sonraí nua a shainmhíniú struchtúr nód nua ar a dtugtar ar Trie. 103 00:04:59,660 --> 00:05:02,560 >> Agus taobh istigh de na sonraí sin Struchtúr tá dhá phíosa. 104 00:05:02,560 --> 00:05:05,460 Táimid ag dul a stóráil ar an ainm ollscoile. 105 00:05:05,460 --> 00:05:09,410 Agus táimid ag dul a stóráil le sraith de leideanna 106 00:05:09,410 --> 00:05:12,190 le nóid eile den chineál céanna. 107 00:05:12,190 --> 00:05:14,780 Mar sin, arís, tá sé seo gur saghas de choincheap na i ngach áit 108 00:05:14,780 --> 00:05:18,567 tá muid, táimid ag ag 10 féidir áiteanna is féidir linn dul. 109 00:05:18,567 --> 00:05:20,150 Má fheiceann muid 0, théann muid síos an brainse. 110 00:05:20,150 --> 00:05:22,690 Má fheiceann muid 1, an brainse, agus mar sin de agus mar sin de agus mar sin de. 111 00:05:22,690 --> 00:05:25,160 Má deirimid 9, théann muid síos an brainse. 112 00:05:25,160 --> 00:05:28,220 Mar sin, ag gach pointe acomhal, is féidir linn dul ar 10 áiteanna agus is féidir. 113 00:05:28,220 --> 00:05:35,740 Mar sin, tá gach nód a bhfuil 10 leideanna nóid eile, go dtí 10 nóid eile. 114 00:05:35,740 --> 00:05:39,810 >> Agus is é an sonraí táimid stóráil ach an t-ainm na hollscoile. 115 00:05:39,810 --> 00:05:41,060 Mar sin, a ligean ar a thógáil Trie. 116 00:05:41,060 --> 00:05:44,860 A ligean ar chur isteach ar feadh cúpla na míreanna isteach inár Trie. 117 00:05:44,860 --> 00:05:46,740 Mar sin, ag an mbarr an-, is é seo ár n-nód fréimhe. 118 00:05:46,740 --> 00:05:49,740 Is dócha go bhfuil sé seo ag dul a bheith rud éigin tú ag dul dhearbhú a domhanda. 119 00:05:49,740 --> 00:05:53,450 Agus tá tú ag dul a choimeád ar bun a domhanda pointeoir leis an nód i gcónaí. 120 00:05:53,450 --> 00:05:55,360 >> Tá tú ag dul a rá, ionann fréimhe, agus an bhfuil tú 121 00:05:55,360 --> 00:05:57,580 ag dul go dtí malloc féin nód Trie. 122 00:05:57,580 --> 00:05:59,850 Agus riamh bhfuil tú ag dul fhréamh chun teagmháil a dhéanamh arís. 123 00:05:59,850 --> 00:06:02,300 Gach uair is mian leat a tús a nascleanúna tríd, 124 00:06:02,300 --> 00:06:05,802 leagtar tú pointeoir eile cothrom le fhréamh, cosúil le trav, 125 00:06:05,802 --> 00:06:07,760 a bhfuil an sampla I úsáid i gcuid mhaith de mo físeáin 126 00:06:07,760 --> 00:06:11,090 anseo ar stoic agus ar scuainí agus liostaí nasc agus mar sin de. 127 00:06:11,090 --> 00:06:13,320 >> Leagtha tú pointeoir eile iarr trav do traversal. 128 00:06:13,320 --> 00:06:15,890 Agus a úsáideann tú trav nascleanúint tríd an struchtúr sonraí. 129 00:06:15,890 --> 00:06:17,500 Mar sin a ligean ar a fheiceáil conas a d'fhéadfadh sé seo cuma. 130 00:06:17,500 --> 00:06:19,880 Mar sin ceart anois, cad dhéanann nód cuma mhaith? 131 00:06:19,880 --> 00:06:22,920 Bhuel, díreach mar ár sonraí dearbhú struchtúr atá léirithe, 132 00:06:22,920 --> 00:06:26,906 ní mór dúinn a teaghrán, a sa chás seo tá folamh. 133 00:06:26,906 --> 00:06:27,780 Níl rud ar bith anseo. 134 00:06:27,780 --> 00:06:29,550 >> Agus le sraith de 10 leideanna. 135 00:06:29,550 --> 00:06:31,790 Agus an ceart anois, againn ach tá 1 nód sa Trie. 136 00:06:31,790 --> 00:06:33,110 Níl rud ar bith eile ann. 137 00:06:33,110 --> 00:06:36,020 Mar sin go léir 10 de na leideanna pointe a margadh saothair. 138 00:06:36,020 --> 00:06:38,090 Sin an méid léiríonn an dearg. 139 00:06:38,090 --> 00:06:39,500 >> A ligean ar chur isteach ar an teaghrán Harvard. 140 00:06:39,500 --> 00:06:41,999 A ligean ar chur isteach ar an Ollscoil Harvard isteach sa Trie, a 141 00:06:41,999 --> 00:06:43,940 Bunaíodh sa bhliain 1636. 142 00:06:43,940 --> 00:06:48,220 Is mian linn a bhaint as an eochair, 1636, a insint dúinn nuair a bhíonn muid 143 00:06:48,220 --> 00:06:50,140 ag dul a stóráil Harvard sa Trie. 144 00:06:50,140 --> 00:06:51,470 Anois, conas a d'fhéadfadh muid a dhéanamh? 145 00:06:51,470 --> 00:06:52,886 >> D'fhéadfadh sé cuma rud éigin mar seo. 146 00:06:52,886 --> 00:06:54,160 Tús a chur againn ag an fhréamh. 147 00:06:54,160 --> 00:06:56,920 Agus ní mór dúinn na 10 háiteanna is féidir linn dul. 148 00:06:56,920 --> 00:06:59,900 Is é an fhréamh díreach mar aon nód eile den Trie. 149 00:06:59,900 --> 00:07:02,850 Tá 10 áiteanna is féidir linn dul ó anseo. 150 00:07:02,850 --> 00:07:07,215 >> Cá háit ar mian linn a is dócha chun dul go má tá an eochair 1636? 151 00:07:07,215 --> 00:07:08,340 Níl i ndáiríre dhá rogha. 152 00:07:08,340 --> 00:07:08,450 Ceart. 153 00:07:08,450 --> 00:07:10,825 Is féidir linn a thógáil ar an eochair ó ceart ar chlé agus tús le 6. 154 00:07:10,825 --> 00:07:14,000 Nó d'fhéadfadh muid a thógáil ar an eochair ó chlé go deas agus tús a chur le 1. 155 00:07:14,000 --> 00:07:16,140 >> Tá sé dócha níos mó iomasach mar bheith ag an duine 156 00:07:16,140 --> 00:07:18,110 a tuigimid go mbainfidh ach dul chlé go deas. 157 00:07:18,110 --> 00:07:21,140 Agus mar sin más mian liom a chur isteach Harvard isteach sa Trie, 158 00:07:21,140 --> 00:07:23,560 Ba mhaith liom is dócha a thosú ag tosú ag an fhréamh, 159 00:07:23,560 --> 00:07:25,720 ag féachaint ar mo 10 rogha i os comhair dom, agus ag rá 160 00:07:25,720 --> 00:07:28,700 Ba mhaith liom dul síos an cosán 1. 161 00:07:28,700 --> 00:07:29,700 OK. 162 00:07:29,700 --> 00:07:31,810 >> Anois, tá 1 cosán null faoi láthair. 163 00:07:31,810 --> 00:07:35,920 Mar sin, más mian liom dul ar aghaidh síos go cosán a chur isteach an ghné seo isteach sa Trie, 164 00:07:35,920 --> 00:07:42,040 Caithfidh mé a malloc nód nua, tá 1 pointe ann, agus ansin tá mé go maith chun dul. 165 00:07:42,040 --> 00:07:46,460 >> Mar sin, tá mé go bunúsach ag i gcás ina pointe Tá mé ag seasamh 166 00:07:46,460 --> 00:07:50,270 ag an fhréamh an crann nó an Trie agus tá 10 brainsí. 167 00:07:50,270 --> 00:07:52,260 Ach tá gach brainse a geata os comhair é. 168 00:07:52,260 --> 00:07:53,060 Ceart. 169 00:07:53,060 --> 00:07:54,850 Mar níl rud ar bith eile atá ann. 170 00:07:54,850 --> 00:07:56,522 Níl aon pasáiste sábháilte. 171 00:07:56,522 --> 00:07:58,980 Ciallaíonn sé sin go níl rud ar bith síos aon cheann de na brainsí. 172 00:07:58,980 --> 00:08:02,532 Más mian liom a thógáil chun tús a chur rud éigin, ba mhaith liom a bhaint as an geata. 173 00:08:02,532 --> 00:08:04,490 Ba mhaith liom a bhaint as an geata os comhair uimhir 1. 174 00:08:04,490 --> 00:08:05,698 Agus ba mhaith liom ag siúl síos go. 175 00:08:05,698 --> 00:08:08,060 Agus ba mhaith liom a thógáil áit eile dom dul. 176 00:08:08,060 --> 00:08:09,470 >> Agus sin an méid atá déanta agam anseo. 177 00:08:09,470 --> 00:08:11,430 Mar sin, 1 a thuilleadh pointí a margadh saothair. 178 00:08:11,430 --> 00:08:13,830 Dúirt mé tá sé sábháilte chun dul síos anseo anois. 179 00:08:13,830 --> 00:08:15,789 Tógadh mé nód eile. 180 00:08:15,789 --> 00:08:18,330 Agus nuair a rachaidh mé go dtí sin nód, mé ní mór cinneadh eile a dhéanamh. 181 00:08:18,330 --> 00:08:20,890 Áit a bhfuil mé ag dul chun dul ó anseo? 182 00:08:20,890 --> 00:08:22,700 >> Bhuel, tá mé imithe cheana féin síos ar an 1. 183 00:08:22,700 --> 00:08:24,470 Mar sin, anois is mian liom is dócha chun dul síos an 6. 184 00:08:24,470 --> 00:08:24,970 Ceart. 185 00:08:24,970 --> 00:08:27,100 Arís, tá mé 10 láthair is féidir liom a roghnú. 186 00:08:27,100 --> 00:08:30,060 Mar sin, a ligean ar dul síos anois uimhir 6. 187 00:08:30,060 --> 00:08:32,280 Mar sin mé soiléir ar an geata os comhair uimhir 6. 188 00:08:32,280 --> 00:08:33,250 Agus siúl mé síos ann. 189 00:08:33,250 --> 00:08:34,580 Agus mé a thógáil nód eile. 190 00:08:34,580 --> 00:08:37,630 Agus tá mé bainte amach pointe acomhal eile. 191 00:08:37,630 --> 00:08:40,289 >> Arís, tá mé 10 roghanna do nuair is féidir liom dul. 192 00:08:40,289 --> 00:08:42,799 Tá mé ar athraíodh a ionad ó 1 go 6. 193 00:08:42,799 --> 00:08:44,215 Mar sin, anois is mian liom is dócha chun dul go dtí 3. 194 00:08:44,215 --> 00:08:45,381 3, níl aon áit is féidir liom dul. 195 00:08:45,381 --> 00:08:48,980 Ionas go mbeidh mé go soiléir ar an mbealach agus mé féin a thógáil spás nua. 196 00:08:48,980 --> 00:08:50,870 Agus ansin ó 3, i gcás ina bhfuil mhaith liom dul? 197 00:08:50,870 --> 00:08:52,450 Ba mhaith liom dul síos 6. 198 00:08:52,450 --> 00:08:54,770 >> Agus, arís, bhí orm soiléir ar an mbealach chun é a dhéanamh. 199 00:08:54,770 --> 00:08:59,179 Mar sin, anois tá mé úsáid as mo eochair a chur isteach a chruthú nóid agus tús a thógáil ar an Trie. 200 00:08:59,179 --> 00:09:00,220 Tá mé thosaigh ag an fhréamh. 201 00:09:00,220 --> 00:09:03,666 Tá mé imithe síos 1636. 202 00:09:03,666 --> 00:09:05,540 Agus anois tá mé ag bun ann ar an nód. 203 00:09:05,540 --> 00:09:06,610 Agus d'fhéadfá a bheith in ann é a fheiceáil ar do scáileán. 204 00:09:06,610 --> 00:09:07,735 >> Tá sé seo chun suntais i buí. 205 00:09:07,735 --> 00:09:10,020 Sin an áit a bhfuil mé i láthair na huaire. 206 00:09:10,020 --> 00:09:11,300 Is é mo eochair a dhéanamh. 207 00:09:11,300 --> 00:09:13,030 Tá ídithe mé gach post i mo eochair. 208 00:09:13,030 --> 00:09:15,040 Mar sin, ní féidir liom dul níos faide. 209 00:09:15,040 --> 00:09:17,720 Mar sin, ag an bpointe seo, gach mé gá i ndáiríre a dhéanamh ná a rá, OK. 210 00:09:17,720 --> 00:09:18,990 Tá sé seo de chineál ar cosúil lorg síos ag an talamh, 211 00:09:18,990 --> 00:09:21,115 má tá tú ag shamhlú féin mar an saghas cosán 212 00:09:21,115 --> 00:09:22,350 le naisc éagsúla. 213 00:09:22,350 --> 00:09:25,800 Sórtáil de ag féachaint síos agus saghas spraeála péinteáil Harvard ar an talamh. 214 00:09:25,800 --> 00:09:26,800 Sin an t-ainm seo. 215 00:09:26,800 --> 00:09:28,300 Know go bhfuil an méid atá ag an suíomh seo. 216 00:09:28,300 --> 00:09:31,870 Má thosaíonn muid ag an fhréamh agus a théann muid síos 1 agus ansin 6 agus ansin 3 agus ansin 6, 217 00:09:31,870 --> 00:09:32,780 áit a bhfuil muid? 218 00:09:32,780 --> 00:09:35,640 Bhuel má táimid síos agus feicimid Harvard, ansin 219 00:09:35,640 --> 00:09:38,960 tá a fhios againn go raibh Harvard a bunaíodh sa bhliain 1636 bunaithe ar an mbealach 220 00:09:38,960 --> 00:09:41,400 tá muid ag cur chun feidhme an struchtúr seo sonraí. 221 00:09:41,400 --> 00:09:43,177 Mar sin, bhí go súil againn go simplí. 222 00:09:43,177 --> 00:09:44,760 Táimid ag dul a dhéanamh ar dhá insertions níos mó. 223 00:09:44,760 --> 00:09:50,060 Agus táthar ag súil go mbainfidh sé cabhrú le féach sé seo déanta dhá uair níos mó. 224 00:09:50,060 --> 00:09:52,210 >> Anois, a ligean ar chur isteach ollscoil eile. 225 00:09:52,210 --> 00:09:54,630 A ligean ar chur isteach Yale isteach sa Trie. 226 00:09:54,630 --> 00:09:57,037 Bunaíodh i 1701 bhí Yale. 227 00:09:57,037 --> 00:09:58,870 Mar sin, beidh orainn tús a chur ag an fhréamh, mar a bhíonn againn i gcónaí. 228 00:09:58,870 --> 00:09:59,890 Agus leag muid pointeoir traversal. 229 00:09:59,890 --> 00:10:01,624 Táimid ag dul a úsáid a bhaint as go bhfuil a bhogadh tríd. 230 00:10:01,624 --> 00:10:03,790 An chéad rud ba mhaith linn a dhéanamh ná dul síos an cosán 1. 231 00:10:03,790 --> 00:10:05,830 Sin an chéad dhigit de ár eochair. 232 00:10:05,830 --> 00:10:08,420 Fortunately, áfach, ní dhéanaimid a dhéanamh ar aon obair an am seo. 233 00:10:08,420 --> 00:10:09,919 Tá an cosán 1 réitithe cheana. 234 00:10:09,919 --> 00:10:13,520 Glanadh mé é roimhe nuair mé Bhí a chur isteach Harvard ag 1636. 235 00:10:13,520 --> 00:10:18,090 Mar sin, is féidir liom bogadh go sábháilte síos 1 agus díreach dul ann. 236 00:10:18,090 --> 00:10:20,150 Más féidir bogadh síos ar an 1. 237 00:10:20,150 --> 00:10:22,930 >> Anois, áfach, ba mhaith liom dul go dtí 7. 238 00:10:22,930 --> 00:10:24,280 Glanadh mé an bealach ar 6. 239 00:10:24,280 --> 00:10:27,050 Tá a fhios agam is féidir liom go sábháilte dul ar aghaidh síos an cosán 6. 240 00:10:27,050 --> 00:10:29,220 Ach is gá dom dul ar aghaidh ar an gcosán 7. 241 00:10:29,220 --> 00:10:30,580 Mar sin, cad is gá dom a dhéanamh? 242 00:10:30,580 --> 00:10:35,070 Bhuel, díreach mar a bhíodh, is gá mé díreach tar éis go soiléir ar an geata, a fháil amach as an mbealach, 243 00:10:35,070 --> 00:10:38,740 agus a thógáil nód nua as an cosán 7. 244 00:10:38,740 --> 00:10:40,250 Díreach mar seo. 245 00:10:40,250 --> 00:10:42,930 >> Mar sin, anois tá mé ar athraíodh a ionad 1 agus ansin 7. 246 00:10:42,930 --> 00:10:45,550 Agus faoi deara anois, tá mé saghas den ar an subbranch nua. 247 00:10:45,550 --> 00:10:46,050 Ceart. 248 00:10:46,050 --> 00:10:49,260 Gach rud eile ó 16 ar, ní féidir liom cúram faoi. 249 00:10:49,260 --> 00:10:50,720 Níl mé ag déanamh rud ar bith 16. 250 00:10:50,720 --> 00:10:51,750 Tá mé ag déanamh 17 stuif. 251 00:10:51,750 --> 00:10:58,380 >> Mar sin, anois ó 17 ar aghaidh, caithfidh mé a saghas blaze cosáin nua anseo. 252 00:10:58,380 --> 00:11:00,462 Is é mo eochair an dhigit chugainn 0. 253 00:11:00,462 --> 00:11:01,670 Ní féidir liom a fháil go soiléir in áit ar bith. 254 00:11:01,670 --> 00:11:02,628 Tógadh mé díreach tar éis an nód. 255 00:11:02,628 --> 00:11:04,550 Mar sin, tá a fhios agam níl aon cosáin ar aghaidh ó anseo. 256 00:11:04,550 --> 00:11:06,370 Mar sin, caithfidh mé a dhéanamh ar cheann féin. 257 00:11:06,370 --> 00:11:09,360 >> Mar sin, malloc mé nód nua agus tá 0 phointe ann. 258 00:11:09,360 --> 00:11:12,770 Agus ansin amháin níos mó ama, malloc mé nód nua agus tá pointe amháin ann. 259 00:11:12,770 --> 00:11:15,870 Arís, tá mé ídithe mo eochair, 1701. 260 00:11:15,870 --> 00:11:18,472 Mar sin, tá mé síos agus spraeála liom péint Yale. 261 00:11:18,472 --> 00:11:19,680 Sin an t-ainm seo a nód. 262 00:11:19,680 --> 00:11:24,660 >> Agus mar sin anois más gá dom riamh a fheiceáil má Yale Tá an Trie, tús a chur mé ag an fhréamh, 263 00:11:24,660 --> 00:11:27,060 Téim síos 1701, agus breathnú síos. 264 00:11:27,060 --> 00:11:30,030 Agus má fheiceann mé Yale spraeála péinteáilte ar an talamh, ansin 265 00:11:30,030 --> 00:11:32,200 Tá a fhios agam Yale ann sa Trie. 266 00:11:32,200 --> 00:11:32,950 A ligean ar a dhéanamh amháin níos mó. 267 00:11:32,950 --> 00:11:36,430 A ligean ar chur isteach Dartmouth isteach sa Trie, a bunaíodh i 1769 bhí ina. 268 00:11:36,430 --> 00:11:37,750 >> Tosaigh ag an fhréamh arís. 269 00:11:37,750 --> 00:11:39,445 Is é mo chéad dhigit de mo eochair 1. 270 00:11:39,445 --> 00:11:40,820 Is féidir liom dul go sábháilte síos go cosán. 271 00:11:40,820 --> 00:11:42,400 Atá ann cheana. 272 00:11:42,400 --> 00:11:44,040 Is é an dhigit eile de mo eochair 7. 273 00:11:44,040 --> 00:11:45,890 Is féidir liom dul go sábháilte síos go cosán. 274 00:11:45,890 --> 00:11:47,540 Tá sé ann chomh maith. 275 00:11:47,540 --> 00:11:49,000 >> Is é mo chéad 6. 276 00:11:49,000 --> 00:11:52,860 Ón áit seo, ó áit a bhfuil mé i láthair na huaire i buí ann sa mhéid is go nód lár, 277 00:11:52,860 --> 00:11:56,060 6 faoi ghlas faoi láthair as. 278 00:11:56,060 --> 00:11:58,830 Más mian liom dul síos go cosán, Caithfidh mé a thógáil air féin. 279 00:11:58,830 --> 00:12:02,250 Mar sin, beidh mé malloc nód nua agus tá 6 phointe ann. 280 00:12:02,250 --> 00:12:04,250 Agus ansin, arís, tá mé blazing cosáin nua anseo. 281 00:12:04,250 --> 00:12:10,750 >> Mar sin, malloc mé nód nua ionas gur as go bhfuil uimhir cosán node-- 9-- agus ansin anois 282 00:12:10,750 --> 00:12:13,584 má taisteal mé 1769, agus tá mé ag síos. 283 00:12:13,584 --> 00:12:15,500 Níl rud ar bith faoi láthair spraeála péinteáilte ansin. 284 00:12:15,500 --> 00:12:16,930 Is féidir liom scríobh Dartmouth. 285 00:12:16,930 --> 00:12:20,710 Agus tá mé a cuireadh isteach Dartmouth isteach sa Trie. 286 00:12:20,710 --> 00:12:23,450 >> Mar sin, tá go a chur isteach rudaí isteach sa Trie. 287 00:12:23,450 --> 00:12:25,384 Anois, ba mhaith linn a chuardach le haghaidh rudaí. 288 00:12:25,384 --> 00:12:27,050 Conas is féidir linn a chuardach le haghaidh rudaí sa Trie? 289 00:12:27,050 --> 00:12:29,170 Bhuel, tá sé go leor i bhfad ar an smaoineamh céanna. 290 00:12:29,170 --> 00:12:33,620 Anois táimid ag úsáid ach na digití de na príomh a fháil amach an féidir linn a nascleanúint ó na fréamhacha 291 00:12:33,620 --> 00:12:37,170 chun áit ar mhaith linn dul sa Trie. 292 00:12:37,170 --> 00:12:41,620 >> Má bhuail muid ar deireadh marbh ag pointe ar bith, ansin Tá a fhios againn nach féidir eilimint ann 293 00:12:41,620 --> 00:12:44,500 nó eile a bheadh ​​go cosán curtha glanta cheana. 294 00:12:44,500 --> 00:12:45,930 Má dhéanann muid go léir ar an mbealach chun an deireadh, go léir is gá dúinn a dhéanamh 295 00:12:45,930 --> 00:12:48,471 Is breathnú síos agus a fheiceáil más rud é go an eilimint táimid ag lorg. 296 00:12:48,471 --> 00:12:49,335 Má tá sé, rath. 297 00:12:49,335 --> 00:12:52,610 Más rud é nach bhfuil sé, theipeann. 298 00:12:52,610 --> 00:12:54,940 >> Sin a ligean le cuardach Harvard sa Trie. 299 00:12:54,940 --> 00:12:56,020 Tús a chur againn ag an fhréamh. 300 00:12:56,020 --> 00:12:58,228 Agus, arís, táimid ag dul chun pointeoir traversal chruthú 301 00:12:58,228 --> 00:12:59,390 a dhéanamh ar ár bogann dúinn. 302 00:12:59,390 --> 00:13:02,080 Ó na fréamhacha a fhios againn go bhfuil an Is é an chéad áit ní mór dúinn dul 1, 303 00:13:02,080 --> 00:13:03,390 Is féidir linn a dhéanamh sin? 304 00:13:03,390 --> 00:13:03,982 Is féidir linn. 305 00:13:03,982 --> 00:13:04,690 Má ann go sábháilte. 306 00:13:04,690 --> 00:13:06,660 Is féidir linn dul ann. 307 00:13:06,660 --> 00:13:08,440 >> Anois, is é an áit eile is gá dúinn dul 6. 308 00:13:08,440 --> 00:13:10,557 An dtugann an cosán 6 ann ó anseo? 309 00:13:10,557 --> 00:13:11,140 Yeah, a dhéanann sé. 310 00:13:11,140 --> 00:13:12,690 Is féidir linn dul síos an cosán 6. 311 00:13:12,690 --> 00:13:13,905 Agus muid ag deireadh suas anseo. 312 00:13:13,905 --> 00:13:16,130 >> An féidir linn dul síos an cosán 3 ó anseo? 313 00:13:16,130 --> 00:13:18,450 Bhuel, mar a casadh sé amach, yes, ann go bhfuil an iomarca. 314 00:13:18,450 --> 00:13:20,790 Agus is féidir linn a fháil ar an cosán 6 ó anseo? 315 00:13:20,790 --> 00:13:21,982 Is féidir linn. 316 00:13:21,982 --> 00:13:24,002 >> Nach bhfuil againn go leor fhreagair an cheist go fóill. 317 00:13:24,002 --> 00:13:25,710 Níl fós amháin níos mó chéim, atá anois 318 00:13:25,710 --> 00:13:28,520 ní mór dúinn chun breathnú síos agus féach más rud é go actually-- 319 00:13:28,520 --> 00:13:32,660 má tá muid ag lorg Harvard é, go cad a fháil againn tar éis dúinn sceite an eochair? 320 00:13:32,660 --> 00:13:35,430 Sa sampla tá muid ag baint úsáide as anseo, Is iad na blianta i gcónaí ceithre dhigit. 321 00:13:35,430 --> 00:13:40,280 Ach d'fhéadfá a bheith ag baint úsáide as an sampla ina tá tú ag a stóráil foclóir de na focail. 322 00:13:40,280 --> 00:13:44,060 >> Agus mar sin in ionad a bheith 10 leideanna do mo suíomh, a bheadh ​​agat 26. 323 00:13:44,060 --> 00:13:46,040 Ceann amháin do gach litir den aibítir. 324 00:13:46,040 --> 00:13:50,350 Agus tá roinnt focail cosúil le sciathán leathair, is fo-thacar de bhaisc, mar shampla. 325 00:13:50,350 --> 00:13:53,511 Agus mar sin, fiú má fhaigheann tú go dtí an deireadh an eochair agus tú ag féachaint síos, 326 00:13:53,511 --> 00:13:55,260 nach dtiocfadh leat a fheiceáil cad bhfuil tú ag lorg. 327 00:13:55,260 --> 00:13:58,500 >> Mar sin, tá tú i gcónaí a lean an cosán ar fad agus ansin 328 00:13:58,500 --> 00:14:01,540 má bhí tú in ann go rathúil chun Traverse an cosán ar fad, 329 00:14:01,540 --> 00:14:03,440 breathnú síos agus a dhéanamh deimhniú deiridh amháin. 330 00:14:03,440 --> 00:14:05,120 An é sin cad tá mé ag lorg? 331 00:14:05,120 --> 00:14:07,740 Bhuel, tá mé síos i ndiaidh tosú ag an mbarr agus ag dul 1636. 332 00:14:07,740 --> 00:14:08,240 Táim ag síos. 333 00:14:08,240 --> 00:14:09,400 Feicim Harvard. 334 00:14:09,400 --> 00:14:11,689 Mar sin, tá, d'éirigh mé. 335 00:14:11,689 --> 00:14:13,980 Cad a tharlaíonn má cad Táim ag lorg nach bhfuil sa Trie, cé. 336 00:14:13,980 --> 00:14:17,200 Cad a tharlaíonn má tá mé ag lorg Princeton, a bunaíodh i 1746. 337 00:14:17,200 --> 00:14:20,875 Agus mar sin 1746 thiocfaidh chun bheith mo eochair chun nascleanúint a dhéanamh tríd an Trie. 338 00:14:20,875 --> 00:14:22,040 Bhuel, tús a chur mé ag an fhréamh. 339 00:14:22,040 --> 00:14:24,760 Agus ar an gcéad dul Ba mhaith liom go téann síos an cosán 1. 340 00:14:24,760 --> 00:14:25,590 An féidir liom a dhéanamh? 341 00:14:25,590 --> 00:14:26,490 Sea, is féidir liom. 342 00:14:26,490 --> 00:14:28,730 >> An féidir liom dul síos an cosán 7 ó ann? 343 00:14:28,730 --> 00:14:29,230 Yeah, is féidir liom. 344 00:14:29,230 --> 00:14:30,750 Atá ann freisin. 345 00:14:30,750 --> 00:14:32,460 Ach is féidir liom dul síos an cosán 4 ó anseo? 346 00:14:32,460 --> 00:14:35,550 Sin cosúil ag iarraidh ar an cheist, is féidir Dul ar aghaidh mé síos go cearnach beag 347 00:14:35,550 --> 00:14:37,114 go atá béim mé i buí? 348 00:14:37,114 --> 00:14:38,030 Níl rud ar bith ann. 349 00:14:38,030 --> 00:14:38,610 Ceart. 350 00:14:38,610 --> 00:14:41,310 >> Níl aon bhealach chun tosaigh síos an cosán 4. 351 00:14:41,310 --> 00:14:46,480 Má bhí Princeton sa Trie, go 4 bheadh ​​glanta dúinn cheana. 352 00:14:46,480 --> 00:14:49,130 Agus mar sin ag an bpointe seo tá muid bainte amach ar deireadh marbh. 353 00:14:49,130 --> 00:14:50,250 Ní féidir linn dul níos faide. 354 00:14:50,250 --> 00:14:53,440 Agus mar sin is féidir linn a rá, go cinntitheach, gan aon. 355 00:14:53,440 --> 00:14:56,760 Ní Princeton ann sa Trie. 356 00:14:56,760 --> 00:14:58,860 >> Mar sin, cad a chiallaíonn sé seo go léir? 357 00:14:58,860 --> 00:14:59,360 Ceart. 358 00:14:59,360 --> 00:15:01,000 Níl a lán ar siúl anseo. 359 00:15:01,000 --> 00:15:02,500 Níl leideanna ar fud na háite. 360 00:15:02,500 --> 00:15:04,249 Agus, mar is féidir leat a fheiceáil díreach ón léaráid, 361 00:15:04,249 --> 00:15:07,010 níl a lán de na nóid sin Tá de chineál ar eitilt timpeall. 362 00:15:07,010 --> 00:15:13,480 Ach faoi deara gach uair a bhíomar ag iarraidh a seiceáil cibé raibh rud éigin sa Trie, 363 00:15:13,480 --> 00:15:15,000 bhí againn ach a dhéanamh 4 mbogann. 364 00:15:15,000 --> 00:15:17,208 >> Gach uair bhíomar ag iarraidh a cuir isteach rud éigin sa Trie, 365 00:15:17,208 --> 00:15:20,440 ní mór dúinn a dhéanamh 4 mbogann, b'fhéidir, mallocing roinnt rudaí feadh na slí. 366 00:15:20,440 --> 00:15:23,482 Ach mar a chonaic muid nuair a cuireadh isteach táimid ag Dartmouth isteach sa Trie, 367 00:15:23,482 --> 00:15:25,940 uaireanta roinnt de na cosán D'fhéadfadh a glanadh cheana féin le haghaidh dúinn. 368 00:15:25,940 --> 00:15:30,520 Agus mar sin mar a fhaigheann ár n-Trie níos mó agus níos mó, ní mór dúinn a dhéanamh obair níos lú gach uair 369 00:15:30,520 --> 00:15:32,270 a chur isteach rudaí nua toisc go bhfuil muid cheana 370 00:15:32,270 --> 00:15:35,746 tógtha a lán de na idirmheánacha brainsí feadh na slí. 371 00:15:35,746 --> 00:15:38,370 Má tá muid ach riamh chun breathnú ar 4 rudaí, tá 4 ach tairiseach. 372 00:15:38,370 --> 00:15:41,750 Táimid i ndáiríre de chineál ar druidim leanas a chur isteach am tairiseach 373 00:15:41,750 --> 00:15:44,501 agus Lookup am tairiseach. 374 00:15:44,501 --> 00:15:47,500 An tradeoff, ar ndóigh, a bheith go an Trie, mar is féidir leat insint is dócha, 375 00:15:47,500 --> 00:15:49,030 Is ollmhór. 376 00:15:49,030 --> 00:15:51,040 Gach ceann de na nóid Bíonn suas go leor de spás. 377 00:15:51,040 --> 00:15:52,090 >> Ach sin an tradeoff. 378 00:15:52,090 --> 00:15:55,260 Más mian linn i ndáiríre tapaidh a chur isteach, scriosadh i ndáiríre tapaidh, 379 00:15:55,260 --> 00:15:59,630 agus Lookup ndáiríre tapaidh, ní mór dúinn a tá a lán de na sonraí eitilt timpeall. 380 00:15:59,630 --> 00:16:03,590 Ní mór dúinn a chur ar ceal a lán de spás agus cuimhne don struchtúr sonraí 381 00:16:03,590 --> 00:16:04,290 a bheith ann. 382 00:16:04,290 --> 00:16:05,415 >> Agus mar sin go bhfuil an tradeoff. 383 00:16:05,415 --> 00:16:07,310 Ach tá sé cosúil linn a d'fhéadfadh a fuair sé. 384 00:16:07,310 --> 00:16:09,560 D'fhéadfadh muid a fuarthas amach go Soitheach Naofa de struchtúir sonraí 385 00:16:09,560 --> 00:16:12,264 le leanas a chur isteach tapa, scriosadh, agus a chuardach. 386 00:16:12,264 --> 00:16:14,430 Agus b'fhéidir go mbeidh sé seo a bheith ina Struchtúr sonraí cuí 387 00:16:14,430 --> 00:16:18,890 a úsáid ar cibé faisnéis táimid ag iarraidh a siopa. 388 00:16:18,890 --> 00:16:21,860 Tá mé Doug Lloyd, is é seo CS50. 389 00:16:21,860 --> 00:16:23,433