1
00:00:00,000 --> 00:00:02,770
[Powered by Google Translate] [Alt 7: More Compordach]

2
00:00:02,770 --> 00:00:05,090
[Rob Bowden] [Ollscoil Harvard]

3
00:00:05,090 --> 00:00:07,930
[Is é seo an CS50] [CS50.TV]

4
00:00:07,930 --> 00:00:10,110
Gach ceart. Mar sin, mar a dúirt mé i mo ríomhphost,

5
00:00:10,110 --> 00:00:14,060
tá sé seo dul chun bheith ina alt dénártha-crann-dian.

6
00:00:14,060 --> 00:00:16,820
Ach nach bhfuil go leor ceisteanna.

7
00:00:16,820 --> 00:00:18,920
Mar sin, táimid ag dul chun iarracht a dhéanamh agus a tharraingt gach ceist amach

8
00:00:18,920 --> 00:00:25,430
agus dul isteach go mion painful de na bealaí is fearr chun rudaí a dhéanamh.

9
00:00:25,430 --> 00:00:31,200
Mar sin, ar dheis ag an tús, théann muid trí líníochtaí sampla de chrainn dhénártha agus rudaí.

10
00:00:31,200 --> 00:00:35,970
Mar sin anseo, "Cuimhnigh go bhfuil crann dhénártha nóid cosúil leis na cinn de liosta nasctha,

11
00:00:35,970 --> 00:00:38,150
ach amháin in ionad amháin pointeoir, tá dhá: ceann amháin do na láimhe clé 'leanbh'

12
00:00:38,150 --> 00:00:41,950
agus ceann do na 'leanbh' ceart. "

13
00:00:41,950 --> 00:00:45,630
Mar sin, le crann dhénártha é díreach cosúil le liosta nasctha,

14
00:00:45,630 --> 00:00:47,910
ach amháin an struct ag dul a bheith dhá threo.

15
00:00:47,910 --> 00:00:51,390
Níl crainn trinary, atá ag dul a bheith trí leideanna,

16
00:00:51,390 --> 00:00:56,540
tá N-bhunu crainn, a bhfuil ach pointeoir cineálach

17
00:00:56,540 --> 00:01:00,320
go bhfuil tú ansin a malloc a bheith mór go leor chun a bheith

18
00:01:00,320 --> 00:01:04,840
leideanna go leor chun na páistí go léir is féidir.

19
00:01:04,840 --> 00:01:08,200
Mar sin, a tharlaíonn crann dhénártha ach go bhfuil roinnt leanúnach ar bheirt.

20
00:01:08,200 --> 00:01:11,260
Más mian leat, is féidir leat a thabhairt ar liosta nasctha mar chrann unary,

21
00:01:11,260 --> 00:01:15,360
ach ní dóigh liom go bhfuil duine ar bith glaonna go.

22
00:01:15,360 --> 00:01:18,060
"Tarraing léaráid boscaí-agus-saigheada de nód crann dhénártha

23
00:01:18,060 --> 00:01:24,110
ina bhfuil líon is fearr leat Nate, ar 7, i gcás ina bhfuil gach leanbh pointeoir null. "

24
00:01:24,110 --> 00:01:27,780
Modh sin, iPad.

25
00:01:27,780 --> 00:01:30,280
>> Tá sé seo ag dul a bheith deas simplí.

26
00:01:30,280 --> 00:01:36,150
Táimid ag dul ach go bhfuil nód, beidh mé a tharraingt air mar cearnach.

27
00:01:36,150 --> 00:01:38,730
Agus beidh mé a tharraingt ar na luachanna i anseo.

28
00:01:38,730 --> 00:01:41,090
Mar sin, beidh an luach a théann i anseo,

29
00:01:41,090 --> 00:01:44,770
agus ansin síos anseo beidh orainn an pointeoir chlé ar thaobh na láimhe clé agus an pointeoir ceart ar dheis.

30
00:01:44,770 --> 00:01:50,430
Agus tá sé an-oiread sin coinbhinsiún a ghlaoch air chlé agus ar dheis, ainmneacha pointeoir.

31
00:01:50,430 --> 00:01:52,460
Tá an dá ag dul a bheith ar neamhní.

32
00:01:52,460 --> 00:01:57,870
Beidh sin a bheith díreach faoin margadh saothair, agus go mbeidh a bheith díreach null.

33
00:01:57,870 --> 00:02:03,630
Maith go leor. Mar sin, ar ais go dtí anseo.

34
00:02:03,630 --> 00:02:05,700
"Le liosta nasctha, bhí againn ach a stóráil ar pointeoir

35
00:02:05,700 --> 00:02:09,639
leis an nód chéad uair sa liosta in ord chun cuimhneamh ar an liosta iomlán nasctha, nó ar an liosta iomlán.

36
00:02:09,639 --> 00:02:11,650
Mar an gcéanna, le crainn, ní mór dúinn ach chun a stóráil ar pointeoir

37
00:02:11,650 --> 00:02:13,420
ar nód amháin chun cuimhneamh ar an crann ar fad.

38
00:02:13,420 --> 00:02:15,980
Is é seo an nód calle an 'root' an chrainn.

39
00:02:15,980 --> 00:02:18,320
Tógáil ar do léaráid ó roimh nó ceann nua a tharraingt

40
00:02:18,320 --> 00:02:21,690
den sórt sin go bhfuil tú léiriú boscaí-agus-saigheada de chrann dénártha

41
00:02:21,690 --> 00:02:25,730
leis an luach 7, ansin 3 i thaobh na láimhe clé,

42
00:02:25,730 --> 00:02:32,760
ansin 9 ar an gceart, agus ansin 6 maidir le ceart an 3. "

43
00:02:32,760 --> 00:02:34,810
A ligean ar féach an féidir liom cuimhneamh ar fad i mo cheann.

44
00:02:34,810 --> 00:02:37,670
Mar sin, tá sé seo ag dul a bheith ar ár fréamhacha suas anseo.

45
00:02:37,670 --> 00:02:41,600
Beidh muid go bhfuil roinnt pointeoir áit éigin, rud éigin go beidh orainn glaoch fréimhe,

46
00:02:41,600 --> 00:02:45,140
agus tá sé dírithe an Guy.

47
00:02:45,140 --> 00:02:48,490
Anois, a dhéanamh nód nua,

48
00:02:48,490 --> 00:02:52,870
cad a bhfuil againn, 3 ar chlé?

49
00:02:52,870 --> 00:02:57,140
Mar sin, nód nua le 3, agus pointí sé ar dtús null.

50
00:02:57,140 --> 00:02:59,190
Feicfidh mé a chur díreach N.

51
00:02:59,190 --> 00:03:02,250
Anois, ba mhaith linn a dhéanamh a théann ar an taobh clé de 7.

52
00:03:02,250 --> 00:03:06,840
Mar sin, táimid seo a athrú pointeoir a chur in iúl anois ar an Guy.

53
00:03:06,840 --> 00:03:12,420
Agus a dhéanann muid mar an gcéanna. Tá muid ag iarraidh 9 thar anseo

54
00:03:12,420 --> 00:03:14,620
a deir dtús ach null.

55
00:03:14,620 --> 00:03:19,600
Táimid ag dul leis an pointeoir, pointe a athrú go 9,

56
00:03:19,600 --> 00:03:23,310
agus anois ba mhaith linn a 6 a chur leis an gceart 3.

57
00:03:23,310 --> 00:03:32,170
Mar sin, dul ar é a - a dhéanamh ar 6.

58
00:03:32,170 --> 00:03:34,310
Agus beidh go Guy pointe ann.

59
00:03:34,310 --> 00:03:38,320
Maith go leor. Mar sin, sin uile iarrann sé ar ár gcumas sin a dhéanamh.

60
00:03:38,320 --> 00:03:42,770
>> Anois, a ligean ar dul thar roinnt téarmaíocht.

61
00:03:42,770 --> 00:03:46,690
Labhair muid cheana féin faoi conas a bhfuil an fhréamh an crann an nód barr-is mó sa chrann.

62
00:03:46,690 --> 00:03:54,720
An ceann ina bhfuil 7. An nóid ag bun an chrainn a dtugtar na duilleoga.

63
00:03:54,720 --> 00:04:01,240
Tá aon nód a bhfuil díreach faoin margadh saothair mar chuid leanaí duilleog.

64
00:04:01,240 --> 00:04:03,680
Mar sin, is féidir, má éiríonn lenár n crann dhénártha ach nód amháin,

65
00:04:03,680 --> 00:04:10,130
go bhfuil crann duille, agus go bhfuil sé.

66
00:04:10,130 --> 00:04:12,060
"Is é an 'airde' an chrainn ar líon na leannlusanna a bhfuil tú a dhéanamh

67
00:04:12,060 --> 00:04:16,620
a fháil ó bharr go duilleog. "

68
00:04:16,620 --> 00:04:18,640
Beidh muid a fháil i, sa dara, an difríocht

69
00:04:18,640 --> 00:04:21,940
idir crainn dénártha cothrom agus neamhchothrom,

70
00:04:21,940 --> 00:04:29,470
ach do anois, an airde iomlán an crann

71
00:04:29,470 --> 00:04:34,520
Ba mhaith liom a rá go bhfuil 3, cé go má tá tú ag comhaireamh an líon na n-leannlusanna

72
00:04:34,520 --> 00:04:39,710
caithfidh tú a dhéanamh d'fhonn a fháil go 9, ansin tá sé i ndáiríre ach ar airde de 2.

73
00:04:39,710 --> 00:04:43,340
Ceart anois is é seo an crann dhénártha neamhchothrom,

74
00:04:43,340 --> 00:04:49,840
ach beidh phléamar cothrom nuair a fhaigheann sé a bheith iomchuí.

75
00:04:49,840 --> 00:04:52,040
Mar sin, anois is féidir linn labhairt faoi nóid i gcrann i dtéarmaí

76
00:04:52,040 --> 00:04:54,700
i gcomparáid leis an nóid eile sa chrann.

77
00:04:54,700 --> 00:04:59,730
Mar sin anois táimid tar éis tuismitheoirí, leanaí, deartháireacha, sinsear, agus sliocht.

78
00:04:59,730 --> 00:05:05,650
Tá siad ciall go leor coitianta, cad a chiallaíonn siad.

79
00:05:05,650 --> 00:05:09,610
Má iarraimid - tá sé do thuismitheoirí.

80
00:05:09,610 --> 00:05:12,830
Mar sin, cad é an tuismitheoir de 3?

81
00:05:12,830 --> 00:05:16,090
[Mic Léinn] 7. >> Yeah. Is é an tuismitheoir ag dul ach a bheith cad pointí a thabhairt duit.

82
00:05:16,090 --> 00:05:20,510
Ansin, cad iad na páistí de 7?

83
00:05:20,510 --> 00:05:23,860
[Mic Léinn] 3 agus 9. >> Yeah.

84
00:05:23,860 --> 00:05:26,460
Fógra go ciallaíonn "leanaí" literally leanaí,

85
00:05:26,460 --> 00:05:31,010
Ní bheadh ​​sin 6 i bhfeidhm, mar tá sé cosúil le grandchild.

86
00:05:31,010 --> 00:05:35,540
Ach ansin má táimid sliocht dul, mar sin cad iad na sliocht 7?

87
00:05:35,540 --> 00:05:37,500
[Mic Léinn] 3, 6 agus 9. >> Yeah.

88
00:05:37,500 --> 00:05:42,330
An sliocht an nód fréimhe ag dul a bheith gach rud i an crann,

89
00:05:42,330 --> 00:05:47,950
ach amháin b'fhéidir an nód fréimhe féin, más rud é nach bhfuil tú ag iarraidh a bhreithniú go shliocht.

90
00:05:47,950 --> 00:05:50,750
Agus ar deireadh, sinsear, mar sin tá sé an treo eile.

91
00:05:50,750 --> 00:05:55,740
Mar sin, cad iad na sinsear de 6?

92
00:05:55,740 --> 00:05:58,920
[Mic Léinn] 3 agus 7. >> Yeah. Ní 9 san áireamh.

93
00:05:58,920 --> 00:06:02,520
Tá sé díreach ar ais lineage díreach leis an fhréamh

94
00:06:02,520 --> 00:06:13,230
ag dul a bheith do sinsear.

95
00:06:13,230 --> 00:06:16,300
>> "Deirimid go bhfuil crann dénártha 'ordaigh' má do gach nód sa gcrann,

96
00:06:16,300 --> 00:06:19,530
gach ceann dá shliocht ar chlé ag luachanna níos lú

97
00:06:19,530 --> 00:06:22,890
agus tá gach ceann de na cinn ar dheis luachanna níos mó.

98
00:06:22,890 --> 00:06:27,060
Mar shampla, tá an crann thuas d'ordaigh ach nach bhfuil sé an socrú ach is féidir ordú. "

99
00:06:27,060 --> 00:06:30,180
Sula muid a fháil leis sin,

100
00:06:30,180 --> 00:06:36,420
Tá crann dhénártha ordaigh ar a dtugtar freisin mar chrann cuardaigh dénártha.

101
00:06:36,420 --> 00:06:38,660
Anseo táimid ag a tharlóidh a bheith ag glaoch sé crann dhénártha de réir,

102
00:06:38,660 --> 00:06:41,850
ach ní chuala mé ar a dtugtar sé crann dhénártha ordaithe roimh,

103
00:06:41,850 --> 00:06:46,650
agus ar tráth na gceist go bhfuil muid i bhfad níos mó seans ann a chur crann cuardaigh dénártha.

104
00:06:46,650 --> 00:06:49,250
Tá siad ar cheann agus mar an gcéanna,

105
00:06:49,250 --> 00:06:54,580
agus tá sé tábhachtach aithníonn tú an t-idirdhealú idir crann dhénártha agus crann cuardaigh dénártha.

106
00:06:54,580 --> 00:06:58,830
Is éard is crann dhénártha ach crann a dhíríonn ar dhá rud.

107
00:06:58,830 --> 00:07:02,120
Pointí gach nód dtí dhá rud.

108
00:07:02,120 --> 00:07:06,310
Níl aon réasúnaíocht faoi na luachanna atá pointí sé le.

109
00:07:06,310 --> 00:07:11,370
Mar sin, is maith os cionn anseo, ós rud é tá sé ina crann cuardaigh dénártha,

110
00:07:11,370 --> 00:07:14,030
tá a fhios againn go má théann muid fágtha de 7,

111
00:07:14,030 --> 00:07:16,670
ansin gach ceann de na luachanna gur féidir linn a bhaint amach, b'fhéidir,

112
00:07:16,670 --> 00:07:19,310
ag dul ar chlé de 7 a bheith níos lú ná 7.

113
00:07:19,310 --> 00:07:24,070
Fógra go bhfuil na luachanna níos lú ná 7 3 agus 6.

114
00:07:24,070 --> 00:07:26,040
Glacfar iad ar fad ar an taobh clé de 7.

115
00:07:26,040 --> 00:07:29,020
Má théann muid leis an gceart 7, tá gach rud a bheith níos mó ná 7,

116
00:07:29,020 --> 00:07:33,220
mar sin tá 9 leis an gceart 7, mar sin tá muid go maith.

117
00:07:33,220 --> 00:07:36,150
Ní hé seo an cás le haghaidh crann dhénártha,

118
00:07:36,150 --> 00:07:40,020
le haghaidh crann dénártha rialta féidir linn a bheith díreach 3 ag an mbarr, 7 an taobh clé,

119
00:07:40,020 --> 00:07:47,630
9 an taobh clé den 7; níl aon ordú luachanna ar bith.

120
00:07:47,630 --> 00:07:56,140
Anois, ní bheidh muid a dhéanamh i ndáiríre seo mar tá sé tedious agus gan ghá,

121
00:07:56,140 --> 00:07:59,400
ach "iarracht a tharraingt mar a lán crainn ordaíodh agus is féidir leat smaoineamh ar

122
00:07:59,400 --> 00:08:01,900
ag baint úsáide as na 7 uimhreacha, 3, 9, agus 6.

123
00:08:01,900 --> 00:08:06,800
Cé mhéad socruithe ar leith ann? Cad é an airde gach ceann? "

124
00:08:06,800 --> 00:08:10,480
>> Beidh muid cúpla, ach tá an príomh-smaoineamh,

125
00:08:10,480 --> 00:08:16,530
tá sé seo ar aon bhealach léiriú uathúil de chrann dénártha ina bhfuil na luachanna seo.

126
00:08:16,530 --> 00:08:22,760
Gach gá dúinn go bhfuil roinnt crann dénártha ina bhfuil 7, 3, 6 agus 9.

127
00:08:22,760 --> 00:08:25,960
Bheadh ​​Ceann eile is féidir bailí é an fhréamh 3,

128
00:08:25,960 --> 00:08:30,260
téigh go dtí an taobh clé agus tá sé 6, téigh go dtí an taobh clé agus tá sé 7,

129
00:08:30,260 --> 00:08:32,730
téigh go dtí an taobh clé agus tá sé 9.

130
00:08:32,730 --> 00:08:36,169
Is é sin le crann cuardaigh breá bailí dénártha.

131
00:08:36,169 --> 00:08:39,570
Níl sé an-cabhrach, mar tá sé díreach cosúil le liosta nasctha

132
00:08:39,570 --> 00:08:43,750
agus go bhfuil gach ceann de na leideanna ach null.

133
00:08:43,750 --> 00:08:48,900
Ach tá sé crann bailí. Yeah?

