1
00:00:00,000 --> 00:00:02,994
>> [CHWARAE CERDDORIAETH]

2
00:00:02,994 --> 00:00:05,426

3
00:00:05,426 --> 00:00:08,550
DOUG LLOYD: Felly rydym wedi bod yn inching yn nes
ac yn nes bod greal sanctaidd o ddata

4
00:00:08,550 --> 00:00:13,050
strwythurau, un y gallwn fewnosod
i mewn, dileu o, ac yn edrych i fyny

5
00:00:13,050 --> 00:00:15,440
mewn amser cyson.

6
00:00:15,440 --> 00:00:16,270
Hawl.

7
00:00:16,270 --> 00:00:17,280
Dyna fath o nod.

8
00:00:17,280 --> 00:00:19,720
Rydym am fod yn gallu ei wneud
pethau iawn, yn gyflym iawn.

9
00:00:19,720 --> 00:00:22,580
>> Ydyn ni wedi ei chael yn fan hyn pan fydd
ydym yn sôn am geisiau?

10
00:00:22,580 --> 00:00:23,670
Wel, gadewch i ni edrych.

11
00:00:23,670 --> 00:00:25,628
Felly, rydym wedi gweld nifer o
strwythurau data gwahanol

12
00:00:25,628 --> 00:00:28,680
sy'n trin mapio
hyn a elwir yn barau gwerth allweddol,

13
00:00:28,680 --> 00:00:32,080
mapio rhyw darn o ddata
i ryw ddarn arall o ddata

14
00:00:32,080 --> 00:00:36,020
felly rydym yn gwybod ble i ddod o hyd
gwybodaeth yn y strwythur.

15
00:00:36,020 --> 00:00:40,060
>> Felly, ar gyfer amrywiaeth, er enghraifft, y
allweddol yw'r mynegai elfen neu amrywiaeth

16
00:00:40,060 --> 00:00:42,600
Lleoliad 0 neu 1 amrywiaeth ac yn y blaen.

17
00:00:42,600 --> 00:00:46,140
Ac mae'r gwerth yn y data
sy'n bodoli yn y lleoliad hwnnw.

18
00:00:46,140 --> 00:00:48,550
Felly, beth yn cael ei storio mewn amrywiaeth 0?

19
00:00:48,550 --> 00:00:54,290
Beth sy'n cael ei storio mewn amrywiaeth 1 yn erbyn unig
0 ac 1, a fyddai'n yr allweddi.

20
00:00:54,290 --> 00:00:56,360
>> Gyda bwrdd hash 'i'
math o yr un syniad.

21
00:00:56,360 --> 00:01:00,690
Gyda bwrdd hash, rydym wedi hash hwn
swyddogaeth sy'n cynhyrchu codau hash.

22
00:01:00,690 --> 00:01:03,670
Felly yr allwedd yw'r cod hash y data.

23
00:01:03,670 --> 00:01:06,530
Ac mae'r gwerth, yn enwedig
buom yn siarad am gadwyno

24
00:01:06,530 --> 00:01:10,590
yn y fideo ar fyrddau hash,
yw bod rhestr gysylltiedig o ddata

25
00:01:10,590 --> 00:01:12,550
hynny hashes at y hashcode.

26
00:01:12,550 --> 00:01:14,050
Hawl.

27
00:01:14,050 --> 00:01:16,050
Beth am ymagwedd arall
dull hwn, er bod?

28
00:01:16,050 --> 00:01:21,000
Beth am ddull lle mae'r
allweddol yn sicr o fod yn unigryw,

29
00:01:21,000 --> 00:01:25,410
yn wahanol i dabl hash, lle y gallem
darfod i fyny ag ddau ddarn o ddata

30
00:01:25,410 --> 00:01:27,200
cael yr un hashcode.

31
00:01:27,200 --> 00:01:30,020
Ac yna mae'n rhaid i ni ddelio â
hynny naill ai trwy stilio neu fwy

32
00:01:30,020 --> 00:01:33,340
gorau oll os gadwyno i atgyweiria bod problem.

33
00:01:33,340 --> 00:01:37,520
>> Felly nawr allwn warantu
y bydd ein prif yn unigryw.

34
00:01:37,520 --> 00:01:39,690
A beth os yw ein gwerth yn
dim ond rhywbeth mor hawdd

35
00:01:39,690 --> 00:01:44,080
fel gwir a gau sy'n dweud wrthym p'un
neu os nad y darn hwnnw o wybodaeth

36
00:01:44,080 --> 00:01:45,610
yn bodoli yn y strwythur?

37
00:01:45,610 --> 00:01:48,180
Gallai Boolean fod mor syml â ychydig.

38
00:01:48,180 --> 00:01:52,660
Yn realistig, mae'n fwy na thebyg yn
Beit yn fwy tebygol na ychydig.

39
00:01:52,660 --> 00:01:55,410
Ond mae hynny'n llawer llai na'r
storio efallai llinyn 50-cymeriad,

40
00:01:55,410 --> 00:01:57,360
er enghraifft.

41
00:01:57,360 --> 00:02:02,210
>> Felly ceisiau, yn debyg i hash tablau,
sy'n cyfuno araeau a rhestr gysylltiedig,

42
00:02:02,210 --> 00:02:05,790
geisiau cyfuno arrays,
strwythurau, ac awgrymiadau

43
00:02:05,790 --> 00:02:08,509
at ei gilydd i storio data mewn
ffordd ddiddorol sy'n

44
00:02:08,509 --> 00:02:11,550
'n bert wahanol i
unrhyw beth yr ydym wedi ei weld hyd yn hyn.

45
00:02:11,550 --> 00:02:16,750
Nawr rydym yn defnyddio'r data fel map ffordd
i lywio y strwythur data.

46
00:02:16,750 --> 00:02:18,710
Ac os gallwn ddilyn
y map ffyrdd, os gallwn

47
00:02:18,710 --> 00:02:22,390
dilynwch y data o
dechrau i'r diwedd, yr ydym chi helpu

48
00:02:22,390 --> 00:02:24,945
gwybod a data hwnnw
bodoli yn y trie.

49
00:02:24,945 --> 00:02:28,310
>> Ac os na allwn ddilyn y map
o ystyr i ben o gwbl,

50
00:02:28,310 --> 00:02:30,600
ni all y data bodoli.

51
00:02:30,600 --> 00:02:32,890
Unwaith eto, yr allweddi dyma
sicr o fod yn unigryw.

52
00:02:32,890 --> 00:02:36,020
Ac felly yn wahanol i dabl hash, nid ydym erioed chi helpu
gorfod delio â gwrthdrawiadau yma.

53
00:02:36,020 --> 00:02:39,090
Ac ni ddau ddarn o ddata
yn union yr un map

54
00:02:39,090 --> 00:02:40,530
oni bai bod y data sydd ar union yr un fath.

55
00:02:40,530 --> 00:02:44,580
>> Os byddwn yn mewnosod John, yna
rydym yn chwilio am John.

56
00:02:44,580 --> 00:02:47,430
Dyna dau ddarn union yr un fath o
data, ar y dde, rydym yn edrych drwy'r.

57
00:02:47,430 --> 00:02:49,880
Ond fel arall, mae unrhyw
ddau ddarn o ddata yn

58
00:02:49,880 --> 00:02:52,750
sicr o gael mapiau unigryw
drwy'r strwythur data.

59
00:02:52,750 --> 00:02:56,210
Ac rydym yn mynd i gymryd golwg ar
yn weledol o hyn mewn dim ond hyn o bryd.

60
00:02:56,210 --> 00:02:58,810
>> Byddwn yn gwneud hyn drwy geisio
creu strwythur data newydd,

61
00:02:58,810 --> 00:03:00,564
mapio'r parau gwerth allweddol canlynol.

62
00:03:00,564 --> 00:03:03,480
Yn yr achos hwn, nid ydym yn mynd i ddefnyddio
rhywbeth mor syml â Boolean.

63
00:03:03,480 --> 00:03:06,200
Rydym mewn gwirionedd bydd yn storio'r y llinyn.

64
00:03:06,200 --> 00:03:08,690
A bod llinyn yn mynd i
fod yn enw prifysgol.

65
00:03:08,690 --> 00:03:12,140
>> Ac yr allwedd yn mynd i fod y flwyddyn
pan fydd y brifysgol ei sefydlu.

66
00:03:12,140 --> 00:03:15,380
Pob blwyddyn ar gyfer prifysgolion
yn mynd i fod pedwar digid.

67
00:03:15,380 --> 00:03:19,840
Ac felly byddwn yn defnyddio rhai pedwar digidau ar
lywio drwy'r strwythur data.

68
00:03:19,840 --> 00:03:22,270
A byddwn yn gweld, unwaith eto, sut
rydym yn gwneud hynny mewn dim ond eiliad.

69
00:03:22,270 --> 00:03:25,110
>> Ar ddiwedd y llwybr,
byddwn yn gweld yr enw

70
00:03:25,110 --> 00:03:30,250
y brifysgol sy'n cyfateb
at hynny allweddol, y rhai pedwar digid.

71
00:03:30,250 --> 00:03:34,390
Y syniad sylfaenol y tu ôl i trie
yw bod gennym lwybr ganolog.

72
00:03:34,390 --> 00:03:35,640
Felly, meddyliwch am y peth fel coeden.

73
00:03:35,640 --> 00:03:39,211
Ac mae hyn yn debyg o ran sillafu
ac o ran cysyniad i goeden.

74
00:03:39,211 --> 00:03:41,460
Yn gyffredinol, pan fyddwn yn meddwl am
coed yn y byd go iawn,

75
00:03:41,460 --> 00:03:44,090
mae ganddynt wreiddyn sydd yn y
ddaear ac maent yn tyfu i fyny

76
00:03:44,090 --> 00:03:46,830
ac mae ganddynt ganghennau
ac mae ganddynt ddail.

77
00:03:46,830 --> 00:03:49,450
Ac yn y bôn y syniad o
mae trie yn union yr un fath,

78
00:03:49,450 --> 00:03:51,755
ac eithrio bod gwreiddyn yn cael ei angori
rhywle yn yr awyr.

79
00:03:51,755 --> 00:03:53,130
Ac mae'r dail ar y gwaelod.

80
00:03:53,130 --> 00:03:55,750
>> Felly mae'n fath o fel cymryd coeden
a dim ond flipping ei ben i lawr.

81
00:03:55,750 --> 00:03:56,880
Ond mae canghennau o hyd.

82
00:03:56,880 --> 00:03:59,463
A byddai hynny yn ein llwybrau,
Bydd hynny yn ein cysylltiadau

83
00:03:59,463 --> 00:04:02,220
o'r gwraidd i'r dail.

84
00:04:02,220 --> 00:04:04,200
Yn yr achos hwn, y rhai
llwybrau, canghennau hynny

85
00:04:04,200 --> 00:04:08,490
yn cael eu labelu gyda digidau bod yn dweud wrthym
pa ffordd i fynd o sefyllfa yr ydym ynddi.

86
00:04:08,490 --> 00:04:11,800
>> Os byddwn yn gweld 0, rydym yn mynd i lawr y gangen hon,
os byddwn yn gweld 1, rydym yn mynd i lawr y gangen hon,

87
00:04:11,800 --> 00:04:12,900
ac yn y blaen ac yn y blaen.

88
00:04:12,900 --> 00:04:14,060
Wel, beth mae hyn yn ei olygu?

89
00:04:14,060 --> 00:04:16,519
Wel, mae hynny'n golygu bod
ar bob pwynt gyffordd

90
00:04:16,519 --> 00:04:19,260
a phob nod yn y
canol a phob cangen,

91
00:04:19,260 --> 00:04:23,020
mae 10 y bo modd
lleoedd y gallwn fynd.

92
00:04:23,020 --> 00:04:27,690
Felly mae 10 awgrymiadau
o bob lleoliad.

93
00:04:27,690 --> 00:04:30,610
>> A dyma lle y gall cais gael
ychydig bach codi ofn ar rywun

94
00:04:30,610 --> 00:04:34,460
pwy sydd nad oes gan lawer o
profiad mewn cyfrifiadureg o'r blaen.

95
00:04:34,460 --> 00:04:35,960
Ond geisiau yn wir yn eithaf anhygoel.