134
00:08:48,900 --> 00:08:51,310
[Mac Léinn] Ná na luachanna a bheith níos mó ar an gceart?

135
00:08:51,310 --> 00:08:56,700
Nó is é seo -? >> Tá na gceist agam dul ar an bhealach eile.

136
00:08:56,700 --> 00:09:00,960
Níl freisin - yeah, a ligean ar athrú go.

137
00:09:00,960 --> 00:09:07,770
9, 7, 6, 3. Ghabháil an Chéasta.

138
00:09:07,770 --> 00:09:11,730
Tá sé fós le déanamh ar a bhfuil cuardach crann dénártha ceaptha a dhéanamh.

139
00:09:11,730 --> 00:09:15,650
Mar sin, tá gach rud ar an taobh clé a bheith níos lú ná aon nód ar leith.

140
00:09:15,650 --> 00:09:23,180
D'fhéadfadh muid a bhogadh go díreach, a rá, an 6 agus é a chur anseo.

141
00:09:23,180 --> 00:09:26,880
No, ní féidir linn. Cén fáth a bhfuil mé a choinneáil á dhéanamh sin?

142
00:09:26,880 --> 00:09:35,350
A ligean ar a dhéanamh - anseo tá 6, anseo 7, 6 pointí le 3.

143
00:09:35,350 --> 00:09:39,290
Tá sé seo fós le crann cuardaigh bailí dénártha.

144
00:09:39,290 --> 00:09:49,260
Cad é atá cearr más rud é go I - a ligean ar féach an féidir liom teacht suas le socrú.

145
00:09:49,260 --> 00:09:52,280
Yeah, maith go leor. Mar sin, cad atá cearr leis an crann?

146
00:09:52,280 --> 00:10:08,920
Buille faoi thuairim mé Tá mé tugtha cheana féin duit leid go bhfuil rud éigin cearr leis.

147
00:10:08,920 --> 00:10:14,430
Cén fáth a bhfuil mé a choinneáil á dhéanamh sin?

148
00:10:14,430 --> 00:10:18,510
Maith go leor. Breathnaíonn sé seo réasúnta.

149
00:10:18,510 --> 00:10:22,590
Má táimid ar gach nód, cosúil le 7, agus ansin ar an taobh clé de 7 3.

150
00:10:22,590 --> 00:10:24,960
Mar sin, ní mór dúinn 3, is é an rud do cheart 3 6.

151
00:10:24,960 --> 00:10:27,750
Agus má fhéachann tú ar 6 is é an rud do cheart 6 a 9.

152
00:10:27,750 --> 00:10:30,910
Mar sin, cén fáth nach bhfuil an crann cuardaigh bailí dénártha?

153
00:10:30,910 --> 00:10:36,330
[Mic Léinn] 9 tá sé fós ar an taobh clé de 7. >> Yeah.

154
00:10:36,330 --> 00:10:43,710
Caithfidh sé a bheith fíor go bhfuil gach luachanna is féidir leat teacht, b'fhéidir, ag dul go dtí an taobh clé den 7 níos lú ná 7.

155
00:10:43,710 --> 00:10:49,120
Má théann muid fágtha de 7, a fháil againn go dtí 3 agus is féidir linn a fháil fós go 6,

156
00:10:49,120 --> 00:10:52,520
is féidir linn a fháil go fóill go dtí 9, ach a bheith imithe níos lú ná 7,

157
00:10:52,520 --> 00:10:55,070
Níor chóir dúinn a bheith in ann a fháil ar roinnt go bhfuil níos mó ná 7.

158
00:10:55,070 --> 00:10:59,830
Mar sin, nach bhfuil an crann cuardaigh bailí dénártha.

159
00:10:59,830 --> 00:11:02,330
>> Mo dheartháir a bhí i ndáiríre ceist agallamh

160
00:11:02,330 --> 00:11:07,760
go raibh go bunúsach seo, cód ach suas rud éigin a bhailíochtú

161
00:11:07,760 --> 00:11:10,500
cibé an bhfuil crann crann cuardaigh dénártha,

162
00:11:10,500 --> 00:11:13,580
agus mar sin bhí an chéad rud a rinne sé ach seiceáil a fheiceáil

163
00:11:13,580 --> 00:11:17,020
má tá an chlé agus ar dheis ceart, agus abair leo ansin síos ann.

164
00:11:17,020 --> 00:11:19,700
Ach ní féidir leat ach é sin a dhéanamh; bhfuil tú súil a choinneáil ar

165
00:11:19,700 --> 00:11:22,550
ar an bhfíric go bhfuil anois tá mé imithe fágtha de 7,

166
00:11:22,550 --> 00:11:26,340
Ní mór gach rud sa subtree a bheith níos lú ná 7.

167
00:11:26,340 --> 00:11:28,430
Ní mór an algartam ceart súil a choinneáil ar

168
00:11:28,430 --> 00:11:35,970
de na teorainneacha gur féidir na luachanna titim b'fhéidir isteach

169
00:11:35,970 --> 00:11:38,360
Ní bheidh muid ag dul tríd gach ceann acu.

170
00:11:38,360 --> 00:11:41,630
Tá ndáil arís deas,

171
00:11:41,630 --> 00:11:44,810
cé nach mór dúinn gotten do na, nó ní bheidh muid a fháil dóibh siúd,

172
00:11:44,810 --> 00:11:47,030
shainiú cé mhéad tá i ndáiríre.

173
00:11:47,030 --> 00:11:53,180
Mar sin, tá 14 acu.

174
00:11:53,180 --> 00:11:56,020
An smaoineamh ar conas a dhéanfaí leat é a dhéanamh go bhfuil go matamaiticiúil cosúil le,

175
00:11:56,020 --> 00:11:59,770
Is féidir leat a roghnú aon cheann amháin a bheith ar an nód fréimhe,

176
00:11:59,770 --> 00:12:03,160
agus ansin más rud é roghnaigh mé 7 a bheith ar an nód fréimhe,

177
00:12:03,160 --> 00:12:08,150
ansin tá, abair, roinnt uimhreacha is féidir a théann a bheith ar mo nód chlé,

178
00:12:08,150 --> 00:12:10,440
agus tá roinnt uimhreacha is féidir a bheith ar mo nód ceart,

179
00:12:10,440 --> 00:12:15,090
ach má tá mé n líon iomlán, ansin an méid is féidir a théann ar an taobh clé

180
00:12:15,090 --> 00:12:18,820
móide go bhfuil an méid is féidir a théann leis an gceart n - 1.

181
00:12:18,820 --> 00:12:26,130
Mar sin, ar an líon atá fágtha, tá siad a bheith in ann dul go dtí an taobh clé nó ceart.

182
00:12:26,130 --> 00:12:31,580
Dealraíonn sé deacair go má chuir mé chéad 3 ansin tá gach rud chun dul go dtí an taobh clé,

183
00:12:31,580 --> 00:12:35,080
ach má chuir mé 7, ansin is féidir roinnt rudaí a théann ar chlé an agus is féidir roinnt rudaí dul go dtí an ceart.

184
00:12:35,080 --> 00:12:39,570
Agus ag '3 'an chéad gceist agam gur féidir gach rud a dul go dtí an ceart.

185
00:12:39,570 --> 00:12:42,350
Tá sé i ndáiríre, tá tú díreach chun smaoineamh ar é mar atá,

186
00:12:42,350 --> 00:12:47,980
Is féidir le cé mhéad rudaí a théann ar an chéad leibhéal eile an chrainn.

187
00:12:47,980 --> 00:12:50,420
Agus a thagann sé amach a bheith 14; nó is féidir leat a tharraingt ar fad iad,

188
00:12:50,420 --> 00:12:54,650
agus ansin beidh tú a fháil 14.

189
00:12:54,650 --> 00:13:01,120
>> Ag dul ar ais anseo,

190
00:13:01,120 --> 00:13:03,510
Is éard is "crainn Ordaíodh dénártha fionnuar mar is féidir linn cuardach a dhéanamh trí iad

191
00:13:03,510 --> 00:13:06,910
ar bhealach an-cosúil le cuardach thar eagar curtha in eagar.

192
00:13:06,910 --> 00:13:10,120
Chun é sin a dhéanamh, táimid ag tosú ag an fhréamh agus ár mbealach obair síos an crann

193
00:13:10,120 --> 00:13:13,440
i dtreo duilleoga, seiceáil gach nód luachanna in aghaidh na luachanna táimid ag cuardach do.

194
00:13:13,440 --> 00:13:15,810
Má tá an nód reatha luach níos lú ná an luach táimid ag lorg,

195
00:13:15,810 --> 00:13:18,050
a théann tú in aice leis an nód leanbh ceart.

196
00:13:18,050 --> 00:13:20,030
Seachas sin, a théann tú chuig an nód leanbh chlé.

197
00:13:20,030 --> 00:13:22,800
Ag pointe éigin, beidh tú ceachtar an luach tú ag lorg, nó go mbainfidh tú rith isteach i margadh saothair,

198
00:13:22,800 --> 00:13:28,520
Ní léiríonn an luach sa chrann. "

199
00:13:28,520 --> 00:13:32,450
Caithfidh mé a ataispeáin an crann a bhí againn roimh; beidh a ghlacadh ar an dara.

200
00:13:32,450 --> 00:13:38,280
Ach ba mhaith linn chun breathnú suas an bhfuil 6, 10, agus 1 i gcrann.

201
00:13:38,280 --> 00:13:49,180
Mar sin, cad a bhí sé, 7, 9, 3, 6. Maith go leor.

202
00:13:49,180 --> 00:13:52,730
Na huimhreacha is mian leat chun breathnú suas, ba mhaith linn chun breathnú suas 6.

203
00:13:52,730 --> 00:13:55,440
Conas a dhéanann an obair algartam?

204
00:13:55,440 --> 00:14:03,040
Bhuel, ní mór dúinn freisin roinnt pointeoir fréimhe ar ár crann.

205
00:14:03,040 --> 00:14:12,460
Agus ba mhaith linn dul go dtí an fhréamh agus a rá, tá an luach is comhionann le luach táimid ag cuardach do?

206
00:14:12,460 --> 00:14:15,000
Mar sin, táimid ag lorg 6, agus mar sin nach bhfuil sé cothrom.

207
00:14:15,000 --> 00:14:20,140
Mar sin, a choinneáil orainn ag dul, agus anois deirimid, maith go leor, mar sin tá 6 níos lú ná 7.

208
00:14:20,140 --> 00:14:23,940
Chiallaíonn sin ba mhaith linn dul ar chlé, nó ar mhaith linn a dul go dtí an ceart?

209
00:14:23,940 --> 00:14:27,340
[Mac Léinn] Clé. >> Yeah.

210
00:14:27,340 --> 00:14:33,340
Tá sé i bhfad níos éasca, tá gach leat a dhéanamh a tharraingt ar cheann nód is féidir ar an crann

211
00:14:33,340 --> 00:14:37,760
agus ansin tú don't - in ionad an iarraidh chun smaoineamh i do cheann,

212
00:14:37,760 --> 00:14:40,020
ceart go leor, má tá sé níos lú, is féidir liom dul go dtí an taobh clé nó an ceart dul,

213
00:14:40,020 --> 00:14:43,030
díreach ag féachaint ar an bpictiúr seo, tá sé an-soiléir go bhfuil mé chun dul go dtí an taobh clé

214
00:14:43,030 --> 00:14:47,700
má tá an nód níos mó ná an luach go bhfuil mé ag lorg.

215
00:14:47,700 --> 00:14:52,600
Mar sin, a théann tú ar chlé, anois tá mé ag 3.

216
00:14:52,600 --> 00:14:57,770
Ba mhaith liom - 3 níos lú ná an luach Táim ag lorg, a bhfuil 6.

217
00:14:57,770 --> 00:15:03,420
Mar sin, táimid ag dul go dtí an ceart, agus anois mé deireadh suas ag 6,

218
00:15:03,420 --> 00:15:07,380
a bhfuil an luach Táim ag lorg, mar sin mé ar ais fíor.

219
00:15:07,380 --> 00:15:15,760
Is é an luach seo chugainn mé ag dul a chuardach le haghaidh 10.

220
00:15:15,760 --> 00:15:23,230
Maith go leor. Mar sin, 10, anois, tá dul chun - ghearradh amach go - ag dul a leanúint ar an fhréamh.

221
00:15:23,230 --> 00:15:27,670
Anois, tá 10 ag dul a bheith níos mó ná 7, agus mar sin ba mhaith liom chun breathnú ar dheis.

222
00:15:27,670 --> 00:15:31,660
Tá mé ag dul chun teacht thar anseo, tá 10 ag dul a bheith níos mó ná 9,

223
00:15:31,660 --> 00:15:34,520
mar sin tá mé ag dul go dtí mhaith chun breathnú ar dheis.

224
00:15:34,520 --> 00:15:42,100
Tagaim thar anseo, ach thar anseo anois tá mé ag null.

225
00:15:42,100 --> 00:15:44,170
Cad a dhéanfaidh mé má bhuail mé null?

226
00:15:44,170 --> 00:15:47,440
[Mac Léinn] ais bréagach? >> Yeah. Ní raibh mé a fháil 10.

227
00:15:47,440 --> 00:15:49,800
1 ag dul a bheith cás beagnach mar an gcéanna,

228
00:15:49,800 --> 00:15:51,950
ach tá sé ag dul ach a bheith iompaithe; seachas ag lorg

229
00:15:51,950 --> 00:15:56,540
síos ar an taobh deas, tá mé ag dul chun breathnú síos ar an taobh clé.

230
00:15:56,540 --> 00:16:00,430
>> Anois liom go bhfuil linn a fháil iarbhír a cód.

231
00:16:00,430 --> 00:16:04,070
Seo an áit - oscailt suas an fearas CS50 agus do bhealach nascleanúint a dhéanamh ann,

232
00:16:04,070 --> 00:16:07,010
ach is féidir go díreach leat a dhéanamh freisin sé sa spás.

233
00:16:07,010 --> 00:16:09,170
Is dócha is fearr chun é a dhéanamh sa spás,

234
00:16:09,170 --> 00:16:13,760
mar is féidir linn oibriú sa spás.

235
00:16:13,760 --> 00:16:19,170
"An Chéad beidh orainn a dhíth sainmhíniú cineál nua le haghaidh nód crann dénártha ina bhfuil luachanna slánuimhir.

236
00:16:19,170 --> 00:16:21,400
Ag baint úsáide as an boilerplate Rialú an thíos,

237
00:16:21,400 --> 00:16:24,510
a chruthú sainmhíniú cineál nua le haghaidh nód i gcrann dénártha.

238
00:16:24,510 --> 00:16:27,930
Má tá tú i bhfostú. . . "Blah, blah, blah. Maith go leor.

239
00:16:27,930 --> 00:16:30,380
Mar sin a ligean a chur ar an boilerplate anseo,

240
00:16:30,380 --> 00:16:41,630
nód struct Rialú an, agus nód. Yeah, maith go leor.

241
00:16:41,630 --> 00:16:44,270
Mar sin, cad iad na réimsí táimid ag dul a iarraidh i ár nód?

242
00:16:44,270 --> 00:16:46,520
[Mac Léinn] Int agus ansin dhá threo?

243
00:16:46,520 --> 00:16:49,700
>> Int luach, dhá threo? Conas is féidir liom scríobh na leideanna?

244
00:16:49,700 --> 00:16:58,440
[Mac Léinn] struct. >> Ba chóir dom a súmáil isteach Yeah, mar sin struct nód * chlé,

245
00:16:58,440 --> 00:17:01,320
agus struct nód * ceart.

246
00:17:01,320 --> 00:17:03,460
Agus cuimhnigh ar an bplé ó am seo caite,

247
00:17:03,460 --> 00:17:15,290
a dhéanann an aon chiall, a dhéanann an aon chiall,

248
00:17:15,290 --> 00:17:18,270
seo a dhéanann aon chiall.

249
00:17:18,270 --> 00:17:25,000
Ní mór duit gach rud ann chun sainmhíniú seo a struct athchúrsach.

250
00:17:25,000 --> 00:17:27,970
Maith go leor, ionas go mbeidh ar cad ár crann ag dul chun breathnú cosúil.

251
00:17:27,970 --> 00:17:37,670
Má rinne muid crann trinary, ansin d'fhéadfadh nód cuma mhaith b2 b1,, struct nód * b3,

252
00:17:37,670 --> 00:17:43,470
áit a bhfuil b, chun craobh - i ndáiríre, tá mé níos mó chuala fhág sé,, lár ceart, ach is cuma cad.

253
00:17:43,470 --> 00:17:55,610
Táimid cúram ach thart ar dénártha, agus mar sin ceart, ar chlé.

254
00:17:55,610 --> 00:17:59,110
"Dearbhaíonn Anois athróg * domhanda nód chun an fhréamh an crann."

255
00:17:59,110 --> 00:18:01,510
Mar sin, ní táimid ag dul a dhéanamh sin.

256
00:18:01,510 --> 00:18:08,950
D'fhonn a dhéanamh rudaí a beagán níos deacra agus níos ginearálta,

257
00:18:08,950 --> 00:18:11,570
ní bheidh againn athróg nód domhanda.

258
00:18:11,570 --> 00:18:16,710
Ina áit sin, i mó beimid go léir a dhearbhú ár rudaí nód,

259
00:18:16,710 --> 00:18:20,500
agus ciallaíonn sé sin go thíos, nuair a thosaíonn muid ag rith