96
00:04:35,960 --> 00:04:37,793
Ac os ydych yn cael y
cyfle i weithio gyda nhw

97
00:04:37,793 --> 00:04:40,420
ac rydych yn barod i gloddio i mewn
ac yn arbrofi â hwy,

98
00:04:40,420 --> 00:04:44,234
eu bod yn wir yn eithaf diddorol
strwythurau data i weithio gyda.

99
00:04:44,234 --> 00:04:46,900
Os ydym am i fewnosod elfen
i mewn i'r trie, pob mae angen i ni ei wneud

100
00:04:46,900 --> 00:04:51,360
yn adeiladu'r llwybr cywir
o'r gwraidd i'r ddeilen.

101
00:04:51,360 --> 00:04:55,390
Dyma beth pob cam ar hyd
Efallai y ffordd yn edrych fel.

102
00:04:55,390 --> 00:04:59,660
Rydym yn mynd i ddiffinio ddata newydd
strwythur ar gyfer cainc newydd o'r enw trie.

103
00:04:59,660 --> 00:05:02,560
>> Ac tu mewn data hwnnw
Strwythur mae dau ddarn.

104
00:05:02,560 --> 00:05:05,460
Rydym yn mynd i storio'r
enwi prifysgol.

105
00:05:05,460 --> 00:05:09,410
Ac rydym yn mynd i storio
amrywiaeth o awgrymiadau

106
00:05:09,410 --> 00:05:12,190
i nodau eraill o'r un math.

107
00:05:12,190 --> 00:05:14,780
Felly, unwaith eto, mae hyn yn y math
o gysyniad o bob man

108
00:05:14,780 --> 00:05:18,567
ydym, yr ydym yn 10 bosib
llefydd gallwn fynd.

109
00:05:18,567 --> 00:05:20,150
Os byddwn yn gweld 0, rydym yn mynd i lawr gangen hon.

110
00:05:20,150 --> 00:05:22,690
Os byddwn yn gweld 1, gangen hon,
ac yn y blaen ac yn y blaen ac yn y blaen.

111
00:05:22,690 --> 00:05:25,160
Os dywedwn 9, rydym yn mynd i lawr gangen hon.

112
00:05:25,160 --> 00:05:28,220
Felly, ar bob pwynt gyffordd,
gallwn fynd 10 lle posibl.

113
00:05:28,220 --> 00:05:35,740
Felly bob nod wedi i gynnwys 10 o awgrymiadau
at ganolfannau eraill, i 10 nodau eraill.

114
00:05:35,740 --> 00:05:39,810
>> Ac mae'r data yr ydym yn storio yn
dim ond enw'r brifysgol.

115
00:05:39,810 --> 00:05:41,060
Felly gadewch i ni adeiladu trie.

116
00:05:41,060 --> 00:05:44,860
Gadewch i ni mewnosod cwpl
o eitemau yn ein trie.

117
00:05:44,860 --> 00:05:46,740
Felly, ar y brig,
mae hyn yn ein nod gwraidd.

118
00:05:46,740 --> 00:05:49,740
Mae'n debyg bod hyn yn mynd i fod yn rhywbeth
ydych yn mynd i fyd-eang ddatgan.

119
00:05:49,740 --> 00:05:53,450
A ydych yn mynd i fyd-eang cynnal
pwyntydd i'r nod hwn bob amser.

120
00:05:53,450 --> 00:05:55,360
>> Rydych yn mynd i ddweud,
gwraidd hafal, ac rydych yn

121
00:05:55,360 --> 00:05:57,580
mynd i malloc eich hun nod trie.

122
00:05:57,580 --> 00:05:59,850
A byth rydych yn mynd
i gyffwrdd gwraidd eto.

123
00:05:59,850 --> 00:06:02,300
Bob tro y byddwch eisiau
dechrau lywio trwy,

124
00:06:02,300 --> 00:06:05,802
chi osod pwyntydd arall
cyfartal i gwraidd, megis Trav,

125
00:06:05,802 --> 00:06:07,760
sef yr enghraifft yr wyf yn
defnyddio mewn llawer o fy fideos

126
00:06:07,760 --> 00:06:11,090
yma ar y staciau a ciwiau
a rhestrau cyswllt ac yn y blaen.

127
00:06:11,090 --> 00:06:13,320
>> Rydych yn gosod pwyntydd arall
Gelwir Trav ar gyfer llwybro.

128
00:06:13,320 --> 00:06:15,890
A ydych yn defnyddio Trav i lywio
drwy'r strwythur data.

129
00:06:15,890 --> 00:06:17,500
Felly, gadewch i ni weld sut y gallai hyn edrych.

130
00:06:17,500 --> 00:06:19,880
Felly ar hyn o bryd, beth
mae cainc yn edrych?

131
00:06:19,880 --> 00:06:22,920
Wel, yn union fel ein data
Nododd datganiad strwythur,

132
00:06:22,920 --> 00:06:26,906
mae gennym llinyn, a oedd yn
yn yr achos hwn yn wag.

133
00:06:26,906 --> 00:06:27,780
Does dim byd yma.

134
00:06:27,780 --> 00:06:29,550
>> Ac amrywiaeth o 10 o awgrymiadau.

135
00:06:29,550 --> 00:06:31,790
Ac yn hyn o bryd, rydym yn unig
wedi 1 nod yn y trie hwn.

136
00:06:31,790 --> 00:06:33,110
Does dim byd arall ynddo.

137
00:06:33,110 --> 00:06:36,020
Felly yr holl 10 o'r rheiny
awgrymiadau pwynt i'w null.

138
00:06:36,020 --> 00:06:38,090
Dyna beth y coch yn dangos.

139
00:06:38,090 --> 00:06:39,500
>> Gadewch i mewnosoder y llinyn Harvard.

140
00:06:39,500 --> 00:06:41,999
Gadewch i mewnosoder y Brifysgol
Harvard i mewn i trie hwn, a oedd yn

141
00:06:41,999 --> 00:06:43,940
ei sefydlu yn y flwyddyn 1636.

142
00:06:43,940 --> 00:06:48,220
Rydym am ddefnyddio'r allweddol,
1636, i ddweud wrthym ble rydym yn

143
00:06:48,220 --> 00:06:50,140
mynd i storio Harvard yn y trie.

144
00:06:50,140 --> 00:06:51,470
Yn awr, sut y gallem wneud hynny?

145
00:06:51,470 --> 00:06:52,886
>> Gallai fod yn edrych yn debyg i hyn.

146
00:06:52,886 --> 00:06:54,160
Rydym yn dechrau yn y gwraidd.

147
00:06:54,160 --> 00:06:56,920
Ac mae gennym y 10 o leoedd gallwn fynd.

148
00:06:56,920 --> 00:06:59,900
Mae'r gwreiddyn yn union fel unrhyw
nod arall y trie.

149
00:06:59,900 --> 00:07:02,850
Mae 10 o leoedd gallwn fynd oddi yma.

150
00:07:02,850 --> 00:07:07,215
>> Ble rydym yn fwy na thebyg eisiau
i fynd os yw'r allwedd yw 1636?

151
00:07:07,215 --> 00:07:08,340
Mae 'n sylweddol ddau opsiwn.

152
00:07:08,340 --> 00:07:08,450
Hawl.

153
00:07:08,450 --> 00:07:10,825
Gallwn adeiladu y allweddol o'r
dde i'r chwith a dechrau gyda 6.

154
00:07:10,825 --> 00:07:14,000
Neu gallem adeiladu allweddol o'r
chwith i'r dde ac yn dechrau gyda 1.

155
00:07:14,000 --> 00:07:16,140
>> Mae'n fwy na thebyg yn fwy
sythweledol fel bod dynol

156
00:07:16,140 --> 00:07:18,110
er mwyn deall ein bod fe
dim ond ewch i'r chwith i'r dde.

157
00:07:18,110 --> 00:07:21,140
Ac felly os ydw i eisiau i fewnosod
Harvard i mewn i trie hwn,

158
00:07:21,140 --> 00:07:23,560
Mae'n debyg fy mod am ddechrau
drwy ddechrau yn y gwraidd,

159
00:07:23,560 --> 00:07:25,720
edrych ar fy 10 opsiynau
o fy mlaen, ac yn dweud

160
00:07:25,720 --> 00:07:28,700
Dw i eisiau mynd i lawr y llwybr 1.

161
00:07:28,700 --> 00:07:29,700
IAWN.

162
00:07:29,700 --> 00:07:31,810
>> Yn awr, 1 llwybr yn null hyn o bryd.

163
00:07:31,810 --> 00:07:35,920
Felly, os ydw i am fynd ymlaen i lawr y llwybr hwnnw
i fewnosod elfen hon yn y trie,

164
00:07:35,920 --> 00:07:42,040
Mae'n rhaid i mi malloc cainc newydd, wedi 1
pwyntio yno, ac yna rwy'n da i fynd.

165
00:07:42,040 --> 00:07:46,460
>> Felly, yr wyf yn y bôn mod mewn
pwynt lle Dwi'n sefyll

166
00:07:46,460 --> 00:07:50,270
wrth wraidd y goeden neu'r
trie ac mae 10 o ganghennau.

167
00:07:50,270 --> 00:07:52,260
Ond mae gan bob cangen mae gan
giât o'i flaen.

168
00:07:52,260 --> 00:07:53,060
Hawl.

169
00:07:53,060 --> 00:07:54,850
Gan nad oes unrhyw beth arall mae 'na.

170
00:07:54,850 --> 00:07:56,522
Dim taith ddiogel.

171
00:07:56,522 --> 00:07:58,980
Mae hynny'n golygu nad oes dim byd
i lawr unrhyw un o'r canghennau hynny.

172
00:07:58,980 --> 00:08:02,532
Os wyf am ddechrau adeiladu
rhywbeth, yr wyf am gael gwared ar y giât.

173
00:08:02,532 --> 00:08:04,490
Rwyf am gael gwared ar y giât
o flaen rhif 1.

174
00:08:04,490 --> 00:08:05,698
Ac yr wyf yn awyddus i gerdded i lawr hynny.

175
00:08:05,698 --> 00:08:08,060
Ac yr wyf am adeiladu
lle arall i mi fynd.

176
00:08:08,060 --> 00:08:09,470
>> A dyna beth yr wyf wedi ei wneud yma.

177
00:08:09,470 --> 00:08:11,430
Felly 1 bellach yn cyfeirio at null.

178
00:08:11,430 --> 00:08:13,830
Rwyf wedi dweud ei fod yn ddiogel i fynd i lawr yma nawr.

179
00:08:13,830 --> 00:08:15,789
Yr wyf yn adeiladu nôd arall.

180
00:08:15,789 --> 00:08:18,330
A pan fyddaf yn cyrraedd y nod, yr wyf yn
rhaid i benderfyniad arall i'w wneud.

181
00:08:18,330 --> 00:08:20,890
Ble ydw i'n mynd i fynd o fan hyn?

182
00:08:20,890 --> 00:08:22,700
>> Wel, yr wyf eisoes wedi mynd i lawr yr 1.

183
00:08:22,700 --> 00:08:24,470
Felly, yn awr yr wyf yn ôl pob tebyg am fynd i lawr y 6.

184
00:08:24,470 --> 00:08:24,970
Hawl.

185
00:08:24,970 --> 00:08:27,100
Unwaith eto, mae gennyf 10 lleoliad y gallaf ddewis.

186
00:08:27,100 --> 00:08:30,060
Felly, gadewch i ni yn awr yn mynd i lawr rhif 6.

187
00:08:30,060 --> 00:08:32,280
Felly, yr wyf clirio'r giât
o flaen rhif 6.

188
00:08:32,280 --> 00:08:33,250
Ac yr wyf yn cerdded i lawr yno.

189
00:08:33,250 --> 00:08:34,580
Ac yr wyf yn adeiladu nôd arall.

190
00:08:34,580 --> 00:08:37,630
Ac yr wyf i wedi cyrraedd pwynt cyffordd arall.

191
00:08:37,630 --> 00:08:40,289
>> Unwaith eto, mae gennyf 10 o ddewisiadau
am ble alla i fynd.

192
00:08:40,289 --> 00:08:42,799
Rydw i wedi symud 1-6.