260
00:18:20,500 --> 00:18:23,130
ár n-Tá feidhm agus ár bhfeidhm isteach,

261
00:18:23,130 --> 00:18:27,410
in ionad ár Tá feidhm ag baint úsáide as ach an athróg nód domhanda,

262
00:18:27,410 --> 00:18:34,280
táimid ag dul a bheith acu é a ghlacadh mar argóint an crann sin ba mhaith linn é a phróiseáil.

263
00:18:34,280 --> 00:18:36,650
Bhí ceaptha Ag an athróg domhanda chun rudaí a dhéanamh níos éasca.

264
00:18:36,650 --> 00:18:42,310
Táimid ag dul chun rudaí a dhéanamh níos deacra.

265
00:18:42,310 --> 00:18:51,210
Anois a ghlacadh nóiméad nó mar sin go díreach é seo a dhéanamh saghas rud,

266
00:18:51,210 --> 00:18:57,690
nuair taobh istigh de phríomh mian leat a chruthú an crann, agus sin uile mian leat a dhéanamh.

267
00:18:57,690 --> 00:19:04,530
Bain triail as agus an crann a thógáil i do fheidhm is mó.

268
00:19:42,760 --> 00:19:47,610
>> Maith go leor. Mar sin ní gá duit fiú a bheith tógtha ar an crann ar an mbealach ar fad go fóill.

269
00:19:47,610 --> 00:19:49,840
Ach tá duine ar bith rud éigin a raibh mé in ann a tharraingt suas

270
00:19:49,840 --> 00:20:03,130
chun a thaispeáint conas a d'fhéadfadh ceann amháin tús a thógáil den sórt sin ag crann?

271
00:20:03,130 --> 00:20:08,080
[Mac Léinn] D'iarr duine éigin ar banging, ag iarraidh a fháil amach.

272
00:20:08,080 --> 00:20:13,100
[Bowden] Duine ar bith compordach lena n-tógáil crann?

273
00:20:13,100 --> 00:20:15,520
[Mac Léinn] Cinnte. Nach bhfuil sé déanta. >> Tá sé go breá. Is féidir linn a chríochnú díreach -

274
00:20:15,520 --> 00:20:26,860
OH, an féidir leat é a shábháil? Hooray.

275
00:20:26,860 --> 00:20:32,020
Mar sin anseo tá muid - OH, tá mé ghearradh beagán de thalamh.

276
00:20:32,020 --> 00:20:34,770
Am súmáilte mé i?

277
00:20:34,770 --> 00:20:37,730
Zúmáil isteach, scrollbharra amach. >> Tá mé ceist. >> Yeah?

278
00:20:37,730 --> 00:20:44,410
[Mac Léinn] Nuair a bheidh tú a shainiú struct, tá rudaí cosúil le initialized rud ar bith?

279
00:20:44,410 --> 00:20:47,160
[Bowden] Uimh >> Maith go leor. Mar sin, bheadh ​​agat a thúsú -

280
00:20:47,160 --> 00:20:50,450
[Bowden] Uimh Nuair a bheidh tú a shainiú, nó nuair a dhéanann tú a fhógairt struct,

281
00:20:50,450 --> 00:20:55,600
nach bhfuil sé initialized de réir réamhshocraithe; tá sé díreach cosúil má tá tú a dhearbhú ina slánuimhir.

282
00:20:55,600 --> 00:20:59,020
Tá sé díreach an rud céanna. Tá sé cosúil le gach ceann dá réimsí ar leith

283
00:20:59,020 --> 00:21:04,460
Is féidir a bhfuil luach truflais ann. >> Agus is féidir a shainmhíniú - nó a dhearbhú struct

284
00:21:04,460 --> 00:21:07,740
ar bhealach a dhéanann sé thúsú iad?

285
00:21:07,740 --> 00:21:13,200
[Bowden] Tá. Mar sin, comhréir initialization aicearra

286
00:21:13,200 --> 00:21:18,660
ag dul chun breathnú cosúil le -

287
00:21:18,660 --> 00:21:22,200
Níl dhá bhealach is féidir linn é seo a. I mo thuairimse, ba chóir dúinn a chur le chéile é

288
00:21:22,200 --> 00:21:25,840
a dhéanamh cinnte go ndéanann clang seo chomh maith.

289
00:21:25,840 --> 00:21:28,510
An t-ord na n-argóintí a thagann ar an struct,

290
00:21:28,510 --> 00:21:32,170
chuir tú an t-ordú de na hargóintí taobh istigh de na braces gcuach.

291
00:21:32,170 --> 00:21:35,690
Mar sin, más mian leat é a thúsú go 9 agus d'fhág sé a bheith ar neamhní agus ansin a bheith ceart faoin margadh saothair,

292
00:21:35,690 --> 00:21:41,570
go mbeadh sé 9, Eolas faoin margadh saothair, null.

293
00:21:41,570 --> 00:21:47,890
Is é an rogha, agus nach bhfuil an eagarthóir mar seo error,

294
00:21:47,890 --> 00:21:50,300
agus a ba mhaith liom a bloc nua,

295
00:21:50,300 --> 00:22:01,800
ach tá an rogha rud éigin cosúil le -

296
00:22:01,800 --> 00:22:04,190
anseo, beidh mé é a chur ar líne nua.

297
00:22:04,190 --> 00:22:09,140
Is féidir leat a rá go sainráite, déan dearmad mé an chomhréir cruinn.

298
00:22:09,140 --> 00:22:13,110
Mar sin, is féidir leat aghaidh a thabhairt ar go sainráite iad de réir ainm, agus a rá,

299
00:22:13,110 --> 00:22:21,570
. C, nó. Luach = 9,. Chlé = NULLComment.

300
00:22:21,570 --> 00:22:24,540
Tá mé ag guessing an gcaithfear iad a camóga.

301
00:22:24,540 --> 00:22:29,110
. Ceart = NULLComment, agus mar sin ar an mbealach seo nach bhfuil tú

302
00:22:29,110 --> 00:22:33,780
iarbhír a fhios an t-ordú an struct,

303
00:22:33,780 --> 00:22:36,650
agus nuair a bhíonn tú ag léamh seo, tá sé i bhfad níos soiléire

304
00:22:36,650 --> 00:22:41,920
faoi ​​cad atá ar an luach a bheith initialized go.

305
00:22:41,920 --> 00:22:44,080
>> A tharlaíonn sé seo a bheith ar cheann de na rudaí a -

306
00:22:44,080 --> 00:22:49,100
mar sin, den chuid is mó, C + + Is le superset de C.

307
00:22:49,100 --> 00:22:54,160
Is féidir leat C cód, é a bhogadh ar aghaidh go dtí C + +, agus ba chóir é a thiomsú.

308
00:22:54,160 --> 00:22:59,570
Tá sé seo ar cheann de na rudaí a C + + Ní thacaíonn, mar sin daoine claonadh ní a dhéanamh.

309
00:22:59,570 --> 00:23:01,850
Níl a fhios agam más rud é go an chúis amháin daoine claonadh gan é a dhéanamh,

310
00:23:01,850 --> 00:23:10,540
ach is gá an cás nuair is gá dom a úsáid a bheith ag obair le C + + agus mar sin ní raibh mé in ann seo a úsáid.

311
00:23:10,540 --> 00:23:14,000
Ní Sampla eile de rud éigin go n-oibríonn le C + + Is

312
00:23:14,000 --> 00:23:16,940
conas ar ais malloc a "* neamhní," go teicniúil,

313
00:23:16,940 --> 00:23:20,200
ach d'fhéadfaí tú a rá ach ruabhric * x cibé malloc =,

314
00:23:20,200 --> 00:23:22,840
agus déanfar é a chaitheamh go huathoibríoch * Char.

315
00:23:22,840 --> 00:23:25,450
Ní sin a caitheadh ​​uathoibríoch tarlú i C + +.

316
00:23:25,450 --> 00:23:28,150
Ní bheadh ​​sin a thiomsú, agus bheadh ​​de dhíth ort go sainráite a rá

317
00:23:28,150 --> 00:23:34,510
* ruabhreac, malloc, is cuma cad, chun é a chaitheamh le * Char.

318
00:23:34,510 --> 00:23:37,270
Ní Tá a lán rudaí go C agus C + + n-aontaíonn ar,

319
00:23:37,270 --> 00:23:40,620
ach tá an dá.

320
00:23:40,620 --> 00:23:43,120
Mar sin, beidh muid ag dul leis an chomhréir.

321
00:23:43,120 --> 00:23:46,150
Ach fiú amháin más rud é nach raibh muid ag dul leis an error,

322
00:23:46,150 --> 00:23:49,470
cad é - d'fhéadfadh a bheith mícheart leis seo?

323
00:23:49,470 --> 00:23:52,170
[Mac Léinn] Ní féidir liom gá téigh i sé? >> Yeah.

324
00:23:52,170 --> 00:23:55,110
Cuimhnigh go bhfuil an arrow le téigh i intuigthe,

325
00:23:55,110 --> 00:23:58,230
agus mar sin nuair a bhíonn muid ag déileáil go díreach le struct,

326
00:23:58,230 --> 00:24:04,300
ba mhaith linn a úsáid. a fháil ag taobh istigh réimse an struct.

327
00:24:04,300 --> 00:24:07,200
Agus is é an t-am amháin a úsáid againn arrow nuair is mian linn a dhéanamh -

328
00:24:07,200 --> 00:24:13,450
go maith, tá arrow ar comhbhrí le -

329
00:24:13,450 --> 00:24:17,020
sin an méid a mbeadh sé i gceist má úsáidtear mé arrow.

330
00:24:17,020 --> 00:24:24,600
Tá gach modh arrow, téigh i seo, anois tá mé ag struct, agus is féidir liom a fháil ar an réimse.

331
00:24:24,600 --> 00:24:28,040
Ceachtar a fháil ar an réimse go díreach nó téigh i agus an réimse a fháil -

332
00:24:28,040 --> 00:24:30,380
Buille faoi thuairim mé ba chóir é seo a bheith luach.

333
00:24:30,380 --> 00:24:33,910
Ach anseo tá mé ag déileáil le díreach struct a ní, a pointeoir a struct,

334
00:24:33,910 --> 00:24:38,780
agus mar sin ní féidir liom a bhaint as an arrow.

335
00:24:38,780 --> 00:24:47,510
Ach an saghas rud is féidir linn a dhéanamh do gach nód.

336
00:24:47,510 --> 00:24:55,790
Oh mo Dhia.

337
00:24:55,790 --> 00:25:09,540
Is é seo an 6, 7, agus 3.

338
00:25:09,540 --> 00:25:16,470
Ansin is féidir linn a chur ar bun na craobhacha i ár crann, is féidir linn a bheith 7 -

339
00:25:16,470 --> 00:25:21,650
is féidir linn a bheith, a d'fhág Ba chóir go pointe 3.

340
00:25:21,650 --> 00:25:25,130
Mar sin, conas is féidir linn a dhéanamh?

341
00:25:25,130 --> 00:25:29,320
[Mic léinn, dothuigthe] >> Yeah. An seoladh node3,

342
00:25:29,320 --> 00:25:34,170
agus más rud é nach raibh tú seoladh, ansin ní bheadh ​​thiomsú díreach.

343
00:25:34,170 --> 00:25:38,190
Ach cuimhnigh go bhfuil na leideanna do na nóid eile.

344
00:25:38,190 --> 00:25:44,930
Ba chóir an ceart pointe 9,

345
00:25:44,930 --> 00:25:53,330
agus ba chóir 3 pointe maidir leis an gceart go 6.

346
00:25:53,330 --> 00:25:58,480
Ceapaim go bhfuil leagtha go léir. Aon tuairimí nó ceisteanna?

347
00:25:58,480 --> 00:26:02,060
[Mac Léinn, dothuigthe] Is é an fhréamh ag dul a bheith 7.

348
00:26:02,060 --> 00:26:08,210
Is féidir linn a rá ach nód * PTR =

349
00:26:08,210 --> 00:26:14,160
nó fhréamh, = & node7.

350
00:26:14,160 --> 00:26:20,730
>> Chun ár gcríoch sin, táimid ag dul a bheith ag déileáil le cuir isteach,

351
00:26:20,730 --> 00:26:25,490
mar sin táimid ag dul a iarraidh a scríobh feidhm a chur isteach i an crann dhénártha

352
00:26:25,490 --> 00:26:34,230
agus tá sé ag dul isteach dosheachanta malloc chun glaoch a chruthú nód nua don chrann.

353
00:26:34,230 --> 00:26:36,590
Mar sin, go bhfuil rudaí ag dul a fháil bréan leis an bhfíric go bhfuil roinnt nóid

354
00:26:36,590 --> 00:26:38,590
Faoi láthair tá ar an chruach

355
00:26:38,590 --> 00:26:43,680
agus nóid eile ag dul chun deireadh suas ar an gcarn nuair a chur isteach orthu.

356
00:26:43,680 --> 00:26:47,640
Tá sé seo go foirfe bailí, ach an chúis amháin

357
00:26:47,640 --> 00:26:49,600
tá muid in ann é seo a dhéanamh ar an chruach

358
00:26:49,600 --> 00:26:51,840
Is é mar tá sé den sórt sin mar shampla bréige go bhfuil a fhios againn

359
00:26:51,840 --> 00:26:56,360
Tá an crann ceaptha le bheith tógtha mar 7, 3, 6, 9.

360
00:26:56,360 --> 00:27:02,970
Más rud é nach raibh againn seo, ansin ní ba mhaith linn a malloc sa chéad áit.

361
00:27:02,970 --> 00:27:06,160
Mar beidh orainn a fheiceáil le beagán níos déanaí, ba chóir dúinn a bheith malloc'ing.

362
00:27:06,160 --> 00:27:08,570
Ceart anois tá sé breá réasúnta a chur ar an chruach,

363
00:27:08,570 --> 00:27:14,750
ach ligean ar seo a athrú a chur chun feidhme malloc.

364
00:27:14,750 --> 00:27:17,160
Dá bhrí sin tá gach ceann de na ag dul anois a bheith rud éigin cosúil le

365
00:27:17,160 --> 00:27:24,240
nód * node9 = malloc (deachúlach (nód)).

366
00:27:24,240 --> 00:27:28,040
Agus anois tá muid ag dul a bheith a dhéanamh ar ár sheiceáil.

367
00:27:28,040 --> 00:27:34,010
más rud é (node9 == NULLComment) - ní raibh mé ag iarraidh go -

368
00:27:34,010 --> 00:27:40,950
ar ais 1, agus ansin is féidir a dhéanamh node9-> againn mar anois tá sé ina pointeoir,

369
00:27:40,950 --> 00:27:45,300
luach = 6, node9-> fhág = NULLComment,

370
00:27:45,300 --> 00:27:48,930
node9-> ceart = NULLComment,

371
00:27:48,930 --> 00:27:51,410
agus táimid ag dul a bheith acu sin a dhéanamh do gach ceann de na nóid.

372
00:27:51,410 --> 00:27:57,490
Mar sin, ina ionad sin, a ligean ar é a chur taobh istigh de feidhm ar leith.

373
00:27:57,490 --> 00:28:00,620
A ligean ar ghlaoch air nód * build_node,

374
00:28:00,620 --> 00:28:09,050
agus tá sé seo beagán cosúil leis an APIs a chuirimid ar fáil le haghaidh Huffman códú.

375
00:28:09,050 --> 00:28:12,730
Thabhairt leat, feidhmeanna túsaitheoirí le haghaidh crann

376
00:28:12,730 --> 00:28:20,520
agus deconstructor "feidhmeanna" do na crainn agus an céanna d'fhoraoisí.

377
00:28:20,520 --> 00:28:22,570
>> Mar sin anseo táimid ag dul go bhfuil feidhm túsaitheoirí

378
00:28:22,570 --> 00:28:25,170
go dtí díreach a thógáil nód dúinn.

379
00:28:25,170 --> 00:28:29,320
Agus tá sé ag dul chun breathnú go leor i bhfad díreach mar seo.

380
00:28:29,320 --> 00:28:32,230
Agus tá mé ag dul fiú a bheith leisciúil agus ní athrú ar ainm an athróg,

381
00:28:32,230 --> 00:28:34,380
cé a dhéanann node9 aon chiall níos mó.

382
00:28:34,380 --> 00:28:38,610
Ó, buille faoi thuairim mé luach node9 ar chóir a bheith 6.

383
00:28:38,610 --> 00:28:42,800
Anois is féidir linn ar ais node9.

384
00:28:42,800 --> 00:28:49,550
Agus anseo ba chóir dúinn ar ais null.

385
00:28:49,550 --> 00:28:52,690
Tá ag gach duine ar chomhaontú maidir feidhme sin a thógáil-a-nód?

386
00:28:52,690 --> 00:28:59,780
Mar sin, anois is féidir linn glaoch go díreach a thógáil ar aon nód le luach áirithe agus leideanna faoin margadh saothair.

387
00:28:59,780 --> 00:29:09,750
Anois is féidir linn glaoch sin, is féidir linn a dhéanamh nód * node9 = build_node (9).

388
00:29:09,750 --> 00:29:25,810
Agus a ligean ar a dhéanamh. . .

389
00:29:25,810 --> 00:29:33,980
6, 3, 7, 6, 3, 7.

390
00:29:33,980 --> 00:29:39,330
Agus anois ba mhaith linn a chur ar bun na leideanna céanna,

391
00:29:39,330 --> 00:29:42,470
ach amháin anois tá gach rud cheana i dtaca le leideanna