193
00:08:42,799 --> 00:08:44,215
Felly, yn awr yr wyf yn ôl pob tebyg am fynd i 3.

194
00:08:44,215 --> 00:08:45,381
3, does unman gallaf fynd.

195
00:08:45,381 --> 00:08:48,980
Felly, rhaid i mi glirio'r ffordd
ac adeiladu fy hun yn lle newydd.

196
00:08:48,980 --> 00:08:50,870
Ac yna o 3, ble ydw i am fynd?

197
00:08:50,870 --> 00:08:52,450
Dw i eisiau mynd i lawr 6.

198
00:08:52,450 --> 00:08:54,770
>> Ac, unwaith eto, roedd yn rhaid i I
clirio'r ffordd i wneud hynny.

199
00:08:54,770 --> 00:08:59,179
Felly nawr Rwyf wedi defnyddio fy allwedd i fewnosod creu
nodau a dechrau adeiladu trie hwn.

200
00:08:59,179 --> 00:09:00,220
Rydw i wedi dechrau yn y gwraidd.

201
00:09:00,220 --> 00:09:03,666
Rydw i wedi mynd i lawr 1636.

202
00:09:03,666 --> 00:09:05,540
Ac yn awr rwy'n ar y gwaelod
yno ar y nod.

203
00:09:05,540 --> 00:09:06,610
Ac efallai y byddwch yn gallu
ei weld ar eich sgrîn.

204
00:09:06,610 --> 00:09:07,735
>> Mae'n hamlygu mewn melyn.

205
00:09:07,735 --> 00:09:10,020
Dyna lle yr wyf ar hyn o bryd.

206
00:09:10,020 --> 00:09:11,300
Mae fy allwedd yn cael ei wneud.

207
00:09:11,300 --> 00:09:13,030
Rydw i wedi blino'n lân pob sefyllfa yn fy allweddol.

208
00:09:13,030 --> 00:09:15,040
Felly, ni allaf fynd ymhellach.

209
00:09:15,040 --> 00:09:17,720
Felly, yn y fan hon, popeth o fewn fy
'n sylweddol angen ei wneud yw dweud, OK.

210
00:09:17,720 --> 00:09:18,990
Mae'n fath o debyg chwilio
i lawr ar y ddaear,

211
00:09:18,990 --> 00:09:21,115
os ydych yn Envisioning
eich hun fel y math hwn o lwybr

212
00:09:21,115 --> 00:09:22,350
gyda gwahanol gysylltiadau.

213
00:09:22,350 --> 00:09:25,800
Trefnu yn edrych i lawr ac yn fath o
chwistrellu peintio Harvard ar lawr gwlad.

214
00:09:25,800 --> 00:09:26,800
Dyna enw'r hwn.

215
00:09:26,800 --> 00:09:28,300
Gwybod dyna beth sydd yn y lleoliad hwn.

216
00:09:28,300 --> 00:09:31,870
Os byddwn yn dechrau wrth wraidd ac rydym yn mynd i lawr
1 ac yna 6 ac yna 3 ac yna 6,

217
00:09:31,870 --> 00:09:32,780
ble rydym ni?

218
00:09:32,780 --> 00:09:35,640
Wel, os ydym yn edrych i lawr
ac rydym yn gweld Harvard, ac yna

219
00:09:35,640 --> 00:09:38,960
rydym yn gwybod bod Harvard oedd
a sefydlwyd yn 1636 yn seiliedig ar y ffordd

220
00:09:38,960 --> 00:09:41,400
rydym yn gweithredu'r strwythur data.

221
00:09:41,400 --> 00:09:43,177
Felly dyna oedd, gobeithio syml.

222
00:09:43,177 --> 00:09:44,760
Rydym yn mynd i wneud dau mewnosodiadau mwy.

223
00:09:44,760 --> 00:09:50,060
A gobeithio y bydd yn helpu i
gweld hyn ei wneud ddwywaith yn fwy.

224
00:09:50,060 --> 00:09:52,210
>> Yn awr, gadewch i ni mewnosod brifysgol arall.

225
00:09:52,210 --> 00:09:54,630
Gadewch i ni mewnosod Iâl i mewn i trie hwn.

226
00:09:54,630 --> 00:09:57,037
Roedd Yale sefydlu ym 1701.

227
00:09:57,037 --> 00:09:58,870
Felly byddwn yn dechrau ar y
gwraidd, fel yr ydym bob amser yn gwneud.

228
00:09:58,870 --> 00:09:59,890
Ac rydym yn gosod pwyntydd llwybro.

229
00:09:59,890 --> 00:10:01,624
Rydym yn mynd i ddefnyddio hynny i symud drwy'r.

230
00:10:01,624 --> 00:10:03,790
Y peth cyntaf yr ydym am ei
ei wneud yw mynd i lawr y llwybr 1.

231
00:10:03,790 --> 00:10:05,830
Dyna y digid cyntaf ein allweddol.

232
00:10:05,830 --> 00:10:08,420
Yn ffodus, fodd bynnag, nid ydym yn ei wneud
rhaid i wneud unrhyw waith y tro hwn.

233
00:10:08,420 --> 00:10:09,919
Mae'r llwybr 1 eisoes wedi cael ei glirio.

234
00:10:09,919 --> 00:10:13,520
Yr wyf yn clirio ei fod o'r blaen pan oeddwn
yn mewnosod Harvard yn 1636.

235
00:10:13,520 --> 00:10:18,090
Felly gallaf symud yn ddiogel
i lawr 1 a dim ond yn mynd yno.

236
00:10:18,090 --> 00:10:20,150
Os gall symud i lawr y 1.

237
00:10:20,150 --> 00:10:22,930
>> Yn awr, fodd bynnag, yr wyf eisiau mynd i 7.

238
00:10:22,930 --> 00:10:24,280
Yr wyf yn clirio'r ffordd ar 6.

239
00:10:24,280 --> 00:10:27,050
Rwy'n gwybod y gallaf ddiogel
ewch ymlaen i lawr y llwybr 6.

240
00:10:27,050 --> 00:10:29,220
Ond mae angen i mi fynd ymlaen ar y llwybr 7.

241
00:10:29,220 --> 00:10:30,580
Felly beth sydd angen imi ei wneud?

242
00:10:30,580 --> 00:10:35,070
Wel, yn union fel o'r blaen, yr wyf yn jyst angen
i glirio'r giât, ewch allan o'r ffordd,

243
00:10:35,070 --> 00:10:38,740
ac adeiladu nod newydd o'r llwybr 7.

244
00:10:38,740 --> 00:10:40,250
Yn union fel hyn.

245
00:10:40,250 --> 00:10:42,930
>> Felly nawr rwyf wedi symud 1 ac yna 7.

246
00:10:42,930 --> 00:10:45,550
Ac yn awr yn sylwi, rwy'n didoli
y ar y subbranch newydd.

247
00:10:45,550 --> 00:10:46,050
Hawl.

248
00:10:46,050 --> 00:10:49,260
Popeth arall o 16
ar, nid wyf yn poeni am.

249
00:10:49,260 --> 00:10:50,720
Dydw i ddim yn gwneud 16 unrhyw beth.

250
00:10:50,720 --> 00:10:51,750
Rwy'n gwneud 17 o stwff.

251
00:10:51,750 --> 00:10:58,380
>> Felly nawr o 17 ymlaen, rhaid i mi
math o tân llwybrau newydd yma.

252
00:10:58,380 --> 00:11:00,462
Y digid nesaf fy allwedd yw 0.

253
00:11:00,462 --> 00:11:01,670
Rwy'n amlwg na allwn gael unrhyw le.

254
00:11:01,670 --> 00:11:02,628
Fi jyst adeiladwyd nod hwn.

255
00:11:02,628 --> 00:11:04,550
Felly, yr wyf yn gwybod nad oes
llwybrau ymlaen o fan hyn.

256
00:11:04,550 --> 00:11:06,370
Felly, rhaid i mi wneud un fy hun.

257
00:11:06,370 --> 00:11:09,360
>> Felly yr wyf yn malloc yn nod newydd
ac mae ganddynt 0 phwynt yno.

258
00:11:09,360 --> 00:11:12,770
Ac yna un mwy o amser, yr wyf yn malloc yn
nod newydd ac yn cael un pwynt yno.

259
00:11:12,770 --> 00:11:15,870
Unwaith eto, yr wyf wedi blino'n lân fy allwedd, 1701.

260
00:11:15,870 --> 00:11:18,472
Felly yr wyf yn edrych i lawr ac yr wyf yn chwistrellu paent Iâl.

261
00:11:18,472 --> 00:11:19,680
Dyna enw'r nôd hwn.

262
00:11:19,680 --> 00:11:24,660
>> Ac felly yn awr os oes angen erioed i weld a oes Iâl
yn yn y trie hwn, yr wyf yn dechrau yn y gwraidd,

263
00:11:24,660 --> 00:11:27,060
Rwy'n mynd i lawr 1701, ac yn edrych i lawr.

264
00:11:27,060 --> 00:11:30,030
Ac os wyf yn gweld Iâl chwistrellu
paentio ar y ddaear, ac yna

265
00:11:30,030 --> 00:11:32,200
Rwy'n gwybod Iâl yn bodoli yn trie hwn.

266
00:11:32,200 --> 00:11:32,950
Gadewch i ni wneud un yn fwy.

267
00:11:32,950 --> 00:11:36,430
Gadewch i ni mewnosod Dartmouth i mewn i hyn
trie, a sefydlwyd yn 1769.

268
00:11:36,430 --> 00:11:37,750
>> Dechreuwch wrth wraidd eto.

269
00:11:37,750 --> 00:11:39,445
Fy digid cyntaf fy allwedd yw 1.

270
00:11:39,445 --> 00:11:40,820
Gallaf symud yn ddiogel i lawr y llwybr hwnnw.

271
00:11:40,820 --> 00:11:42,400
Mae hynny eisoes yn bodoli.

272
00:11:42,400 --> 00:11:44,040
Mae'r digid nesaf fy allwedd yw 7.

273
00:11:44,040 --> 00:11:45,890
Gallaf symud yn ddiogel i lawr y llwybr hwnnw.

274
00:11:45,890 --> 00:11:47,540
Mae'n bodoli hefyd.

275
00:11:47,540 --> 00:11:49,000
>> Fy nesaf yw 6.

276
00:11:49,000 --> 00:11:52,860
Oddi yma, o'r lle yr wyf ar hyn o bryd
mewn melyn yno yn y nod canol,

277
00:11:52,860 --> 00:11:56,060
6 yn cael ei gloi i ffwrdd ar hyn o bryd.

278
00:11:56,060 --> 00:11:58,830
Os ydw i eisiau mynd i lawr y llwybr,
Mae'n rhaid i mi adeiladu fy hun.

279
00:11:58,830 --> 00:12:02,250
Felly byddaf yn malloc yn nod newydd
ac wedi 6 phwynt yno.

280
00:12:02,250 --> 00:12:04,250
Ac yna, unwaith eto, rwy'n
ffaglu llwybrau newydd yma.

281
00:12:04,250 --> 00:12:10,750
>> Felly yr wyf yn malloc cainc newydd fel bod gan
y rhif y llwybr node-- 9-- ac yna nawr

282
00:12:10,750 --> 00:12:13,584
os byddaf yn teithio 1769, ac yr wyf yn edrych i lawr.

283
00:12:13,584 --> 00:12:15,500
Does dim byd ar hyn o bryd
chwistrellu paentio yno.

284
00:12:15,500 --> 00:12:16,930
Gallaf ysgrifennu Dartmouth.

285
00:12:16,930 --> 00:12:20,710
Ac yr wyf i wedi mewnosod
Dartmouth i mewn i'r trie.

286
00:12:20,710 --> 00:12:23,450
>> Felly dyna mewnosod
pethau i mewn i'r trie.

287
00:12:23,450 --> 00:12:25,384
Nawr rydym am i chwilio am bethau.

288
00:12:25,384 --> 00:12:27,050
Sut ydym yn chwilio am bethau yn y trie?

289
00:12:27,050 --> 00:12:29,170
Wel, mae'n 'n bert lawer yr un syniad.

290
00:12:29,170 --> 00:12:33,620
Nawr rydym jyst arfer y digidau ar yr allwedd
i weld os gallwn lywio gan y gwraidd