392
00:29:42,470 --> 00:29:48,480
mar sin a thuilleadh gá an seoladh.

393
00:29:48,480 --> 00:29:56,300
Maith go leor. Mar sin, cad é an rud deireanach Ba mhaith liom a dhéanamh?

394
00:29:56,300 --> 00:30:03,850
Níl earráid-seiceáil nach bhfuil mé ag déanamh.

395
00:30:03,850 --> 00:30:06,800
Cad a dhéanann a thógáil ar ais nód?

396
00:30:06,800 --> 00:30:11,660
[Mac Léinn, dothuigthe] >> Yeah. Má theip ar malloc, beidh sé ar ais null.

397
00:30:11,660 --> 00:30:16,460
Mar sin, tá mé ag dul a chur lazily sé síos anseo in ionad a dhéanamh mar choinníoll le haghaidh gach.

398
00:30:16,460 --> 00:30:22,320
Más rud é (node9 == NULLComment, nó - fiú níos simplí,

399
00:30:22,320 --> 00:30:28,020
tá sé seo comhionann le díreach más rud é nach node9.

400
00:30:28,020 --> 00:30:38,310
Mar sin, más rud é nach node9, nó nach node6, nó nach node3, nó nach bhfuil node7, ar ais 1.

401
00:30:38,310 --> 00:30:42,850
B'fhéidir gur chóir dúinn a phriontáil malloc theip, nó rud éigin.

402
00:30:42,850 --> 00:30:46,680
[Mac Léinn] An bhfuil bréagach cothrom le nialasach chomh maith?

403
00:30:46,680 --> 00:30:51,290
[Bowden] Tá aon luach náid bréagach.

404
00:30:51,290 --> 00:30:53,920
Dá bhrí sin tá null luach nialas.

405
00:30:53,920 --> 00:30:56,780
Is Zero luach nialas. Is Bréagach luach nialas.

406
00:30:56,780 --> 00:31:02,130
Aon - go leor i bhfad an 2 ach na luachanna atá náid faoin margadh saothair agus nialas,

407
00:31:02,130 --> 00:31:07,900
bréagach ach hais mar a shainmhínítear nialas.

408
00:31:07,900 --> 00:31:13,030
Baineann sé freisin má dhéanann muid dhearbhú athraitheach domhanda.

409
00:31:13,030 --> 00:31:17,890
Má rinne muid go bhfuil fréamh * nód suas anseo,

410
00:31:17,890 --> 00:31:24,150
ansin - is é an rud deas faoi athróga domhanda go bhfuil siad i gcónaí ag luach tosaigh.

411
00:31:24,150 --> 00:31:27,500
Ní Sin fíor feidhmeanna, conas taobh istigh de anseo,

412
00:31:27,500 --> 00:31:34,870
má tá muid, ar nós, * nód nó x nód.

413
00:31:34,870 --> 00:31:37,380
Tá aon smaoineamh cad x.value, x.whatever,

414
00:31:37,380 --> 00:31:40,700
nó d'fhéadfadh muid a phriontáil agus d'fhéadfadh siad a bheith treallach.

415
00:31:40,700 --> 00:31:44,980
Ní Sin fíor na n-athróg domhanda.

416
00:31:44,980 --> 00:31:47,450
Fréimhe Mar sin nód nó x nód.

417
00:31:47,450 --> 00:31:53,410
De réir réamhshocraithe, gach rud go domhanda, más rud é nach initialized go sainráite le roinnt luach,

418
00:31:53,410 --> 00:31:57,390
Tá luach nialais mar a luach.

419
00:31:57,390 --> 00:32:01,150
Mar sin anseo, fréamh * nód, ní féidir linn a thúsú go sainráite é a rud ar bith,

420
00:32:01,150 --> 00:32:06,350
a fhágann go mbeidh a luach réamhshocraithe a bheith faoin margadh saothair, arb é an luach nialas leideanna.

421
00:32:06,350 --> 00:32:11,870
Is é an luach réamhshocraithe x ag dul a chiallaíonn go bhfuil x.value náid,

422
00:32:11,870 --> 00:32:14,260
x.left Is faoin margadh saothair, agus x.right tá margadh saothair.

423
00:32:14,260 --> 00:32:21,070
Mar sin, ós rud é go bhfuil sé struct, beidh gach ceann de na réimsí an struct luachanna nialais.

424
00:32:21,070 --> 00:32:24,410
Ní gá dúinn a úsáid go anseo, cé.

425
00:32:24,410 --> 00:32:27,320
Tá [Mac Léinn] An structs éagsúla ná athróga eile, agus na hathróga eile

426
00:32:27,320 --> 00:32:31,400
luachanna truflais; is iad seo nialais?

427
00:32:31,400 --> 00:32:36,220
[Bowden] luachanna eile freisin. Mar sin, i x, beidh x nialas.

428
00:32:36,220 --> 00:32:40,070
Má tá sé ar raon domhanda, tá sé luach tosaigh. >> Maith go leor.

429
00:32:40,070 --> 00:32:48,950
[Bowden] Is féidir leis an luach tosaigh thug tú é nó nialas.

430
00:32:48,950 --> 00:32:53,260
Sílim go Bíonn cúram de gach ceann de seo.

431
00:32:53,260 --> 00:32:58,390
>> Maith go leor. Mar sin, iarrann an chuid eile den cheist,

432
00:32:58,390 --> 00:33:01,260
"Anois, ba mhaith linn a scríobh le feidhm a dtugtar Tá

433
00:33:01,260 --> 00:33:04,930
le fréamhshamhail bool Tá luach slánuimhir. "

434
00:33:04,930 --> 00:33:08,340
Nach bhfuil muid ag dul a dhéanamh bool Tá luach slánuimhir.

435
00:33:08,340 --> 00:33:15,110
Is é ár fhréamhshamhail dul chun breathnú cosúil le

436
00:33:15,110 --> 00:33:22,380
bool Tá (luach slánuimhir.

437
00:33:22,380 --> 00:33:24,490
Agus ansin táimid ag dul freisin chun pas a fháil sé an crann

438
00:33:24,490 --> 00:33:28,870
gur chóir é a sheiceáil a fheiceáil má tá sé an luach sin.

439
00:33:28,870 --> 00:33:38,290
Mar sin, nód * crann). Maith go leor.

440
00:33:38,290 --> 00:33:44,440
Agus ansin is féidir linn a ghlaoch air le rud éigin cosúil le,

441
00:33:44,440 --> 00:33:46,090
b'fhéidir go mbainfidh muid ag iarraidh a printf nó rud éigin.

442
00:33:46,090 --> 00:33:51,040
Tá 6, ár root.

443
00:33:51,040 --> 00:33:54,300
Ba chóir don ais amháin, nó fíor,

444
00:33:54,300 --> 00:33:59,390
cé go bhfuil Ba chóir go 5 fréimhe ar ais bréagach.

445
00:33:59,390 --> 00:34:02,690
Mar sin a ghlacadh an dara a chur i bhfeidhm.

446
00:34:02,690 --> 00:34:06,780
Is féidir leat é a dhéanamh go iteratively nó go hathchúrsach.

447
00:34:06,780 --> 00:34:09,739
Is é an rud deas mar gheall ar an mbealach atá againn rudaí a chur ar bun go

448
00:34:09,739 --> 00:34:12,300
lends sé é féin chun ár réiteach athchúrsach i bhfad níos éasca

449
00:34:12,300 --> 00:34:14,719
ná mar a bhí ar an mbealach domhanda-athraitheach.

450
00:34:14,719 --> 00:34:19,750
Toisc go bhfuil má tá muid ach luach slánuimhir, ansin ní mór dúinn aon bhealach recursing síos subtrees.

451
00:34:19,750 --> 00:34:24,130
Ba mhaith linn go mbeadh feidhm cúntóir ar leithligh a recurses síos an subtrees dúinn.

452
00:34:24,130 --> 00:34:29,610
Ach ós rud é tá muid athraigh sé a chur ar an crann mar argóint,

453
00:34:29,610 --> 00:34:32,760
rud ba chóir a bheith i gcónaí sa chéad áit,

454
00:34:32,760 --> 00:34:35,710
anois is féidir linn recurse níos éasca.

455
00:34:35,710 --> 00:34:38,960
Mar sin, atriallach nó recursive, beidh muid ag dul thar an dá cheann,

456
00:34:38,960 --> 00:34:46,139
ach beidh orainn a fheiceáil go bhfuil deireadh athchúrsach a bheith suas éasca go leor.

457
00:34:59,140 --> 00:35:02,480
Maith go leor. An bhfuil aon duine rud éigin is féidir linn obair le?

458
00:35:02,480 --> 00:35:12,000
>> [Mac Léinn] fuair mé atriallach réiteach. >> Ceart go leor, atriallach.

459
00:35:12,000 --> 00:35:16,030
Maith go leor, Breathnaíonn an dea-.

460
00:35:16,030 --> 00:35:18,920
Mar sin, ba mhaith chun siúl dúinn tríd?

461
00:35:18,920 --> 00:35:25,780
[Mac Léinn] Cinnte. Mar sin, leag mé athróg teocht a fháil ar an nód chéad chrann.

462
00:35:25,780 --> 00:35:28,330
Agus ansin lúbtha mé díreach tar éis trí cé nach bhfuil teocht null cothrom,

463
00:35:28,330 --> 00:35:31,700
mar sin nuair a bhí fós sa crann, buille faoi thuairim mé.

464
00:35:31,700 --> 00:35:35,710
Agus má tá an luach is comhionann leis an luach go bhfuil teocht atá dírithe,

465
00:35:35,710 --> 00:35:37,640
ansin ar ais go luach.

466
00:35:37,640 --> 00:35:40,210
Seachas sin, seiceálann sé má tá sé ar an taobh dheis nó ar an taobh clé.

467
00:35:40,210 --> 00:35:43,400
Má tá tú riamh a fháil staid ina níl aon crann níos mó,

468
00:35:43,400 --> 00:35:47,330
ansin ar ais é - bealach amach sé an lúb agus tuairisceáin bréagach.

469
00:35:47,330 --> 00:35:52,190
[Bowden] Maith go leor. Mar sin, is cosúil go maith.

470
00:35:52,190 --> 00:35:58,470
Duine ar bith aon tuairimí ar rud ar bith?

471
00:35:58,470 --> 00:36:02,400
Tá mé aon tuairimí ceart ar chor ar bith.

472
00:36:02,400 --> 00:36:11,020
Is é an rud amháin is féidir linn é seo a Guy.

473
00:36:11,020 --> 00:36:21,660
Ó, tá sé ag dul chun dul ar longish beag.

474
00:36:21,660 --> 00:36:33,460
Feicfidh mé a shocrú go bhfuil suas. Maith go leor.

475
00:36:33,460 --> 00:36:37,150
>> Ba chóir gach duine cuimhneamh conas a oibríonn thrínártha.

476
00:36:37,150 --> 00:36:38,610
Tharla tráth na gceist curtha cinnte san am atá caite

477
00:36:38,610 --> 00:36:41,170
a thabhairt duit feidhm le hoibreoir trínártha,

478
00:36:41,170 --> 00:36:45,750
agus a rá, seo a aistriú, rud éigin a dhéanamh nach úsáideann thrínártha.

479
00:36:45,750 --> 00:36:49,140
Mar sin, tá sé seo le cás an-choitianta nuair ba mhaith liom a cheapann trínártha a úsáid,

480
00:36:49,140 --> 00:36:54,610
i gcás má chruthaíonn roinnt coinníoll athróg rud éigin,

481
00:36:54,610 --> 00:36:58,580
eile a leagtar go athróg céanna le rud éigin eile.

482
00:36:58,580 --> 00:37:03,390
Sin rud gur féidir go minic a chlaochlú an saghas rud

483
00:37:03,390 --> 00:37:14,420
inar leag an athróg seo - nó, go maith, tá sé seo fíor? Ansin seo, eile é seo.

484
00:37:14,420 --> 00:37:18,550
[Mac Léinn] Is é an chéad cheann más fíor, ceart?

485
00:37:18,550 --> 00:37:25,570
[Bowden] Yeah. Is é an bealach a léigh mé i gcónaí é, is ionann teocht luach níos mó ná luach sealadach,

486
00:37:25,570 --> 00:37:30,680
ansin é seo, eile é seo. Tá sé seo tú ceist.

487
00:37:30,680 --> 00:37:35,200
An bhfuil níos mó é? Ansin a dhéanamh ar an chéad rud. Eile a dhéanamh ar an dara rud.

488
00:37:35,200 --> 00:37:41,670
Mé beagnach i gcónaí - an colon, mé díreach tar éis - i mo cheann, léigh mé mar eile.

489
00:37:41,670 --> 00:37:47,180
>> An bhfuil aon duine a réiteach athchúrsach?

490
00:37:47,180 --> 00:37:49,670
Maith go leor. Sé seo ar cheann táimid ag dul a - d'fhéadfadh sé a bheith cheana féin go hiontach,

491
00:37:49,670 --> 00:37:53,990
ach táimid ag dul a dhéanamh níos fearr fiú.

492
00:37:53,990 --> 00:37:58,720
Tá sé seo i bhfad deas an smaoineamh céanna cruinn.

493
00:37:58,720 --> 00:38:03,060
Tá sé díreach, go maith, ar mhaith leat a mhíniú?

494
00:38:03,060 --> 00:38:08,340
[Mac Léinn] Cinnte. Mar sin, táimid ag déanamh cinnte nach bhfuil an crann nialasach ar dtús,

495
00:38:08,340 --> 00:38:13,380
mar má tá an crann null ansin tá sé ag dul a thabhairt ar ais bréagach toisc nach mór dúinn a fuair é.

496
00:38:13,380 --> 00:38:19,200
Agus má tá fós crann, táimid ag dul isteach - táimid seiceáil ar dtús má tá an luach an nód atá ann faoi láthair.

497
00:38:19,200 --> 00:38:23,740
Fill ar ais fíor má tá sé, agus más rud é nach recurse againn ar an taobh clé nó ceart.

498
00:38:23,740 --> 00:38:25,970
An bhfuil an fhuaim cuí? >> Mm-hmm. (Socrú)

499
00:38:25,970 --> 00:38:33,880
Mar sin, fógra go bhfuil sé seo beagnach - struchtúir den chineál céanna an-an réiteach atriallach.

500
00:38:33,880 --> 00:38:38,200
Tá sé sin go díreach in ionad recursing, bhí againn lúb tamaill.

501
00:38:38,200 --> 00:38:40,840
Agus an cás bonn anseo nuair nach crann null comhionann

502
00:38:40,840 --> 00:38:44,850
Bhí na coinníollacha faoinar bhris muid amach as an lúb tamaill.

503
00:38:44,850 --> 00:38:50,200
Tá siad an-chosúil. Ach táimid ag dul a dhéanfaidh an taisceadh sin amháin eile.

504
00:38:50,200 --> 00:38:54,190
Anois, a dhéanann muid an rud céanna anseo.

505
00:38:54,190 --> 00:38:57,680
Fógra táimid ag filleadh ar an rud céanna sa dá de na línte,

506
00:38:57,680 --> 00:39:00,220
ach amháin i gcás go bhfuil argóint amháin éagsúla.

507
00:39:00,220 --> 00:39:07,950
Mar sin, táimid ag dul a dhéanamh go isteach i thrínártha.

508
00:39:07,950 --> 00:39:13,790
Bhuail mé rud éigin rogha, agus rinne sé ina siombail. Maith go leor.

509
00:39:13,790 --> 00:39:21,720
Mar sin, táimid ag dul a thabhairt ar ais Tá go.

510
00:39:21,720 --> 00:39:28,030
Tá sé seo ag fáil a bheith ar línte éagsúla, go maith, súmáilte i go bhfuil sé.

511
00:39:28,030 --> 00:39:31,060
De ghnáth, mar rud stíle, ní dóigh liom go bhfuil go leor daoine

512
00:39:31,060 --> 00:39:38,640
a chur ar spás tar éis an arrow, ach buille faoi thuairim mé má tá tú ag teacht, tá sé fíneáil.

513
00:39:38,640 --> 00:39:44,320
Má tá luach níos lú ná luach crann, ba mhaith linn a recurse ar chlé crann,

514
00:39:44,320 --> 00:39:53,890
eile ba mhaith linn a recurse ar dheis crann.

515
00:39:53,890 --> 00:39:58,610
Mar sin, go raibh céim ar cheann de seo a dhéanamh cuma níos lú.

516
00:39:58,610 --> 00:40:02,660
Céim dhá cheann de seo a dhéanamh cuma níos lú -

517
00:40:02,660 --> 00:40:09,150
is féidir linn seo a scaradh le línte éagsúla.

518
00:40:09,150 --> 00:40:16,500
Maith go leor. Tá Céim dhá cheann de na a dhéanamh breathnú sé níos lú anseo,

519
00:40:16,500 --> 00:40:25,860
mar sin is ionann luach ar ais luach crann, nó ina bhfuil cibé.

520
00:40:25,860 --> 00:40:28,340
>> Is é seo an rud is tábhachtaí.

521
00:40:28,340 --> 00:40:30,860
Níl mé cinnte má dúirt sé go sainráite é sa rang,

522
00:40:30,860 --> 00:40:34,740
ach tá sé ar a dtugtar gearr-chuaird meastóireachta.

523
00:40:34,740 --> 00:40:41,060
Is é an smaoineamh anseo luach == luach crann.

524
00:40:41,060 --> 00:40:49,960
Más rud é go fíor, ansin tá sé seo fíor, agus ba mhaith linn 'nó' go bhfuil cuma cad é thar anseo.

525
00:40:49,960 --> 00:40:52,520
Mar sin, gan fiú smaoineamh ar is cuma cad é thar anseo,

526
00:40:52,520 --> 00:40:55,070
cad é an abairt ar fad ag dul ar ais?

527
00:40:55,070 --> 00:40:59,430
[Mac Léinn] Fíor? >> Yeah, mar gheall ar fíor aon ní,

528
00:40:59,430 --> 00:41:04,990
Is or'd nó fíor le rud ar bith gá fíor - or'd.

529
00:41:04,990 --> 00:41:08,150
Mar sin, a luaithe is mar a fheicimid luach ar ais luach crann =,

530
00:41:08,150 --> 00:41:10,140
táimid ag dul díreach a thabhairt ar ais fíor.

531
00:41:10,140 --> 00:41:15,710
Nach bhfuil ag dul fiú a recurse Tá tuilleadh síos ar an líne.

532
00:41:15,710 --> 00:41:20,980
Is féidir linn a dhéanfaidh an taisceadh sin amháin eile.

533
00:41:20,980 --> 00:41:29,490
Ní crann Tuairisceán null cothrom agus seo ar fad.

534
00:41:29,490 --> 00:41:32,650
Rinne sé é feidhm amháin-líne.

535
00:41:32,650 --> 00:41:36,790
Tá sé seo freisin, mar shampla de gearr-chuaird meastóireachta.

536
00:41:36,790 --> 00:41:40,680
Ach anois tá sé an smaoineamh céanna -

537
00:41:40,680 --> 00:41:47,320
in ionad - sin más crann nach faoin margadh saothair cothrom - nó, go maith,

538
00:41:47,320 --> 00:41:49,580
má dhéanann crann null cothrom, a bhfuil an cás olc,

539
00:41:49,580 --> 00:41:54,790
má bhíonn crann null, tá ansin an chéad choinníoll ag dul a bheith bréagach.

540
00:41:54,790 --> 00:42:00,550
Mar sin, bréagach anded le rud ar bith ag dul a bheith cad é?

541
00:42:00,550 --> 00:42:04,640
[Mac Léinn] Bréagach. >> Yeah. Is é seo an leath eile den gearr-chuaird meastóireachta,

542
00:42:04,640 --> 00:42:10,710
i gcás más rud é nach crann null nach ionann, ansin nach bhfuil muid ag dul chun dul fiú -

543
00:42:10,710 --> 00:42:14,930
nó má dhéanann crann null cothrom, ansin nach bhfuil muid ag dul a dhéanamh ar luach == luach crann.

544
00:42:14,930 --> 00:42:17,010
Táimid ag dul díreach a thabhairt ar ais láithreach bréagach.

545
00:42:17,010 --> 00:42:20,970
Rud atá tábhachtach, ós rud é más rud é nach raibh sé gearr-chuaird a mheas,

546
00:42:20,970 --> 00:42:25,860
ansin má dhéanann crann null cothrom, tá an dara coinníoll ag dul chun locht seg,

547
00:42:25,860 --> 00:42:32,510
toisc go bhfuil crann-> luach dereferencing null.

548
00:42:32,510 --> 00:42:40,490
Mar sin tá go sin. An féidir seo a dhéanamh - athrú aon uair amháin os a chionn.

549
00:42:40,490 --> 00:42:44,840
Is é seo an rud an-choitianta freisin, ní a dhéanamh ar an líne amháin leis seo,

550
00:42:44,840 --> 00:42:49,000
ach tá sé rud coitianta i coinníollacha nach bhfuil, b'fhéidir ar dheis anseo,

551
00:42:49,000 --> 00:42:59,380
ach más rud é (crann! = NULLComment, agus crann-> Luach == luach), cibé rud.

552
00:42:59,380 --> 00:43:01,560
Is é seo an riocht an-choitianta, i gcás ina ionad a bheith

553
00:43:01,560 --> 00:43:06,770
seo a bhriseadh ina dhá IFS, áit mhaith, is é an nialasach crann?

554
00:43:06,770 --> 00:43:11,780
Maith go leor, nach bhfuil sé nialasach, mar sin anois an luach crann cothrom le luach? Déan é seo.

555
00:43:11,780 --> 00:43:17,300
Ina áit sin, an coinníoll seo, ní bheidh an seg locht

556
00:43:17,300 --> 00:43:21,220
toisc go mbeidh sé briseadh amach má tharlaíonn sé seo a bheith ar neamhní.

557
00:43:21,220 --> 00:43:24,000
Bhuel, buille faoi thuairim mé má tá do crann pointeoir go hiomlán neamhbhailí, is féidir seg sé fós locht,

558
00:43:24,000 --> 00:43:26,620
ach ní féidir é a locht seg má tá crann null.

559
00:43:26,620 --> 00:43:32,900
Má bhí sé faoin margadh saothair, go mbeadh sé briseadh amach roimh dereferenced tú riamh ar an pointeoir sa chéad áit.

560
00:43:32,900 --> 00:43:35,000
[Mac Léinn] An bhfuil an mheastóireacht ar a dtugtar leisciúil?

561
00:43:35,000 --> 00:43:40,770
>> Is é [Bowden] meastóireacht leisciúil rud ar leith.

562
00:43:40,770 --> 00:43:49,880
Tá meastóireacht leisciúil níos mó cosúil le iarraidh ort le haghaidh luach,

563
00:43:49,880 --> 00:43:54,270
iarrann tú a ríomh ar luach, de chineál ar, ach ní gá duit é láithreach.

564
00:43:54,270 --> 00:43:59,040
Mar sin, go dtí go dhíth ort i ndáiríre é, nach bhfuil sé a mheas.

565
00:43:59,040 --> 00:44:03,920
Ní hé seo go díreach an rud céanna, ach sa pset Huffman,

566
00:44:03,920 --> 00:44:06,520
Deir sé go bhfuil muid "lazily" a scríobh.

567
00:44:06,520 --> 00:44:08,670
Is é an chúis a dhéanann muid go toisc go bhfuil muid ag buffering iarbhír an scríobh -

568
00:44:08,670 --> 00:44:11,820
nach bhfuil muid ag iarraidh a scríobh giotán aonair ag an am,

569
00:44:11,820 --> 00:44:15,450
nó bytes aonair ag an am, ba mhaith linn áit a fháil ar smután de bytes.

570
00:44:15,450 --> 00:44:19,270
Ansin, nuair atá againn le smután de bytes, ansin beidh orainn a scríobh sé amach.

571
00:44:19,270 --> 00:44:22,640
Cé iarrann tú é a scríobh - agus fwrite agus fread a dhéanamh ar an saghas céanna rud.

572
00:44:22,640 --> 00:44:26,260
Siad a mhaolánú do léann scríobhann agus.

573
00:44:26,260 --> 00:44:31,610
Cé tú ag iarraidh é a scríobh láithreach bonn, ní bheidh is dócha.

574
00:44:31,610 --> 00:44:34,540
Agus nach féidir leat a bheith cinnte go bhfuil rudaí ag dul a bheith scríofa

575
00:44:34,540 --> 00:44:37,540
go dtí go ghlaonn tú ar hfclose nó is cuma cad é,

576
00:44:37,540 --> 00:44:39,620
a deir ansin, ceart go leor, tá mé ag dúnadh mo chomhad,

577
00:44:39,620 --> 00:44:43,450
ciallaíonn sé gur mhaith liom a scríobh níos fearr gach rud nach bhfuil mé scríofa go fóill.

578
00:44:43,450 --> 00:44:45,770
Tá sé tar éis ní gá gach rud a scríobh amach

579
00:44:45,770 --> 00:44:49,010
go dtí go bhfuil tú ag dúnadh an comhad, agus ansin ní mór é a.

580
00:44:49,010 --> 00:44:56,220
Mar sin, tá go díreach cad leisciúil - Waits sé go dtí go bhfuil sé le tarlú.

581
00:44:56,220 --> 00:44:59,990
Seo - a ghlacadh 51 agus beidh tú dul isteach go mion níos mó,

582
00:44:59,990 --> 00:45:05,470
mar gheall ar OCaml agus gach rud i 51, tá gach rud athchúrsáil.

583
00:45:05,470 --> 00:45:08,890
Níl aon réiteach atriallach, go bunúsach.

584
00:45:08,890 --> 00:45:11,550
Tá gach rud athchúrsáil, agus meastóireacht leisciúil

585
00:45:11,550 --> 00:45:14,790
ag dul a bheith tábhachtach do a lán de na cúinsí

586
00:45:14,790 --> 00:45:19,920
más rud é, más rud é nach raibh tú a mheas lazily, a bheadh ​​i gceist -

587
00:45:19,920 --> 00:45:24,760
Is é an sampla sruthanna, atá mar cheann fada.

588
00:45:24,760 --> 00:45:30,990
Go teoiriciúil, is féidir leat smaoineamh ar na uimhreacha aiceanta mar shruth de 1-2-3-4-5-6-7,

589
00:45:30,990 --> 00:45:33,090
Tá rudaí sin lazily measúnú fíneáil.

590
00:45:33,090 --> 00:45:37,210
Má rá liom Ba mhaith liom an uimhir deichiú, ansin is féidir liom a mheas suas go dtí an uimhir deichiú.

591
00:45:37,210 --> 00:45:40,300
Más mian liom an uimhir céadú, ansin is féidir liom a mheas suas go dtí an uimhir céadú.

592
00:45:40,300 --> 00:45:46,290
Gan meastóireacht leisciúil, ansin tá sé ag dul chun iarracht a dhéanamh chun meastóireacht a dhéanamh ar gach líon láithreach.

593
00:45:46,290 --> 00:45:50,000
Tá tú ag mheas uimhreacha infinitely go leor, agus sin ní hamháin is féidir.

594
00:45:50,000 --> 00:45:52,080
Mar sin, tá a lán de na cúinsí ina meastóireacht leisciúil

595
00:45:52,080 --> 00:45:57,840
ach fíor-riachtanach chun rudaí a bheith ag obair.

596
00:45:57,840 --> 00:46:05,260
>> Anois, ba mhaith linn a scríobh isteach ina bhfuil isteach ag dul a bheith

597
00:46:05,260 --> 00:46:08,430
céanna atá ag athrú ina sainmhíniú.

598
00:46:08,430 --> 00:46:10,470
Mar sin, ceart anois tá sé isteach bool (luach slánuimhir).

599
00:46:10,470 --> 00:46:23,850
Táimid ag dul leis an athrú go dtí isteach bool (slánuimhir luach, nód * crann).

600
00:46:23,850 --> 00:46:29,120
Táimid ag dul i ndáiríre a athrú go arís i beagán, beidh orainn a fheiceáil cén fáth.

601
00:46:29,120 --> 00:46:32,210
Agus a ligean ar bogadh build_node, ach le haghaidh an heck de,

602
00:46:32,210 --> 00:46:36,730
thuas isteach mar sin nach bhfuil againn a scríobh fhréamhshamhail feidhm.

603
00:46:36,730 --> 00:46:42,450
Cé acu leid go bhfuil tú ag dul a bheith ag baint úsáide build_node i isteach.

604
00:46:42,450 --> 00:46:49,590
Maith go leor. Tóg nóiméad as sin.

605
00:46:49,590 --> 00:46:52,130
I mo thuairimse, shábháil mé an t-athbhreithniú más mian leat a tharraingt ó sin,

606
00:46:52,130 --> 00:47:00,240
nó, ar a laghad, rinne mé anois.

607
00:47:00,240 --> 00:47:04,190
Theastaigh uaim sos beag chun smaoineamh ar an loighic isteach,

608
00:47:04,190 --> 00:47:08,750
más rud é nach féidir leat smaoineamh ar é.

609
00:47:08,750 --> 00:47:12,860
Go bunúsach, beidh tú riamh ach a bheith isteach ag duilleoga.

610
00:47:12,860 --> 00:47:18,640
Cosúil le, más rud é isteach I 1, ansin tá mé ag dul dosheachanta a bheith isteach 1 -

611
00:47:18,640 --> 00:47:21,820
Beidh mé ag athrú go dubh - I'll a chur isteach 1 thar anseo.

612
00:47:21,820 --> 00:47:28,070
Nó má isteach mé 4, ba mhaith liom a bheith isteach i 4 thar anseo.

613
00:47:28,070 --> 00:47:32,180
Mar sin, is cuma cad a dhéanann tú, agus tú ag dul a bheith isteach ag duilleog.

614
00:47:32,180 --> 00:47:36,130
Gach bhfuil tú a dhéanamh ná iterate síos an crann go dtí go bhfaigheann tú an nód

615
00:47:36,130 --> 00:47:40,890
Ba chóir go mbeadh go bhfuil an nód tuismitheoir, an nód nua tuismitheoir,

616
00:47:40,890 --> 00:47:44,560
agus athrú ansin a pointeoir chlé nó ceart, ag brath ar cé acu

617
00:47:44,560 --> 00:47:47,060
tá sé níos mó ná nó níos lú ná an nód atá ann faoi láthair.

618
00:47:47,060 --> 00:47:51,180
Athraigh go pointeoir a chur in iúl le do nód nua.

619
00:47:51,180 --> 00:48:05,490
Mar sin, abair síos an crann, an pointe duille a dhéanamh leis an nód nua.

620
00:48:05,490 --> 00:48:09,810
Chomh maith leis sin smaoineamh ar cén fáth go bhfuil cosc ​​ar an gcineál staid roimh,

621
00:48:09,810 --> 00:48:17,990
nuair a tógadh mé an crann dhénártha áit a raibh sé ceart

622
00:48:17,990 --> 00:48:19,920
má bhreathnaíonn tú ach ag nód amháin,

623
00:48:19,920 --> 00:48:24,830
ach bhí 9 an taobh clé den 7 más rud é athluaigh tú síos go léir ar an mbealach.

624
00:48:24,830 --> 00:48:29,770
Mar sin, go bhfuil sé dodhéanta sa chás seo, ós rud é -

625
00:48:29,770 --> 00:48:32,530
smaoineamh isteach i thart ar 9 nó rud éigin; ag an nód an-an chéad,

626
00:48:32,530 --> 00:48:35,350
Tá mé ag dul a fheiceáil 7 agus tá mé ag dul go díreach chun dul go dtí an ceart.

627
00:48:35,350 --> 00:48:38,490
Mar sin, is cuma cad a dhéanann mé, má tá mé isteach ag dul go dtí duille,

628
00:48:38,490 --> 00:48:40,790
agus chun duille baint úsáide as an algartam is cuí,

629
00:48:40,790 --> 00:48:43,130
tá sé ag dul a bheith dodhéanta dom a 9 isteach ar an taobh clé de 7

630
00:48:43,130 --> 00:48:48,250
mar gheall ar chomh luath agus bhuail mé 7 Tá mé ag dul chun dul go dtí an ceart.

631
00:48:59,740 --> 00:49:02,070
An bhfuil aon duine rud éigin a tús a chur leis?

632
00:49:02,070 --> 00:49:05,480
[Mac Léinn] is féidir liom. >> Cinnte.

633
00:49:05,480 --> 00:49:09,200
[Mac Léinn, dothuigthe]

634
00:49:09,200 --> 00:49:14,390
[Mac léinn eile, dothuigthe]

635
00:49:14,390 --> 00:49:18,330
[Bowden] tá sé mhór. Maith go leor. Want a mhíniú?

636
00:49:18,330 --> 00:49:20,690
>> [Mac Léinn] Ós rud é a fhios againn go raibh muid ag chur isteach

637
00:49:20,690 --> 00:49:24,060
nóid nua ag deireadh an crann,

638
00:49:24,060 --> 00:49:28,070
Lúbtha mé tríd an crann iteratively

639
00:49:28,070 --> 00:49:31,360
go dtí go bhfuair mé le nód a chuir nialasach.

640
00:49:31,360 --> 00:49:34,220
Agus ansin shocraigh mé chun é a chur ceachtar ar an taobh dheis nó ar an taobh clé

641
00:49:34,220 --> 00:49:37,420
baint úsáide as an athróg ceart; inis sé dom nuair a chur air.

642
00:49:37,420 --> 00:49:41,850
Agus ansin, go bunúsach, rinne mé díreach tar éis go deireanach -

643
00:49:41,850 --> 00:49:47,520
an bpointe nód teocht leis an nód nua a bhí sé ag cruthú é,

644
00:49:47,520 --> 00:49:50,770
ceachtar ar an taobh clé nó ar an taobh deas, ag brath ar an méid a bhí an luach ceart.

645
00:49:50,770 --> 00:49:56,530
Ar deireadh, leag mé an luach nód nua an luach a thástáil.

646
00:49:56,530 --> 00:49:59,550
[Bowden] Maith go leor, mar sin liom a fheiceáil aon cheist anseo.

647
00:49:59,550 --> 00:50:02,050
Tá sé seo cosúil le 95% de ar an mbealach ann.

648
00:50:02,050 --> 00:50:07,550
An cheist amháin go bhfeiceann, go maith, a dhéanann duine ar bith eile a fheiceáil i gceist?

649
00:50:07,550 --> 00:50:18,400
Cad é an imthoisc faoina bhriseadh siad amach as an lúb?

650
00:50:18,400 --> 00:50:22,100
[Mac Léinn] Má tá teocht null? >> Yeah. Mar sin é an chaoi a bhriseann tú amach as an lúb má tá teocht nialasach.

651
00:50:22,100 --> 00:50:30,220
Ach cad a dhéanfaidh mé ar dheis anseo?

652
00:50:30,220 --> 00:50:35,410
Teocht téigh I, ina bhfuil dosheachanta faoin margadh saothair.

653
00:50:35,410 --> 00:50:39,840
Mar sin, nach bhfuil an rud eile is gá duit a dhéanamh ach súil a choinneáil go dtí go bhfuil teocht nialasach,

654
00:50:39,840 --> 00:50:45,590
ba mhaith leat súil a choinneáil ar an tuismitheoir i gcónaí.

655
00:50:45,590 --> 00:50:52,190
Ba mhaith linn freisin tuismitheoir * nód, buille faoi thuairim mé féidir linn a choinneáil go bhfuil ag null ar dtús.

656
00:50:52,190 --> 00:50:55,480
Tá sé seo ag dul go bhfuil iompar aisteach ar an fhréamh an crann,

657
00:50:55,480 --> 00:50:59,210
ach beidh muid a fháil chun go.

658
00:50:59,210 --> 00:51:03,950
Má tá luach níos mó ná cibé, ansin teocht ceart teocht.

659
00:51:03,950 --> 00:51:07,910
Ach sula dhéanaimid sin, tuismitheoir = teocht.

660
00:51:07,910 --> 00:51:14,500
Nó an bhfuil na tuismitheoirí dul i gcónaí a teocht cothrom? An é sin an cás?

661
00:51:14,500 --> 00:51:19,560
Mura bhfuil teocht nialasach, ansin tá mé ag dul chun bogadh síos, is cuma cén,

662
00:51:19,560 --> 00:51:24,030
ar nód a bhfuil teocht an tuismitheoir.

663
00:51:24,030 --> 00:51:27,500
Mar sin, tá tuismitheoir ag dul a bheith sealadach, agus ansin bogadh liom teocht síos.

664
00:51:27,500 --> 00:51:32,410
Anois tá teocht nialasach, ach pointí tuismitheoir tuismitheoir an rud is faoin margadh saothair.

665
00:51:32,410 --> 00:51:39,110
Mar sin síos anseo, níl mé ag iarraidh a shocrú ceart ionann 1.

666
00:51:39,110 --> 00:51:41,300
Mar sin, bhog mé go dtí an ceart, mar sin má dheis = 1,

667
00:51:41,300 --> 00:51:45,130
agus buille faoi thuairim mé ba mhaith leat a dhéanamh -

668
00:51:45,130 --> 00:51:48,530
má tá tú ag bogadh ar chlé, is mian leat a shocrú ceart cothrom le 0.

669
00:51:48,530 --> 00:51:55,950
Nó eile má tá tú ag bogadh riamh leis an gceart.

670
00:51:55,950 --> 00:51:58,590
Mar sin ceart = 0. Má tá ceart = 1,

671
00:51:58,590 --> 00:52:04,260
anois, ba mhaith linn a dhéanamh ar an tuismitheoir newnode pointeoir ceart,

672
00:52:04,260 --> 00:52:08,520
eile ba mhaith linn a dhéanamh ar an tuismitheoir newnode pointeoir chlé.

673
00:52:08,520 --> 00:52:16,850
Ceisteanna ar sin?

674
00:52:16,850 --> 00:52:24,880
Maith go leor. Mar sin, is é seo an tslí a - go maith, i ndáiríre, in ionad é seo a dhéanamh,

675
00:52:24,880 --> 00:52:29,630
súil againn leath leat build_node a úsáid.

676
00:52:29,630 --> 00:52:40,450
Agus ansin má bhíonn newnode null, ar ais bréagach.

677
00:52:40,450 --> 00:52:44,170
Sin sin. Anois, is é seo cad súil againn tú a dhéanamh.

678
00:52:44,170 --> 00:52:47,690
>> Tá sé seo cad a dhéanann na réitigh foirne.

679
00:52:47,690 --> 00:52:52,360
Ní aontaím leis seo mar an bealach is ceart "" de ag dul faoi

680
00:52:52,360 --> 00:52:57,820
ach tá sé seo breá breá agus beidh sé ag obair.

681
00:52:57,820 --> 00:53:02,840
Rud amháin go bhfuil ceart beag aisteach anois

682
00:53:02,840 --> 00:53:08,310
má thosaíonn an crann amach mar faoin margadh saothair, táimid ag dul i gcrann null.

683
00:53:08,310 --> 00:53:12,650
Buille faoi thuairim mé braitheann sé ar cé tú shainiú ar an iompar a ritheadh ​​i gcrann null.

684
00:53:12,650 --> 00:53:15,490
Ba mhaith liom smaoineamh go má théann tú i gcrann Eolas faoin margadh saothair,

685
00:53:15,490 --> 00:53:17,520
ansin tríd an luach isteach i gcrann null

686
00:53:17,520 --> 00:53:23,030
Ba chóir go díreach ar ais crann áit a bhfuil an luach amháin go nód amháin.

687
00:53:23,030 --> 00:53:25,830
An aontaíonn daoine le sin? D'fhéadfá, dá mba mhaith leat,

688
00:53:25,830 --> 00:53:28,050
má éiríonn leat i gcrann null

689
00:53:28,050 --> 00:53:31,320
agus is mian leat a chur isteach ar luach isteach é, ar ais bréagach.

690
00:53:31,320 --> 00:53:33,830
Tá sé suas chun tú a shainmhíniú go.

691
00:53:33,830 --> 00:53:38,320
Chun seo a dhéanamh an chéad rud a dúirt mé agus ansin -

692
00:53:38,320 --> 00:53:40,720
go maith, agus tú ag dul go bhfuil deacracht a dhéanamh, mar gheall ar

693
00:53:40,720 --> 00:53:44,090
go mbeadh sé níos éasca má bhí againn le pointeoir domhanda leis an rud,

694
00:53:44,090 --> 00:53:48,570
ach ní féidir linn, mar sin má tá crann nialasach, níl aon rud is féidir linn a dhéanamh faoi sin.

695
00:53:48,570 --> 00:53:50,960
Is féidir linn ar ais ach bréagach.

696
00:53:50,960 --> 00:53:52,840
Mar sin, tá mé ag dul isteach a athrú.

697
00:53:52,840 --> 00:53:56,540
D'fhéadfadh muid teicniúil a athrú ach an ceart seo anseo,

698
00:53:56,540 --> 00:53:58,400
conas a iterating sé thar rudaí,

699
00:53:58,400 --> 00:54:04,530
ach tá mé ag dul isteach a athrú a ghlacadh nód ** crann.

700
00:54:04,530 --> 00:54:07,510
Leideanna Double.

701
00:54:07,510 --> 00:54:09,710
Cad a chiallaíonn sé seo?

702
00:54:09,710 --> 00:54:12,330
In ionad déileáil le leideanna chun nóid,

703
00:54:12,330 --> 00:54:16,690
Is é an rud Tá mé ag dul a bheith ag ionramháil an pointeoir.

704
00:54:16,690 --> 00:54:18,790
Tá mé ag dul a bheith ag ionramháil an pointeoir.

705
00:54:18,790 --> 00:54:21,770
Tá mé ag dul a bheith leideanna ionramháil go díreach.

706
00:54:21,770 --> 00:54:25,760
Tá ciall ó shin, machnamh a dhéanamh ar síos -

707
00:54:25,760 --> 00:54:33,340
go maith, ceart seo anois pointí nialasach.

708
00:54:33,340 --> 00:54:38,130
Cad ba mhaith liom a dhéanamh ná a ionramháil an pointeoir a chur in iúl nach nialasach.

709
00:54:38,130 --> 00:54:40,970
Ba mhaith liom é a chur in iúl do mo nód nua.

710
00:54:40,970 --> 00:54:44,870
Má tá mé a choinneáil ach rian de leideanna le mo threo,

711
00:54:44,870 --> 00:54:47,840
ansin ní féidir liom gá súil a choinneáil ar a pointeoir tuismitheoir.

712
00:54:47,840 --> 00:54:52,640
Is féidir liom a choinneáil ach rian a fheiceáil má tá an pointeoir dírithe nialasach,

713
00:54:52,640 --> 00:54:54,580
agus má tá an pointeoir dírithe nialasach,

714
00:54:54,580 --> 00:54:57,370
athrú a chur in iúl leis an nód ba mhaith liom.

715
00:54:57,370 --> 00:55:00,070
Agus is féidir liom é a athrú ó tá mé pointeoir chuig an pointeoir.

716
00:55:00,070 --> 00:55:02,040
A ligean ar a fheiceáil an ceart seo anois.

717
00:55:02,040 --> 00:55:05,470
Is féidir leat a dhéanamh i ndáiríre é go hathchúrsach go héasca go leor.

718
00:55:05,470 --> 00:55:08,080
An bhfuil muid ag iarraidh sin a dhéanamh?

719
00:55:08,080 --> 00:55:10,980
Sea, a dhéanann muid.

720
00:55:10,980 --> 00:55:16,790
>> A ligean ar é a fheiceáil go hathchúrsach.

721
00:55:16,790 --> 00:55:24,070
Gcéad dul síos, cad ár gcás bonn ag dul a bheith?

722
00:55:24,070 --> 00:55:29,140
Beagnach i gcónaí ar ár gcás bonn; ach i ndáiríre, tá sé seo de chineál ar tricky.

723
00:55:29,140 --> 00:55:34,370
Rudaí chéad chéad, más rud é (crann == NULLComment)

724
00:55:34,370 --> 00:55:37,550
Buille faoi thuairim mé táimid ag dul díreach a thabhairt ar ais bréagach.

725
00:55:37,550 --> 00:55:40,460
Tá sé seo difriúil ó do null crann a bheith.

726
00:55:40,460 --> 00:55:44,510
Is é seo an pointeoir le do pointeoir fréimhe a bheith null

727
00:55:44,510 --> 00:55:48,360
rud a chiallaíonn nach do pointeoir fréimhe ann.

728
00:55:48,360 --> 00:55:52,390
Mar sin anseo síos, más rud é is féidir liom

729
00:55:52,390 --> 00:55:55,760
* nód - a ligean ar athúsáid ach seo.

730
00:55:55,760 --> 00:55:58,960
Nód * fhréamh = NULLComment,

731
00:55:58,960 --> 00:56:00,730
agus ansin tá mé ag dul isteach a ghlaoite ag déanamh rud éigin cosúil le,

732
00:56:00,730 --> 00:56:04,540
isteach 4 i & root.

733
00:56:04,540 --> 00:56:06,560
Mar sin, & fréimhe, más rud é fréamh a * nód

734
00:56:06,560 --> 00:56:11,170
ansin & root dul chun bheith ina ** nód.

735
00:56:11,170 --> 00:56:15,120
Tá sé seo bailí. Sa chás seo, crann, suas anseo,

736
00:56:15,120 --> 00:56:20,120
Níl crann Eolas faoin margadh saothair - nó cuir isteach.

737
00:56:20,120 --> 00:56:24,630
Anseo. Ní Crann Eolas faoin margadh saothair; * Tá crann nialasach, atá fíneáil

738
00:56:24,630 --> 00:56:26,680
mar má tá crann * nialasach, ansin is féidir liom a ionramháil

739
00:56:26,680 --> 00:56:29,210
a chur in iúl anois cad ba mhaith liom é a chur in iúl go.

740
00:56:29,210 --> 00:56:34,750
Ach má tá crann nialasach, a chiallaíonn go tháinig mé díreach síos anseo agus dúirt null.

741
00:56:34,750 --> 00:56:42,710
Ní sin ciall a bhaint as. Ní féidir liom aon rud a dhéanamh leis sin.

742
00:56:42,710 --> 00:56:45,540
Má tá crann nialasach, ar ais bréagach.

743
00:56:45,540 --> 00:56:48,220
Mar sin, mé go bunúsach cheana féin an méid a dúradh é ár gcás bonn fíor.

744
00:56:48,220 --> 00:56:50,580
Agus is é an méid sin ag dul a bheith?

745
00:56:50,580 --> 00:56:55,030
[Mac Léinn, dothuigthe]

746
00:56:55,030 --> 00:57:00,000
[Bowden] Tá. Mar sin, más rud é (* crann == NULLComment).

747
00:57:00,000 --> 00:57:04,520
Baineann sé seo leis an gcás thar anseo

748
00:57:04,520 --> 00:57:09,640
i gcás má tá mo pointeoir dearg an pointeoir Tá mé dírithe ar,

749
00:57:09,640 --> 00:57:12,960
mar sin cosúil Tá mé dírithe ar an pointeoir, anois tá mé dírithe ar an pointeoir.

750
00:57:12,960 --> 00:57:15,150
Anois, tá mé dírithe ar an pointeoir.

751
00:57:15,150 --> 00:57:18,160
Mar sin, más rud é mo pointeoir dearg, a bhfuil mo ** nód,

752
00:57:18,160 --> 00:57:22,880
Is é riamh - má *, mo pointeoir dearg, riamh faoin margadh saothair,

753
00:57:22,880 --> 00:57:28,470
ciallaíonn sé go bhfuil mé ar an gcás ina bhfuil mé ag díriú ar pointeoir go pointí -

754
00:57:28,470 --> 00:57:32,530
tá sé seo le pointeoir a bhaineann leis duilleog.

755
00:57:32,530 --> 00:57:41,090
Ba mhaith liom seo a athrú pointeoir a chur in iúl do mo nód nua.

756
00:57:41,090 --> 00:57:45,230
Tar ar ais thar anseo.

757
00:57:45,230 --> 00:57:56,490
Beidh mo newnode a bheith díreach nód * n = build_node (luach)

758
00:57:56,490 --> 00:58:07,300
ansin n má n = NULLComment aischuir bréagach.

759
00:58:07,300 --> 00:58:12,600
Eile ba mhaith linn a athrú ar a bhfuil an pointeoir dírithe faoi láthair chun

760
00:58:12,600 --> 00:58:17,830
a chur in iúl anois ar ár nód nua-thógtha.

761
00:58:17,830 --> 00:58:20,280
Is féidir linn a dhéanamh i ndáiríre go anseo.

762
00:58:20,280 --> 00:58:30,660
In ionad n rá, deirimid * crann = más rud é * crann.

763
00:58:30,660 --> 00:58:35,450
Tá ag gach duine a thuiscint go? Go bhfuil ag déileáil le leideanna chun leideanna,

764
00:58:35,450 --> 00:58:40,750
féidir linn a athrú leideanna faoin margadh saothair a chur in iúl chun rudaí a ba mhaith linn iad a chur in iúl go.

765
00:58:40,750 --> 00:58:42,820
Sin ár gcás bonn.

766
00:58:42,820 --> 00:58:45,740
>> Anois ár atarlú, nó ar ár athchúrsáil,

767
00:58:45,740 --> 00:58:51,430
ag dul a bheith an-chosúil le gach recursions eile tá muid ag déanamh.

768
00:58:51,430 --> 00:58:55,830
Táimid ag dul go dtí gur mian luach a chur isteach,

769
00:58:55,830 --> 00:58:59,040
agus anois tá mé ag dul trínártha a úsáid arís, ach cad é ár staid ag dul a bheith?

770
00:58:59,040 --> 00:59:05,180
Cad a bhfuil sé táimid ag lorg chun a chinneadh cé acu ba mhaith linn dul ar chlé nó ceart?

771
00:59:05,180 --> 00:59:07,760
Déanaimis é a dhéanamh i gcéimeanna ar leith.

772
00:59:07,760 --> 00:59:18,850
Más rud é (luach <) cad é?

773
00:59:18,850 --> 00:59:23,200
[Mac Léinn] an crann ar luach?

774
00:59:23,200 --> 00:59:27,490
[Bowden] Mar sin, cuimhnigh go bhfuil mé faoi láthair -

775
00:59:27,490 --> 00:59:31,260
[Mic léinn, dothuigthe]

776
00:59:31,260 --> 00:59:34,140
[Bowden] Yeah, mar sin ceart anseo, a ligean ar rá go bhfuil an arrow glas

777
00:59:34,140 --> 00:59:39,050
Is sampla de cad is crann faoi láthair, tá pointeoir leis an pointeoir.

778
00:59:39,050 --> 00:59:46,610
Mar sin, Ciallaíonn sé sin go mé pointeoir le pointeoir go 3.

779
00:59:46,610 --> 00:59:48,800
An téigh i sounded faoi dhó maith.

780
00:59:48,800 --> 00:59:51,010
Cad a dhéanfaidh mé - conas is féidir liom a dhéanamh?

781
00:59:51,010 --> 00:59:53,210
[Mac Léinn] téigh i uair amháin, agus ansin déan arrow sin ar bhealach?

782
00:59:53,210 --> 00:59:58,420
[Bowden] Mar sin (* crann) Is é an dereference téigh i uair amháin, -> luach

783
00:59:58,420 --> 01:00:05,960
ag dul a thabhairt dom luach na nód go bhfuil mé ag déanamh tagairt go hindíreach.

784
01:00:05,960 --> 01:00:11,980
Mar sin, is féidir liom scríobh chomh maith ** sé tree.value más fearr leat sin.

785
01:00:11,980 --> 01:00:18,490
Ceachtar oibríonn.

786
01:00:18,490 --> 01:00:26,190
Más rud é go bhfuil an cás, ansin ba mhaith liom a ghlaoch isteach le luach.

787
01:00:26,190 --> 01:00:32,590
Agus cad é mo nód cothrom le dáta ** ag dul a bheith?

788
01:00:32,590 --> 01:00:39,440
Ba mhaith liom dul go dtí an taobh clé, mar sin ** tree.left ag dul a bheith ar mo chlé.

789
01:00:39,440 --> 01:00:41,900
Agus ba mhaith liom an pointeoir leis an rud

790
01:00:41,900 --> 01:00:44,930
ionas go má chríochnaíonn thaobh na láimhe clé a bheith suas an pointeoir nialasach,

791
01:00:44,930 --> 01:00:48,360
Is féidir liom a mhodhnú go pointe go dtí mo nód nua.

792
01:00:48,360 --> 01:00:51,460
>> Agus is féidir an cás eile a bheith an-chosúil.

793
01:00:51,460 --> 01:00:55,600
Déanaimis a dhéanamh i ndáiríre go bhfuil mo trínártha ceart anois.

794
01:00:55,600 --> 01:01:04,480
Cuir isteach luach más rud é luach <(** crann). Luach.

795
01:01:04,480 --> 01:01:11,040
Ansin ba mhaith linn ár ** thabhairt cothrom le dáta ar an taobh clé,

796
01:01:11,040 --> 01:01:17,030
eile ba mhaith linn ár ** thabhairt cothrom le dáta leis an gceart.

797
01:01:17,030 --> 01:01:22,540
[Mac Léinn] An bhfuil a fháil go bhfuil an pointeoir leis an pointeoir?

798
01:01:22,540 --> 01:01:30,940
[Bowden] Cuimhnigh go - Is é ** tree.right le réalta nód.

799
01:01:30,940 --> 01:01:35,040
[Mac Léinn, dothuigthe] >> Yeah.

800
01:01:35,040 --> 01:01:41,140
** Tree.right Is mar seo pointeoir nó rud éigin.

801
01:01:41,140 --> 01:01:45,140
Mar sin, ag cur le pointeoir leis sin, tugann go dom cad ba mhaith liom

802
01:01:45,140 --> 01:01:50,090
an pointeoir leis an Guy.

803
01:01:50,090 --> 01:01:54,260
[Mac Léinn] Níorbh fhéidir linn dul arís fáth go bhfuil muid ag baint úsáide as an dá threo?

804
01:01:54,260 --> 01:01:58,220
[Bowden] Yeah. Mar sin, - no, is féidir leat, agus go bhfuil réiteach roimh

805
01:01:58,220 --> 01:02:04,540
Ba bhealach é a dhéanamh gan déanamh dhá threo.

806
01:02:04,540 --> 01:02:08,740
Ní mór duit a bheith in ann a thuiscint ag baint úsáide as dhá threo,

807
01:02:08,740 --> 01:02:11,660
agus tá sé seo le réiteach níos glaine.

808
01:02:11,660 --> 01:02:16,090
Chomh maith leis sin, faoi deara go bhfuil, cad a tharlaíonn má tá mo chrann -

809
01:02:16,090 --> 01:02:24,480
cad a tharlaíonn má bhí mo fréimhe null? Cad a tharlaíonn má dhéanaim an gcás seo ar dheis anseo?

810
01:02:24,480 --> 01:02:30,540
Mar sin, nód * fhréamh = NULLComment, cuir isteach 4 i & root.

811
01:02:30,540 --> 01:02:35,110
Cad é fréamh ag dul a bheith tar éis é seo?

812
01:02:35,110 --> 01:02:37,470
[Mac Léinn, dothuigthe] >> Yeah.

813
01:02:37,470 --> 01:02:41,710
Tá luach root ag dul a bheith 4.

814
01:02:41,710 --> 01:02:45,510
Tá chlé Root ag dul a bheith ar neamhní, tá ceart fréimhe ag dul a bheith ar neamhní.

815
01:02:45,510 --> 01:02:49,490
Sa chás nach raibh muid pas a fhréamh le seoladh,

816
01:02:49,490 --> 01:02:52,490
ní raibh muid ábalta a mhodhnú fréimhe.

817
01:02:52,490 --> 01:02:56,020
I gcás ina bhfuil an crann - áit a raibh fréamhacha nialasach,

818
01:02:56,020 --> 01:02:58,410
raibh againn ach a thabhairt ar ais bréagach. Níl aon rud gur féidir linn a dhéanamh.

819
01:02:58,410 --> 01:03:01,520
Ní féidir linn a chur isteach nód isteach i crann folamh.

820
01:03:01,520 --> 01:03:06,810
Ach is féidir anois againn; linn a dhéanamh ach crann folamh isteach i gcrann aon-nód.

821
01:03:06,810 --> 01:03:13,400
A bhfuil de ghnáth ar an mbealach ag súil go bhfuil sé ceaptha a bheith ag obair.

822
01:03:13,400 --> 01:03:21,610
>> Ina theannta sin, tá sé seo i bhfad níos giorra ná

823
01:03:21,610 --> 01:03:26,240
freisin taifead a choinneáil de na tuismitheoirí, agus mar sin tú abair síos go léir ar an mbealach.

824
01:03:26,240 --> 01:03:30,140
Anois, tá mé mo mháthair, agus tá mé díreach tar éis mo pointeoir ceart tuismitheoir ar an cuma.

825
01:03:30,140 --> 01:03:35,640
Ina áit sin, má rinne muid an iteratively, ba é a bheith an smaoineamh céanna le lúb tamaill.

826
01:03:35,640 --> 01:03:38,100
Ach in ionad a bheith chun déileáil le mo pointeoir tuismitheoir,

827
01:03:38,100 --> 01:03:40,600
ina ionad sin a bheadh ​​mo pointeoir reatha an rud

828
01:03:40,600 --> 01:03:43,790
go bhfuil mé ag athrú go díreach a chur in iúl do mo nód nua.

829
01:03:43,790 --> 01:03:46,090
Ní féidir liom déileáil le cibé an tá atá dírithe sé ar an taobh clé.

830
01:03:46,090 --> 01:03:48,810
Ní féidir liom déileáil le cibé an tá atá dírithe chuig an ceart.

831
01:03:48,810 --> 01:04:00,860
Tá sé díreach is cuma cad é an pointeoir, tá mé ag dul a shocrú a chur in iúl do mo nód nua.

832
01:04:00,860 --> 01:04:05,740
Tá ag gach duine a thuiscint conas a oibríonn sé?

833
01:04:05,740 --> 01:04:09,460
Más rud é nach cén fáth ar mhaith linn a dhéanamh ar an mbealach seo,

834
01:04:09,460 --> 01:04:14,920
ach ar a laghad go bhfuil an obair mar réiteach?

835
01:04:14,920 --> 01:04:17,110
[Mac Léinn] Cá bhfuil muid ar ais fíor?

836
01:04:17,110 --> 01:04:21,550
[Bowden] Sin is dócha ceart anseo.

837
01:04:21,550 --> 01:04:26,690
Má táimid isteach i gceart é, ar ais fíor.

838
01:04:26,690 --> 01:04:32,010
Eile, síos anseo táimid ag dul a iarraidh a thabhairt ar ais ar ais isteach is cuma cad.

839
01:04:32,010 --> 01:04:35,950
>> Tá Agus cad speisialta faoi an fheidhm athchúrsach?

840
01:04:35,950 --> 01:04:43,010
Tá sé eireaball athchúrsach, mar sin chomh fada agus muid ag chur le chéile le roinnt leas iomlán a bhaint,

841
01:04:43,010 --> 01:04:48,060
tabharfaidh sé aitheantas sin agus ní bheidh a fháil thar maoil Stack tú as seo,

842
01:04:48,060 --> 01:04:53,230
fiú má tá ár n-crann ar airde de 10,000 nó 10 milliún.

843
01:04:53,230 --> 01:04:55,630
[Mac Léinn, dothuigthe]

844
01:04:55,630 --> 01:05:00,310
[Bowden] I mo thuairimse, a dhéanann sé sé ag Dash - nó cén leibhéal leas iomlán a bhaint

845
01:05:00,310 --> 01:05:03,820
bhfuil gá le haghaidh athchúrsáil eireaball a aithint.

846
01:05:03,820 --> 01:05:09,350
I mo thuairimse, aithníonn sé - GCC agus clang

847
01:05:09,350 --> 01:05:12,610
chomh maith go bhfuil bríonna éagsúla le haghaidh a n leibhéil leas iomlán a bhaint.

848
01:05:12,610 --> 01:05:17,870
Ba mhaith liom a rá go bhfuil sé DashO 2, do cinnte go mbeidh sé aitheantas athchúrsáil eireaball.

849
01:05:17,870 --> 01:05:27,880
Ach táimid - d'fhéadfaí tú a thógáil cosúil le mar shampla Fibonocci nó rud éigin.

850
01:05:27,880 --> 01:05:30,030
Níl sé éasca a thástáil leis seo, mar tá sé deacair a thógáil

851
01:05:30,030 --> 01:05:32,600
crann dénártha go chomh mór.

852
01:05:32,600 --> 01:05:37,140
Ach yeah, Sílim go bhfuil sé DashO 2, go

853
01:05:37,140 --> 01:05:40,580
má tá tú a thiomsú le DashO 2, beidh sé cuma ar athchúrsáil eireaball

854
01:05:40,580 --> 01:05:54,030
agus seirbhíse a uasmhéadú sin amach.

855
01:05:54,030 --> 01:05:58,190
A ligean ar dul ar ais chuig - cuir isteach Tá literally an rud deireanach ag teastáil uaidh.

856
01:05:58,190 --> 01:06:04,900
A ligean ar dul ar ais chuig an chur isteach thar anseo

857
01:06:04,900 --> 01:06:07,840
nuair a táimid ag dul a dhéanamh ar an smaoineamh céanna.

858
01:06:07,840 --> 01:06:14,340
Beidh sé a bheith fós ar an locht ar gan a bheith in ann déileáil go hiomlán

859
01:06:14,340 --> 01:06:17,940
nuair a bhíonn an fhréamh féin faoin margadh saothair, nó go bhfuil an iontráil seo caite faoin margadh saothair,

860
01:06:17,940 --> 01:06:20,060
ach in ionad déileáil le pointeoir tuismitheoir,

861
01:06:20,060 --> 01:06:27,430
a ligean ar an loighic chéanna de leideanna a choinneáil maidir le leideanna.

862
01:06:27,430 --> 01:06:35,580
Má anseo againn a choinneáil ar ár nód ** rth,

863
01:06:35,580 --> 01:06:37,860
agus ní mór dúinn súil a choinneáil ar cheart níos mó,

864
01:06:37,860 --> 01:06:47,190
ach nód ** rth = & crann.

865
01:06:47,190 --> 01:06:54,800
Agus anois tá ár n-lúb agus ag dul a bheith cé go bhfuil ní rth * null comhionann.

866
01:06:54,800 --> 01:07:00,270
Ná ní gá a choinneáil ar na tuismitheoirí níos mó.

867
01:07:00,270 --> 01:07:04,180
Ná ní gá súil a choinneáil ar chlé agus ar dheis.

868
01:07:04,180 --> 01:07:10,190
Agus beidh mé a ghlaoch air teocht, toisc go bhfuil muid ag baint úsáide as cheana féin teocht.

869
01:07:10,190 --> 01:07:17,200
Maith go leor. Mar sin, más rud é (luach> * teocht),

870
01:07:17,200 --> 01:07:24,010
ansin & (* teocht) -> ceart

871
01:07:24,010 --> 01:07:29,250
eile teocht = & (* teocht) -> ar chlé.

872
01:07:29,250 --> 01:07:32,730
Agus anois, ag an bpointe seo, tar éis an lúb agus,

873
01:07:32,730 --> 01:07:36,380
Is féidir liom ach seo toisc go b'fhéidir go bhfuil sé níos éasca chun smaoineamh ar iteratively ná go hathchúrsach,

874
01:07:36,380 --> 01:07:39,010
ach tar éis an lúb agus,

875
01:07:39,010 --> 01:07:43,820
* Tá an teocht an pointeoir ba mhaith linn a athrú.

876
01:07:43,820 --> 01:07:48,960
>> Sula bhí againn tuismitheoir, agus bhíomar ag iarraidh a athrú ar chlé tuismitheoir nó tuismitheoir ceart,

877
01:07:48,960 --> 01:07:51,310
ach más mian linn a athrú ceart tuismitheoir,

878
01:07:51,310 --> 01:07:54,550
ansin * teocht ceart tuismitheoirí, agus is féidir linn a athrú go díreach leis.

879
01:07:54,550 --> 01:08:05,860
Mar sin anseo síos, is féidir linn a dhéanamh * teocht = newnode, agus go bhfuil sé.

880
01:08:05,860 --> 01:08:09,540
Mar sin, fógra, ni dhearna muid sa thógáil amach línte cód.

881
01:08:09,540 --> 01:08:14,770
D'fhonn súil a choinneáil ar an tuismitheoir i go léir go bhfuil iarracht bhreise.

882
01:08:14,770 --> 01:08:18,689
Anseo, má táimid a choinneáil ach rian ar an pointeoir leis an pointeoir,

883
01:08:18,689 --> 01:08:22,990
agus fiú má bhíomar ag iarraidh a fháil haitheantas coibhneasta de seo go léir braces chatach anois,

884
01:08:22,990 --> 01:08:27,170
dhéanamh breathnú níos giorra.

885
01:08:27,170 --> 01:08:32,529
Tá sé seo anois ar an réiteach ceannann céanna,

886
01:08:32,529 --> 01:08:38,210
ach níos lú línte cód.

887
01:08:38,210 --> 01:08:41,229
Nuair a thosóidh tú ag aithint seo mar réiteach bailí,

888
01:08:41,229 --> 01:08:43,529
tá sé chomh maith níos éasca mar gheall ar ná mar, maith go leor,

889
01:08:43,529 --> 01:08:45,779
cén fáth a bhfuil mé ag an mbratach ar dheis o?

890
01:08:45,779 --> 01:08:49,290
Cad a chiallaíonn? Ó, tá signifying go

891
01:08:49,290 --> 01:08:51,370
gach uair a théann mé ceart, is gá dom a shocrú,

892
01:08:51,370 --> 01:08:53,819
eile má théann mé fágtha gá dom é a shocrú go nialas.

893
01:08:53,819 --> 01:09:04,060
Anseo, ní dóigh liom go bhfuil cúis faoi sin; tá sé ach níos éasca chun machnamh.

894
01:09:04,060 --> 01:09:06,710
Ceisteanna?

895
01:09:06,710 --> 01:09:16,290
[Mac Léinn, dothuigthe] >> Yeah.

896
01:09:16,290 --> 01:09:23,359
Maith go leor, mar sin i an giotán deireanach -

897
01:09:23,359 --> 01:09:28,080
Buille faoi thuairim mé go bhfuil feidhm amháin tapaidh agus éasca is féidir linn a dhéanamh,

898
01:09:28,080 --> 01:09:34,910
let's - le chéile, buille faoi thuairim mé, déan iarracht agus scríobh bhfuil feidhm

899
01:09:34,910 --> 01:09:38,899
nach bhfuil cúram cibé an bhfuil sé crann cuardaigh dénártha.

900
01:09:38,899 --> 01:09:43,770
Cuimsíonn sé seo ba chóir feidhm ais fíor

901
01:09:43,770 --> 01:09:58,330
más rud é in áit ar bith sa crann dhénártha ginearálta an luach táimid ag lorg.

902
01:09:58,330 --> 01:10:02,520
Mar sin a ligean a dhéanamh ar dtús é go hathchúrsach agus ansin beidh muid é a dhéanamh iteratively.

903
01:10:02,520 --> 01:10:07,300
Is féidir linn i ndáiríre a dhéanamh go díreach le chéile, toisc go bhfuil sé seo ag dul a bheith i ndáiríre gearr.

904
01:10:07,300 --> 01:10:11,510
>> Cad é mo chás bonn ag dul a bheith?

905
01:10:11,510 --> 01:10:13,890
[Mac Léinn, dothuigthe]

906
01:10:13,890 --> 01:10:18,230
[Bowden] más rud é sin, (crann == NULLComment), ansin cad é?

907
01:10:18,230 --> 01:10:22,740
[Mac Léinn] ais bréagach.

908
01:10:22,740 --> 01:10:26,160
[Bowden] Eile, go maith, ní féidir liom gá an duine eile.

909
01:10:26,160 --> 01:10:30,250
Bhí Más rud é mo chás bonn eile.

910
01:10:30,250 --> 01:10:32,450
Luach [Mac Léinn] Crann Fir? >> Yeah.

911
01:10:32,450 --> 01:10:36,430
Mar sin, más rud é (luach crann-> luach ==.

912
01:10:36,430 --> 01:10:39,920
Fógra táimid ar ais gan * nód, nód ** s?

913
01:10:39,920 --> 01:10:42,990
Ní bheidh Tá gá a úsáid ** nód,

914
01:10:42,990 --> 01:10:45,480
ós rud é nach bhfuil muid leideanna a mhodhnú.

915
01:10:45,480 --> 01:10:50,540
Táimid ag thrasnaíonn díreach leo.

916
01:10:50,540 --> 01:10:53,830
Má tharlaíonn sin, ansin ba mhaith linn a thabhairt ar ais fíor.

917
01:10:53,830 --> 01:10:58,270
Eile ba mhaith linn a lean na leanaí.

918
01:10:58,270 --> 01:11:02,620
Mar sin, ní féidir linn a réasúnú maidir le cé acu an bhfuil gach rud ar an taobh clé níos lú

919
01:11:02,620 --> 01:11:05,390
agus tá gach rud ar dheis níos mó.

920
01:11:05,390 --> 01:11:09,590
Mar sin, cad ár staid ag dul a bheith anseo - nó, cad tá muid ag dul a dhéanamh?

921
01:11:09,590 --> 01:11:11,840
[Mac Léinn, dothuigthe] >> Yeah.

922
01:11:11,840 --> 01:11:17,400
Tuairisceán Tá (luach, crann-> ar chlé)

923
01:11:17,400 --> 01:11:26,860
nó go bhfuil (luach, crann-> dheis). Agus sin é.

924
01:11:26,860 --> 01:11:29,080
Agus faoi deara go bhfuil roinnt meastóireacht gearr-chuaird,

925
01:11:29,080 --> 01:11:32,520
i gcás má tharlaíonn linn chun teacht ar an luach sa crann chlé,

926
01:11:32,520 --> 01:11:36,820
againn riamh gá chun breathnú ar an crann ceart.

927
01:11:36,820 --> 01:11:40,430
Sin é an fheidhm ar fad.

928
01:11:40,430 --> 01:11:43,690
Anois, a ligean é a dhéanamh iteratively,

929
01:11:43,690 --> 01:11:48,060
atá ag dul a bheith níos lú deas.

930
01:11:48,060 --> 01:11:54,750
Beidh muid a chur ar an tús is gnách ar an rth nód * = crann.

931
01:11:54,750 --> 01:12:03,250
Cé go (rth! = NULLComment).

932
01:12:03,250 --> 01:12:08,600
Go tapa ag dul a fheiceáil fhadhb.

933
01:12:08,600 --> 01:12:12,250
Má rth - amach anseo, má sos againn riamh as seo,

934
01:12:12,250 --> 01:12:16,020
ansin tá muid ag rith amach as rudaí chun breathnú ar, ar ais mar sin bréagach.

935
01:12:16,020 --> 01:12:24,810
Más rud é (rth-> Luach == luach), ar ais fíor.

936
01:12:24,810 --> 01:12:32,910
Mar sin, anois, tá muid in áit -

937
01:12:32,910 --> 01:12:36,250
níl a fhios againn cé acu ba mhaith linn dul ar chlé nó ceart.

938
01:12:36,250 --> 01:12:44,590
Mar sin, treallach, a ligean ar dul ar chlé díreach.

939
01:12:44,590 --> 01:12:47,910
Tá mé á reáchtáil ar ndóigh isteach i gceist nuair a bhí mé tréigthe go hiomlán gach rud -

940
01:12:47,910 --> 01:12:50,760
Beidh mé ach seiceáil riamh an taobh clé den chrann.

941
01:12:50,760 --> 01:12:56,050
Ní bheidh mé ag seiceáil rud ar bith go bhfuil leanbh ceart rud ar bith.

942
01:12:56,050 --> 01:13:00,910
Conas is féidir liom a shocrú seo?

943
01:13:00,910 --> 01:13:05,260
[Mac Léinn] Tá tú a choinneáil ar an chlé agus ar dheis i chairn.

944
01:13:05,260 --> 01:13:13,710
[Bowden] Yeah. Mar sin a ligean a dhéanamh

945
01:13:13,710 --> 01:13:32,360
struct liosta, nód * n, agus ansin nód ** chugainn?

946
01:13:32,360 --> 01:13:40,240
I mo thuairimse, go n-oibríonn breá.

947
01:13:40,240 --> 01:13:45,940
Is mian linn dul thar na láimhe clé, nó let's - suas anseo.

948
01:13:45,940 --> 01:13:54,350
= Struct liosta liosta, beidh sé tús

949
01:13:54,350 --> 01:13:58,170
amach ag an liosta seo struct.

950
01:13:58,170 --> 01:14:04,040
* Liosta = NULLComment. Mar sin, tá go bhfuil ag dul a bheith ar ár liosta nasctha

951
01:14:04,040 --> 01:14:08,430
de subtrees go bhfuil muid ndearna os a chionn.

952
01:14:08,430 --> 01:14:13,800
Táimid ag dul a lean ar chlé anois,

953
01:14:13,800 --> 01:14:17,870
ach ós rud é is gá dúinn gan dabht teacht ar ais chuig an ceart,

954
01:14:17,870 --> 01:14:26,140
Táimid ag dul a choinneáil ar an taobh dheis taobh istigh de ár liosta struct.

955
01:14:26,140 --> 01:14:32,620
Ansin, beidh orainn new_list nó struct,

956
01:14:32,620 --> 01:14:41,080
struct liosta *, new_list = malloc (deachúlach (liosta)).

957
01:14:41,080 --> 01:14:44,920
Tá mé ag dul neamhshuim a dhéanamh de earráid-seiceáil a dhéanamh go, ach ba chóir duit seiceáil a fheiceáil má tá sé null.

958
01:14:44,920 --> 01:14:50,540
New_list an nód sé ag dul a chur in iúl -

959
01:14:50,540 --> 01:14:56,890
ó, sin an fáth a bhí mé sé suas anseo. Tá sé seo ag dul a chur in iúl ar liosta struct dara.

960
01:14:56,890 --> 01:15:02,380
Sin díreach cé nasctha liostaí oibre.

961
01:15:02,380 --> 01:15:04,810
Is é seo mar an gcéanna liosta slánuimhir nasctha

962
01:15:04,810 --> 01:15:06,960
ach amháin tá muid in áit ach slánuimhir le * nód.

963
01:15:06,960 --> 01:15:11,040
Tá sé díreach mar an gcéanna.

964
01:15:11,040 --> 01:15:15,100
Mar sin, new_list, luach ár nód new_list,

965
01:15:15,100 --> 01:15:19,120
ag dul a bheith rth-> ceart.

966
01:15:19,120 --> 01:15:24,280
Tá an luach ár new_list-> Tá seo chugainn ag dul a bheith ar ár liosta bunaidh,

967
01:15:24,280 --> 01:15:30,760
agus ansin táimid ag dul a thabhairt cothrom le dáta ar ár liosta a chur in iúl go new_list.

968
01:15:30,760 --> 01:15:33,650
>> Anois, ní mór dúinn de chineál éigin ar bhealach na rudaí ag tarraingt,

969
01:15:33,650 --> 01:15:37,020
cosúil le againn trasnú an subtree ar fad ar chlé.

970
01:15:37,020 --> 01:15:40,480
Anois, ní mór dúinn rudaí a tharraingt amach é,

971
01:15:40,480 --> 01:15:43,850
Is cosúil rth Eolas faoin margadh saothair; nach bhfuil muid ag iarraidh a thabhairt ar ais ach bréagach.

972
01:15:43,850 --> 01:15:50,370
Ba mhaith linn a tharraingt anois taobh amuigh ar ár liosta nua.

973
01:15:50,370 --> 01:15:53,690
Bealach áisiúil é seo a dhéanamh - go maith, i ndáiríre, níl bealaí éagsúla seo a dhéanamh.

974
01:15:53,690 --> 01:15:56,680
Duine ar bith a bhfuil moladh?

975
01:15:56,680 --> 01:15:58,790
Nuair ba chóir dom a dhéanamh nó conas ba chóir dom a dhéanamh?

976
01:15:58,790 --> 01:16:08,010
Ní mór dúinn ach cúpla nóiméad, ach aon mholtaí agat?

977
01:16:08,010 --> 01:16:14,750
In ionad - ar bhealach amháin, in ionad ár riocht oiriúnach agus,

978
01:16:14,750 --> 01:16:17,090
cad é nach bhfuil muid ag lorg faoi láthair ag margadh saothair,

979
01:16:17,090 --> 01:16:22,340
ina ionad sin táimid ag dul chun leanúint ar aghaidh chun dul go dtí go bhfuil ár liosta féin null.

980
01:16:22,340 --> 01:16:25,680
Mar sin, má chríochnaíonn ár liosta suas a bheith faoin margadh saothair,

981
01:16:25,680 --> 01:16:30,680
ansin ní mór dúinn a rith amach as rudaí a lorg, chun cuardach a dhéanamh os a chionn.

982
01:16:30,680 --> 01:16:39,860
Ach ciallaíonn sé sin go bhfuil an chéad rud ar ár liosta ag dul ach a bheith ar an nód ar dtús.

983
01:16:39,860 --> 01:16:49,730
Beidh an rud an-an chéad - táimid a thuilleadh gá a fheiceáil go.

984
01:16:49,730 --> 01:16:58,710
Mar sin, liosta-> Beidh a chur ar ár n crann.

985
01:16:58,710 --> 01:17:02,860
liosta-> Tá seo chugainn ag dul a bheith ar neamhní.

986
01:17:02,860 --> 01:17:07,580
Agus anois cé nach liosta null comhionann.

987
01:17:07,580 --> 01:17:11,610
Cur ag dul chun rud éigin a tharraingt ón liosta tú.

988
01:17:11,610 --> 01:17:13,500
Dá bhrí sin tá rth ag dul go dtí cothrom liosta-> n.

989
01:17:13,500 --> 01:17:20,850
Agus ansin tá liosta ag dul go dtí cothrom liosta-> n, nó liosta-> seo chugainn.

990
01:17:20,850 --> 01:17:23,480
Mar sin, is ionann luach rth má luach.

991
01:17:23,480 --> 01:17:28,790
Anois is féidir linn a chur dá ár pointeoir ceart agus ár n-pointeoir chlé

992
01:17:28,790 --> 01:17:32,900
chomh fada is nach bhfuil siad null.

993
01:17:32,900 --> 01:17:36,390
Síos anseo, buille faoi thuairim mé ba chóir dúinn a leithéid a dhéanamh sa chéad áit.

994
01:17:36,390 --> 01:17:44,080
Más rud é (rth-> ceart! = NULLComment)

995
01:17:44,080 --> 01:17:56,380
ansin tá muid ag dul a chur isteach go nód i ár liosta.

996
01:17:56,380 --> 01:17:59,290
Más rud é (rth-> ar chlé), tá sé seo le beagán oibre breise, ach tá sé breá.

997
01:17:59,290 --> 01:18:02,690
Más rud é (rth-> chlé! = NULLComment),

998
01:18:02,690 --> 01:18:14,310
agus táimid ag dul a chur isteach ar an taobh clé isteach ar ár liosta nasctha,

999
01:18:14,310 --> 01:18:19,700
agus ba chóir go mbeadh go bhfuil sé.

1000
01:18:19,700 --> 01:18:22,670
Táimid iterate - chomh fada agus a bhfuil rud éigin i ár liosta,

1001
01:18:22,670 --> 01:18:26,640
ní mór dúinn eile nód chun breathnú ar.

1002
01:18:26,640 --> 01:18:28,920
Mar sin, táimid ag an nód,

1003
01:18:28,920 --> 01:18:31,390
muid ár liosta chun cinn go dtí an ceann eile.

1004
01:18:31,390 --> 01:18:34,060
Más rud é go bhfuil nód an luach táimid ag lorg, is féidir linn ar ais fíor.

1005
01:18:34,060 --> 01:18:37,640
Eile isteach an dá subtrees ár chlé agus ar dheis,

1006
01:18:37,640 --> 01:18:40,510
chomh fada agus nach mbíonn siad faoin margadh saothair, isteach inár liosta

1007
01:18:40,510 --> 01:18:43,120
ionas go mbeidh muid ag dul dosheachanta os a gcionn.

1008
01:18:43,120 --> 01:18:45,160
Mar sin, más rud é nach raibh siad faoin margadh saothair,

1009
01:18:45,160 --> 01:18:47,950
má chuir ár n-pointeoir fhréamh le dhá rud,

1010
01:18:47,950 --> 01:18:51,670
ansin ar dtús tharraing muid rud éigin amach ionas chríochnaíonn ár liosta suas a bheith null.

1011
01:18:51,670 --> 01:18:56,890
Agus ansin chuir muid dhá rud ar ais i, mar sin anois tá ár liosta de mhéid 2.

1012
01:18:56,890 --> 01:19:00,030
Ansin táimid ag dul a lúb ar ais ar bun agus táimid ag dul díreach a tharraingt,

1013
01:19:00,030 --> 01:19:04,250
ligean le rá, an pointeoir na láimhe clé den ár n-nód fréimhe.

1014
01:19:04,250 --> 01:19:07,730
Agus beidh go díreach a choinneáil ag tarlú; beidh muid suas go deireadh looping thar gach rud.

1015
01:19:07,730 --> 01:19:11,280
>> Fógra go raibh sé seo i bhfad níos casta

1016
01:19:11,280 --> 01:19:14,160
sa tuaslagán athchúrsach.

1017
01:19:14,160 --> 01:19:17,260
Agus dúirt mé amanna éagsúla

1018
01:19:17,260 --> 01:19:25,120
go bhfuil an réiteach athchúrsach de ghnáth i bhfad níos coitianta leis an atriallach réiteach.

1019
01:19:25,120 --> 01:19:30,820
Anseo is é seo go díreach cad é an réiteach athchúrsach a dhéanamh.

1020
01:19:30,820 --> 01:19:36,740
Is é an t-athrú ach amháin go ionad hintuigthe ag baint úsáide as an chairn, an chruach chláir,

1021
01:19:36,740 --> 01:19:40,840
mar do bhealach a choimeád rian ar cad nóid ní mór duit fós chun cuairt a thabhairt,

1022
01:19:40,840 --> 01:19:45,430
anois caithfidh tú a úsáid go sainráite liosta nasctha.

1023
01:19:45,430 --> 01:19:49,070
Sa dá chás tá tú ag súil a choinneáil ar riachtanais an méid nód fós le cuairt.

1024
01:19:49,070 --> 01:19:51,790
I gcás athchúrsach tá sé ach níos éasca mar gheall ar Stack

1025
01:19:51,790 --> 01:19:57,100
i bhfeidhm le haghaidh tú mar an chairn chláir.

1026
01:19:57,100 --> 01:19:59,550
Fógra go bhfuil an liosta nasctha, tá sé chairn.

1027
01:19:59,550 --> 01:20:01,580
Cibé rud a chuir muid go díreach ar an chruach

1028
01:20:01,580 --> 01:20:09,960
Is é láithreach cad táimid ag dul a tharraingt amach an chairn chun cuairt a thabhairt chugainn.

1029
01:20:09,960 --> 01:20:14,380
Táimid amach as an am, ach ceist ar bith?

1030
01:20:14,380 --> 01:20:23,530
[Mac Léinn, dothuigthe]

1031
01:20:23,530 --> 01:20:27,790
[Bowden] Yeah. Mar sin, má ní mór dúinn ár liosta nasctha,

1032
01:20:27,790 --> 01:20:30,150
reatha ag dul a chur in iúl ar an Guy,

1033
01:20:30,150 --> 01:20:34,690
agus anois tá muid chun cinn go díreach ar ár liosta nasctha chun díriú ar an Guy.

1034
01:20:34,690 --> 01:20:44,200
Táimid ag thrasnaíonn níos mó ná an liosta nasctha sa líne.

1035
01:20:44,200 --> 01:20:51,200
Agus ansin buille faoi thuairim mé ba chóir dúinn saor in aisce ar ár liosta nasctha agus rudaí

1036
01:20:51,200 --> 01:20:53,880
uair amháin sular fhill sé fíor nó bréagach, ní mór dúinn

1037
01:20:53,880 --> 01:20:57,360
iterate ar ár liosta nasctha agus i gcónaí síos anseo, buille faoi thuairim mé,

1038
01:20:57,360 --> 01:21:03,900
má táimid rth nach bhfuil ceart comhionann le, cuir é, mar sin anois is mian linn go saor in aisce

1039
01:21:03,900 --> 01:21:09,600
rth mar, go maith, raibh muid dearmad go hiomlán mar gheall ar an liosta? Yeah.

1040
01:21:09,600 --> 01:21:12,880
Mar sin, go bhfuil an méid ba mhaith linn a dhéanamh anseo.

1041
01:21:12,880 --> 01:21:16,730
Cá bhfuil an pointeoir?

1042
01:21:16,730 --> 01:21:23,320
Cur bhí ansin - ba mhaith linn a liosta struct ionann * 10 liosta eile.

1043
01:21:23,320 --> 01:21:29,240
Liosta saor in aisce, liosta = teocht.

1044
01:21:29,240 --> 01:21:32,820
Agus i gcás ina ais linn fíor, a dhéanann muid a iterate

1045
01:21:32,820 --> 01:21:37,050
níos mó ná an chuid eile ar ár liosta nasctha rudaí freeing.

1046
01:21:37,050 --> 01:21:39,700
Is é an rud deas mar gheall ar an réiteach athchúrsach rudaí freeing

1047
01:21:39,700 --> 01:21:44,930
ach ciallaíonn factorings popping as an chairn a tharlóidh ar do shon.

1048
01:21:44,930 --> 01:21:50,720
Mar sin, tá muid imithe as rud éigin go bhfuil cosúil le 3 línte crua-le-smaointe faoi chód

1049
01:21:50,720 --> 01:21:57,520
chun rud é go suntasach i bhfad níos mó deacair smaoineamh-faoi líne de chód.

1050
01:21:57,520 --> 01:22:00,620
Aon níos mó ceisteanna?

1051
01:22:00,620 --> 01:22:08,760
Gach ceart. Táimid go maith. Slán!

1052
01:22:08,760 --> 01:22:11,760
[CS50.TV]