291
00:12:33,620 --> 00:12:37,170
i ble rydym am fynd yn y trie.

292
00:12:37,170 --> 00:12:41,620
>> Os byddwn yn taro pen marw ar unrhyw adeg, yna
gwyddom na all yr elfen honno yn bodoli

293
00:12:41,620 --> 00:12:44,500
neu fel arall a fyddai llwybr
eisoes wedi eu clirio.

294
00:12:44,500 --> 00:12:45,930
Os byddwn yn ei wneud yn yr holl ffordd i
y diwedd, i gyd mae angen i ni ei wneud

295
00:12:45,930 --> 00:12:48,471
yn edrych i lawr a gweld os yw hynny'n
yr elfen rydym yn chwilio am.

296
00:12:48,471 --> 00:12:49,335
Os ydyw, llwyddiant.

297
00:12:49,335 --> 00:12:52,610
Os nad yw'n, yn methu.

298
00:12:52,610 --> 00:12:54,940
>> Felly gadewch i ni chwilio am
Harvard yn y trie hwn.

299
00:12:54,940 --> 00:12:56,020
Rydym yn dechrau yn y gwraidd.

300
00:12:56,020 --> 00:12:58,228
Ac, unwaith eto, rydyn ni'n mynd i
creu pwyntydd llwybro

301
00:12:58,228 --> 00:12:59,390
i wneud ein symudiadau i ni.

302
00:12:59,390 --> 00:13:02,080
O'r gwraidd rydym yn gwybod bod y
lle cyntaf mae angen i ni fynd yn 1,

303
00:13:02,080 --> 00:13:03,390
gallwn wneud hynny?

304
00:13:03,390 --> 00:13:03,982
Oes, gallwn.

305
00:13:03,982 --> 00:13:04,690
Os bodoli yn ddiogel.

306
00:13:04,690 --> 00:13:06,660
Gallwn fynd yno.

307
00:13:06,660 --> 00:13:08,440
>> Yn awr, y lle nesaf, mae angen i ni fynd yw 6.

308
00:13:08,440 --> 00:13:10,557
A yw'r llwybr 6 yn bodoli o fan hyn?

309
00:13:10,557 --> 00:13:11,140
Yeah, mae'n ei wneud.

310
00:13:11,140 --> 00:13:12,690
Gallwn fynd i lawr y llwybr 6.

311
00:13:12,690 --> 00:13:13,905
Ac rydym yn y pen draw fan hyn.

312
00:13:13,905 --> 00:13:16,130
>> A allwn ni fynd i lawr y llwybr 3 o fan hyn?

313
00:13:16,130 --> 00:13:18,450
Wel, gan ei fod yn troi allan,
ie, sy'n bodoli hefyd.

314
00:13:18,450 --> 00:13:20,790
A gallwn fynd ar y llwybr 6 o fan hyn?

315
00:13:20,790 --> 00:13:21,982
Oes, gallwn.

316
00:13:21,982 --> 00:13:24,002
>> Nid ydym wedi ateb yn eithaf
y cwestiwn eto.

317
00:13:24,002 --> 00:13:25,710
Mae dal un yn fwy
cam, sydd bellach

318
00:13:25,710 --> 00:13:28,520
mae angen i ni edrych i lawr a
weld os dyna actually--

319
00:13:28,520 --> 00:13:32,660
os ydym yn chwilio am Harvard, yw bod
yr hyn yr ydym yn dod o hyd ar ôl i ni gwacáu y allweddol?

320
00:13:32,660 --> 00:13:35,430
Yn yr enghraifft rydym yn ei ddefnyddio yma,
y blynyddoedd yw pedwar digid bob amser.

321
00:13:35,430 --> 00:13:40,280
Ond efallai y byddwch yn defnyddio'r enghraifft lle
ydych yn storio geiriadur o eiriau.

322
00:13:40,280 --> 00:13:44,060
>> Ac felly yn lle cael 10 o awgrymiadau
ar gyfer fy lleoliad, efallai y byddwch yn cael 26.

323
00:13:44,060 --> 00:13:46,040
Un ar gyfer pob llythyren o'r wyddor.

324
00:13:46,040 --> 00:13:50,350
Ac mae rhai geiriau fel ystlumod,
sydd yn is-set o swp, er enghraifft.

325
00:13:50,350 --> 00:13:53,511
Ac felly hyd yn oed os ydych yn cyrraedd y
diwedd y cyfnod allweddol ac yr ydych yn edrych i lawr,

326
00:13:53,511 --> 00:13:55,260
efallai nad ydych yn gweld yr hyn
rydych chi'n chwilio amdano.

327
00:13:55,260 --> 00:13:58,500
>> Felly, mae'n rhaid i chi bob amser dramwy
y llwybr cyfan ac yna

328
00:13:58,500 --> 00:14:01,540
os oeddech yn gallu llwyddo
i groesi'r llwybr cyfan,

329
00:14:01,540 --> 00:14:03,440
edrych i lawr ac yn gwneud un cadarnhad terfynol.

330
00:14:03,440 --> 00:14:05,120
Ai dyna beth rwy'n chwilio amdano?

331
00:14:05,120 --> 00:14:07,740
Wel, yr wyf yn edrych i lawr ar ôl dechrau
ar y brig ac yn mynd 1636.

332
00:14:07,740 --> 00:14:08,240
Yr wyf yn edrych i lawr.

333
00:14:08,240 --> 00:14:09,400
Rwy'n gweld Harvard.

334
00:14:09,400 --> 00:14:11,689
Felly, ie, yr wyf yn llwyddo.

335
00:14:11,689 --> 00:14:13,980
Beth os yw'r hyn dwi'n chwilio am
Nid yw yn y trie, er.

336
00:14:13,980 --> 00:14:17,200
Beth os ydw i'n chwilio am Princeton,
a sefydlwyd yn 1746.

337
00:14:17,200 --> 00:14:20,875
Ac felly yn dod yn 1746 fy allwedd
i lywio drwy'r trie.

338
00:14:20,875 --> 00:14:22,040
Wel, yr wyf yn dechrau yn y gwraidd.

339
00:14:22,040 --> 00:14:24,760
Ac y lle cyntaf i mi eisiau
i yn mynd i lawr y llwybr 1.

340
00:14:24,760 --> 00:14:25,590
A allaf ei wneud?

341
00:14:25,590 --> 00:14:26,490
Ie, yr wyf yn gallu.

342
00:14:26,490 --> 00:14:28,730
>> A allaf fynd i lawr y llwybr 7 oddi yno?

343
00:14:28,730 --> 00:14:29,230
Yeah, gallaf.

344
00:14:29,230 --> 00:14:30,750
Sy'n bodoli hefyd.

345
00:14:30,750 --> 00:14:32,460
Ond gall yr wyf yn mynd i lawr y llwybr 4 o fan hyn?

346
00:14:32,460 --> 00:14:35,550
Dyna fel gofyn y cwestiwn, gall
Yr wyf yn symud ymlaen i lawr mai ychydig sgwâr

347
00:14:35,550 --> 00:14:37,114
fy mod i wedi hamlygu mewn melyn?

348
00:14:37,114 --> 00:14:38,030
Does dim byd yno.

349
00:14:38,030 --> 00:14:38,610
Hawl.

350
00:14:38,610 --> 00:14:41,310
>> Does dim ffordd ymlaen i lawr y llwybr 4.

351
00:14:41,310 --> 00:14:46,480
Os oedd Princeton yn y trie hwn, fod 4
Byddai wedi cael eu clirio i ni yn barod.

352
00:14:46,480 --> 00:14:49,130
Ac felly yn y fan hon
rydym wedi cyrraedd diwedd marw.

353
00:14:49,130 --> 00:14:50,250
Ni allwn fynd ymhellach.

354
00:14:50,250 --> 00:14:53,440
Ac felly gallwn ddweud, yn bendant, dim.

355
00:14:53,440 --> 00:14:56,760
Nid yw Princeton yn bodoli yn trie hwn.

356
00:14:56,760 --> 00:14:58,860
>> Felly beth mae hyn i gyd yn ei olygu?

357
00:14:58,860 --> 00:14:59,360
Hawl.

358
00:14:59,360 --> 00:15:01,000
Mae llawer yn digwydd yma.

359
00:15:01,000 --> 00:15:02,500
Mae awgrymiadau i gyd dros y lle.

360
00:15:02,500 --> 00:15:04,249
Ac, fel y gwelwch
yn unig gan y diagram,

361
00:15:04,249 --> 00:15:07,010
mae llawer o nodau sy'n
yn fath o hedfan o gwmpas.

362
00:15:07,010 --> 00:15:13,480
Ond sylwi bob tro y byddwn yn awyddus i
gwirio a oedd rhywbeth yn y trie,

363
00:15:13,480 --> 00:15:15,000
byddwn ond roedd yn rhaid i wneud 4 symudiadau.

364
00:15:15,000 --> 00:15:17,208
>> Bob tro y byddwn yn awyddus i
mewnosoder rhywbeth yn y trie,

365
00:15:17,208 --> 00:15:20,440
rhaid i ni wneud 4 symudiadau, o bosibl
mallocing rhai pethau ar hyd y ffordd.

366
00:15:20,440 --> 00:15:23,482
Ond fel y gwelsom pan fyddwn yn mewnosod
Dartmouth i mewn i'r trie,

367
00:15:23,482 --> 00:15:25,940
Weithiau mae rhai o'r llwybr
Efallai eisoes yn cael ei glirio i ni.

368
00:15:25,940 --> 00:15:30,520
Ac felly fel ein trie mynd yn fwy a
mwy, rydym wedi gwneud llai o waith bob tro

369
00:15:30,520 --> 00:15:32,270
i fewnosod pethau newydd
oherwydd ein bod i wedi eisoes

370
00:15:32,270 --> 00:15:35,746
Adeiladwyd llawer o'r canolradd
canghennau ar hyd y ffordd.

371
00:15:35,746 --> 00:15:38,370
Os ydym wedi dim ond erioed i edrych ar
4 bethau, 4 yn unig yw gyson.

372
00:15:38,370 --> 00:15:41,750
Rydym wir yn fath o agosáu
mewnosod amser cyson

373
00:15:41,750 --> 00:15:44,501
a am-edrych o amser yn gyson.

374
00:15:44,501 --> 00:15:47,500
Mae tradeoff, wrth gwrs, yw y
trie hwn, fel y mae'n debyg y gallwch ddweud,

375
00:15:47,500 --> 00:15:49,030
yn enfawr.

376
00:15:49,030 --> 00:15:51,040
Mae pob un o'r nodau hyn
cymryd llawer o le.

377
00:15:51,040 --> 00:15:52,090
>> Ond dyna y tradeoff.

378
00:15:52,090 --> 00:15:55,260
Os ydym am wirioneddol gyflym
mewnosod, dileu 'n sylweddol yn gyflym,

379
00:15:55,260 --> 00:15:59,630
a am-edrych 'n sylweddol yn gyflym, mae'n rhaid i ni
yn cael llawer o ddata yn hedfan o gwmpas.

380
00:15:59,630 --> 00:16:03,590
Mae'n rhaid i neilltuo llawer o le
a chof am y strwythur data

381
00:16:03,590 --> 00:16:04,290
i fodoli.

382
00:16:04,290 --> 00:16:05,415
>> Ac felly dyna y tradeoff.

383
00:16:05,415 --> 00:16:07,310
Ond mae'n edrych fel ein bod
allai fod wedi dod o hyd iddo.

384
00:16:07,310 --> 00:16:09,560
Efallai y byddwn wedi canfod bod
greal sanctaidd o strwythurau data

385
00:16:09,560 --> 00:16:12,264
gyda mewnosod cyflym,
dileu, ac am-edrych.

386
00:16:12,264 --> 00:16:14,430
Ac efallai y bydd hyn yn
strwythur data priodol

387
00:16:14,430 --> 00:16:18,890
i'w ddefnyddio ar gyfer pa bynnag wybodaeth
ydym yn ceisio ei siop.

388
00:16:18,890 --> 00:16:21,860
Rwy'n Doug Lloyd, mae hyn yn cs50.

389
00:16:21,860 --> 00:16:23,433