1
00:00:00,000 --> 00:00:02,500
[Powered by Google Translate] [Seksyon 7] [Mwens Alèz]

2
00:00:02,500 --> 00:00:04,890
[Nate Hardison] [Inivèsite Harvard]

3
00:00:04,890 --> 00:00:07,000
[Sa a se CS50.] [CS50.TV]

4
00:00:07,000 --> 00:00:09,080
>> Byenveni nan Seksyon 7.

5
00:00:09,080 --> 00:00:11,330
Mèsi a siklòn Sandy,

6
00:00:11,330 --> 00:00:13,440
olye pou yo gen yon seksyon nòmal semèn sa a,

7
00:00:13,440 --> 00:00:17,650
n ap fè sa a mache-a, atravè seksyon an nan kesyon.

8
00:00:17,650 --> 00:00:22,830
Mwen pral yo dwe swiv ansanm ak Pwoblèm nan Fikse 6 Specification,

9
00:00:22,830 --> 00:00:25,650
ak ale atravè tout tout kesyon yo ki nan la

10
00:00:25,650 --> 00:00:27,770
Yon seksyon nan seksyon Kesyon.

11
00:00:27,770 --> 00:00:30,940
Si gen nenpòt kesyon,

12
00:00:30,940 --> 00:00:32,960
tanpri poste sa yo sou CS50 diskite.

13
00:00:32,960 --> 00:00:35,480
>> Byen. Se pou nou jwenn te kòmanse.

14
00:00:35,480 --> 00:00:40,780
Kounye a, m ap gade paj 3 nan Specification a Set Pwoblèm.

15
00:00:40,780 --> 00:00:44,110
Nou pwal premye kòmanse pale osijè pye bwa binè

16
00:00:44,110 --> 00:00:47,850
depi moun ki gen yon anpil nan enpòtans nan seri pwoblèm yo semenn sa a -

17
00:00:47,850 --> 00:00:49,950
kodaj a Tree Huffman.

18
00:00:49,950 --> 00:00:55,000
Youn nan estrikti yo done trè premye nou te pale de sou CS50 te etalaj la.

19
00:00:55,000 --> 00:01:00,170
Sonje ke yon etalaj lan se yon sekans nan eleman -

20
00:01:00,170 --> 00:01:04,019
tout kalite nan menm - ki estoke dwa pwochen nan chak lòt nan memwa.

21
00:01:04,019 --> 00:01:14,420
Si mwen gen yon etalaj nonb antye relatif ki mwen ka trase lè l sèvi avèk sa a style bwat-nimewo-nonm antye relatif -

22
00:01:14,420 --> 00:01:20,290
Se pou nou di mwen gen 5 nan premye bwat la, mwen gen 7 an dezyèm lan,

23
00:01:20,290 --> 00:01:27,760
Lè sa a, mwen gen 8, 10, ak 20 nan ti bwat la final la.

24
00:01:27,760 --> 00:01:33,000
Sonje byen, de la reyèlman bon bagay sou sa a etalaj

25
00:01:33,000 --> 00:01:38,800
yo se ke nou gen aksè sa a konstan-fwa nan nenpòt ki eleman an patikilye

26
00:01:38,800 --> 00:01:40,500
 nan etalaj la si nou konnen endèks li yo.

27
00:01:40,500 --> 00:01:44,670
Pou egzanp, si mwen vle gen tan pwan eleman nan twazyèm nan etalaj la -

28
00:01:44,670 --> 00:01:47,870
nan endèks 2 lè l sèvi avèk sistèm zewo ki baze sou Indexing nou yo -

29
00:01:47,870 --> 00:01:52,220
Mwen literalman jis gen nan fè yon senp kalkil matematik,

30
00:01:52,220 --> 00:01:56,170
hop ak sa yo ki pozisyon nan etalaj la,

31
00:01:56,170 --> 00:01:57,840
rale mete deyò 8 sa a, ki estoke a,

32
00:01:57,840 --> 00:01:59,260
epi mwen bon yo ale.

33
00:01:59,260 --> 00:02:03,350
>> Youn nan bagay ki move sou sa a etalaj - ke nou te pale osijè de

34
00:02:03,350 --> 00:02:05,010
lè nou diskite lye lis -

35
00:02:05,010 --> 00:02:09,120
se ke si mwen vle insert yon eleman nan sa a etalaj,

36
00:02:09,120 --> 00:02:11,090
Mwen pral gen fè kèk déplacement alantou.

37
00:02:11,090 --> 00:02:12,940
Pou egzanp, sa a etalaj dwa isit la

38
00:02:12,940 --> 00:02:16,850
se nan Ranje lòd - Ranje nan lòd moute -

39
00:02:16,850 --> 00:02:19,440
5, Lè sa a, 7, Lè sa a, 8, Lè sa a, 10, ak Lè sa a, 20 -

40
00:02:19,440 --> 00:02:23,100
Men, si mwen vle insert nimewo a 9 nan sa a etalaj,

41
00:02:23,100 --> 00:02:27,460
Mwen pral gen chanjman kèk nan eleman yo nan lòd fè espas.

42
00:02:27,460 --> 00:02:30,440
Nou ka desine sa a soti isit la.

43
00:02:30,440 --> 00:02:35,650
Mwen pral gen pou avanse pou 5 an, 7 la, ak Lè sa a, 8 la;

44
00:02:35,650 --> 00:02:38,720
kreye yon espas kote mwen ka mete 9 la,

45
00:02:38,720 --> 00:02:45,910
ak Lè sa a, 10 ak 20 an ka ale nan a dwat a 9 an.

46
00:02:45,910 --> 00:02:49,450
Sa a se kalite yon doulè paske nan senaryo ki pi mal la-ka -

47
00:02:49,450 --> 00:02:54,350
lè n ap gen yo insert swa nan kòmansman an oswa nan fen a

48
00:02:54,350 --> 00:02:56,040
nan etalaj la, depann sou ki jan n ap déplacement -

49
00:02:56,040 --> 00:02:58,850
nou ta ka fini gen chanjman tout nan eleman yo

50
00:02:58,850 --> 00:03:00,750
kounye a ke nou ap estoke nan etalaj la.

51
00:03:00,750 --> 00:03:03,810
>> Se konsa, sa ki te fason nan alantou sa a?

52
00:03:03,810 --> 00:03:09,260
Fason nan alantou sa a te pou yo ale nan lye-lis metòd nou an kote -

53
00:03:09,260 --> 00:03:19,820
olye pou yo estoke eleman yo 5, 7, 8, 10, ak 20 tout pwochen nan chak lòt nan memwa -

54
00:03:19,820 --> 00:03:25,630
ki sa nou olye t 'te sere yo kalite tout kote nou te vle estoke yo

55
00:03:25,630 --> 00:03:32,470
nan sa yo nœuds lis lye-ki mwen desen soti isit la, kalite komisyon hoc.

56
00:03:32,470 --> 00:03:42,060
Lè sa a, nou konekte yo ansanm lè l sèvi avèk sa yo endikasyon kap vini an.

57
00:03:42,060 --> 00:03:44,370
Mwen ka gen yon konsèy soti nan 5 a 7 an,

58
00:03:44,370 --> 00:03:46,420
yon konsèy, nan lè 7 a 8 an,

59
00:03:46,420 --> 00:03:47,770
yon konsèy de 8 a 10 an,

60
00:03:47,770 --> 00:03:51,220
epi finalman, yon konsèy ki sòti nan 10 a 20 an a,

61
00:03:51,220 --> 00:03:54,880
ak Lè sa a, yon konsèy nil a 20 an ki endike ke pa gen anyen gòch.

62
00:03:54,880 --> 00:03:59,690
Komès-off la nou genyen isit la

63
00:03:59,690 --> 00:04:05,360
se ke kounye a si nou vle insert nimewo a 9 nan Ranje lis nou an,

64
00:04:05,360 --> 00:04:08,270
tout sa nou dwe fè se kreye yon ne nouvo ak 9,

65
00:04:08,270 --> 00:04:12,290
WIRE l 'kanpe nan pwen nan plas la ki apwopriye,

66
00:04:12,290 --> 00:04:20,630
ak Lè sa a, re-fil 8 nan nan pwen desann nan 9 lan.

67
00:04:20,630 --> 00:04:25,660
Sa a se trè vit, an konsideran nou konnen egzakteman ki kote nou vle insert 9 la.

68
00:04:25,660 --> 00:04:32,610
Men, komès-off la an echanj pou sa a se ke nou te kounye a pèdi aksè a konstan-fwa

69
00:04:32,610 --> 00:04:36,230
nan nenpòt ki eleman an patikilye nan estrikti done nou an.

70
00:04:36,230 --> 00:04:40,950
Pou egzanp, si mwen vle jwenn eleman nan katriyèm nan lis sa a lye,

71
00:04:40,950 --> 00:04:43,510
Mwen pral gen kòmanse nan kòmansman la anpil nan lis la

72
00:04:43,510 --> 00:04:48,930
ak travay fason mwen an nan konte ne-pa-ne, jouk tan mwen jwenn youn nan katriyèm.

73
00:04:48,930 --> 00:04:55,870
>> Yo nan lòd yo jwenn pi bon pèfòmans aksè pase yon lis lye -

74
00:04:55,870 --> 00:04:59,360
men tou kenbe kèk nan benefis sa yo ke nou te gen

75
00:04:59,360 --> 00:05:01,800
an tèm de tan ensèsyon-nan yon lis lye -

76
00:05:01,800 --> 00:05:05,750
yon pye bwa binè ki pral bezwen sèvi ak yon ti kras pi plis memwa.

77
00:05:05,750 --> 00:05:11,460
An patikilye, olye pou yo jis yo gen yon konsèy nan yon ne pyebwa binè -

78
00:05:11,460 --> 00:05:13,350
tankou lis la lye-ne fè sa ki -

79
00:05:13,350 --> 00:05:16,950
nou pral ajoute yon konsèy dezyèm ne nan pyebwa binè.

80
00:05:16,950 --> 00:05:19,950
Olye ke sèlman yo gen yon konsèy eleman kap vini an,

81
00:05:19,950 --> 00:05:24,420
nou pwal gen yon konsèy nan yon pitit gòch ak yon timoun dwat.

82
00:05:24,420 --> 00:05:26,560
>> Se pou nou desine yon foto yo wè sa ki ki aktyèlman sanble.

83
00:05:26,560 --> 00:05:31,350
Yon fwa ankò, mwen pral sèvi ak sa yo bwat ak kèk flèch.

84
00:05:31,350 --> 00:05:37,150
Yon ne pyebwa binè pral kòmanse an ak jis nan ti kare yon senp.

85
00:05:37,150 --> 00:05:40,940
Li nan pral gen yon espas pou valè a,

86
00:05:40,940 --> 00:05:47,280
ak Lè sa a, li la tou pral gen yon espas pou timoun nan bò gòch ak pitit la dwat.

87
00:05:47,280 --> 00:05:49,280
Mwen pral mete lejann sou yo isit la.

88
00:05:49,280 --> 00:05:57,560
Nou pral fè timoun nan bò gòch, ak Lè sa a, nou pral kontinye fè timoun nan dwa.

89
00:05:57,560 --> 00:05:59,920
Gen anpil diferan fason pou fè sa.

90
00:05:59,920 --> 00:06:02,050
Pafwa pou espas ak konvenyans,

91
00:06:02,050 --> 00:06:06,460
Mwen pral aktyèlman rale l 'tankou mwen ap fè isit la sou anba a

92
00:06:06,460 --> 00:06:10,910
kote mwen pral gen menm valè a nan tèt la,

93
00:06:10,910 --> 00:06:14,060
ak Lè sa a, timoun nan dwa sou anba dwa-a,

94
00:06:14,060 --> 00:06:16,060
ak timoun nan bò gòch anba bò gòch la.

95
00:06:16,060 --> 00:06:20,250
Ale tounen nan dyagram sa a tèt,

96
00:06:20,250 --> 00:06:22,560
nou gen valè a nan tèt la anpil,

97
00:06:22,560 --> 00:06:25,560
Lè sa a, nou gen konsèy gòch la-pitit, ak Lè sa a, nou gen konsèy nan dwa ak timoun.

98
00:06:25,560 --> 00:06:30,110
>> Nan Specification a Set Pwoblèm,

99
00:06:30,110 --> 00:06:33,110
nou pale sou desen yon ne ki gen yon valè 7,

100
00:06:33,110 --> 00:06:39,750
ak Lè sa a, yon konsèy gòch-timoun ki nil, ak yon konsèy dwat-timoun ki nil.

101
00:06:39,750 --> 00:06:46,040
Nou ka swa ekri nil kapital yo nan espas yo pou

102
00:06:46,040 --> 00:06:51,610
tou de timoun nan bò gòch ak pitit an dwa, oubyen nou ka trase sa a koupe dyagonal

103
00:06:51,610 --> 00:06:53,750
nan chak nan bwat yo pou montre pou ke li nan nil.

104
00:06:53,750 --> 00:06:57,560
Mwen pral fè sa senpleman paske sa a, se pi senp.

105
00:06:57,560 --> 00:07:03,700
Kisa ou wè isit la yo se de fason nan diagramming yon binè ne trè senp pyebwa

106
00:07:03,700 --> 00:07:07,960
kote nou gen valè a 7 ak endikasyon pitit nil.

107
00:07:07,960 --> 00:07:15,220
>> Pati nan dezyèm nan chita pale spesifikasyon nou sou ki jan ak lye lis -

108
00:07:15,220 --> 00:07:18,270
sonje, nou sèlman te gen nan kenbe fèm nan fè eleman an trè premye nan yon lis

109
00:07:18,270 --> 00:07:20,270
sonje lis la tout antye -

110
00:07:20,270 --> 00:07:26,140
ak menm jan an tou, ak yon pyebwa binè, nou gen sèlman yo kenbe fèm nan fè yon sèl konsèy bò pyebwa ki

111
00:07:26,140 --> 00:07:31,120
nan lòd yo kenbe kontwòl sou estrikti nan done tout antye.

112
00:07:31,120 --> 00:07:36,150
Sa a eleman espesyal nan pye bwa a yo rele ne nan rasin nan pyebwa sa a.

113
00:07:36,150 --> 00:07:43,360
Pou egzanp, si sa a ne yon sèl - sa a ne ki gen valè a 7

114
00:07:43,360 --> 00:07:45,500
avèk endikasyon nil gòch-yo ak pitit dwa--

115
00:07:45,500 --> 00:07:47,360
te valè a sèlman nan pyebwa nou yo,

116
00:07:47,360 --> 00:07:50,390
Lè sa a, sa a ta ka ne rasin nou an.

117
00:07:50,390 --> 00:07:52,240
Li nan kòmansman la anpil nan pyebwa nou yo.

118
00:07:52,240 --> 00:07:58,530
Nou ka wè sa a ti kras yon pi klè yon fwa nou kòmanse ajoute plis nœuds bò pyebwa nou yo.

119
00:07:58,530 --> 00:08:01,510
Kite m 'rale moute yon paj nouvo.

120
00:08:01,510 --> 00:08:05,000
>> Koulye a, nou ap ale nan desine yon pye bwa ki gen 7 nan rasin la,

121
00:08:05,000 --> 00:08:10,920
ak 3 andedan timoun nan bò gòch, ak 9 andedan timoun nan dwa.

122
00:08:10,920 --> 00:08:13,500
Yon fwa ankò, sa a se trè senp.

123
00:08:13,500 --> 00:08:26,510
Nou gen 7, trase yon ne pou 3 an, yon ne pou 9,

124
00:08:26,510 --> 00:08:32,150
ak mwen pral mete konsèy gòch la-pitit de 7 a lonje dwèt sou ne la, ki gen 3,

125
00:08:32,150 --> 00:08:37,850
ak konsèy nan dwa-pitit nan ne la, ki gen 7 a ne la, ki gen 9.

126
00:08:37,850 --> 00:08:42,419
Koulye a, depi 3 ak 9 pa gen okenn timoun yo,

127
00:08:42,419 --> 00:08:48,500
nou pwal mete tout endikasyon pitit yo nan pral nil.

128
00:08:48,500 --> 00:08:56,060
Isit la, rasin lan pyebwa nou koresponn ak ne la, ki gen nimewo a 7.

129
00:08:56,060 --> 00:09:02,440
Ou ka wè si tout nou gen se yon konsèy ak sa yo ki ne rasin,

130
00:09:02,440 --> 00:09:07,330
nou ka Lè sa a, mache nan pyebwa nou yo ak jwenn tou de nœuds pitit -

131
00:09:07,330 --> 00:09:10,630
tou de 3 ak 9.

132
00:09:10,630 --> 00:09:14,820
Pa gen bezwen kenbe endikasyon nan chak ne sèl sou pyebwa sa a.

133
00:09:14,820 --> 00:09:22,080
Byen. Koulye a, nou ap ale nan ajoute yon lòt ne dyagram sa a.

134
00:09:22,080 --> 00:09:25,370
Nou pral ajoute yon ne ki gen 6,

135
00:09:25,370 --> 00:09:34,140
e nou pral ajoute sa a kòm timoun nan dwa a ne la, ki gen 3.

136
00:09:34,140 --> 00:09:41,850
Pou fè sa, mwen pral efase ke konsèy nil nan 3 ne la-

137
00:09:41,850 --> 00:09:47,750
ak fil li jiska lonje dwèt sou ne la, ki gen 6. Byen.

138
00:09:47,750 --> 00:09:53,800
>> Nan pwen sa a, se pou yo ale sou yon ti kras nan tèminoloji.

139
00:09:53,800 --> 00:09:58,230
Pou yo kòmanse, rezon ki fè yo rele sa yon pyebwa binè an patikilye

140
00:09:58,230 --> 00:10:00,460
se ke li gen de pwent timoun.

141
00:10:00,460 --> 00:10:06,020
Gen lòt kalite pye bwa ki gen plis endikasyon timoun.

142
00:10:06,020 --> 00:10:10,930
An patikilye, nou te fè yon 'eseye' nan Set Pwoblèm 5.

143
00:10:10,930 --> 00:10:19,310
Ou ap remake ke nan ki eseye, ou te gen 27 endikasyon diferan bay timoun diferan -

144
00:10:19,310 --> 00:10:22,410
yon sèl pou chak nan 26 lèt yo ki nan alfabè a lang angle,

145
00:10:22,410 --> 00:10:25,410
ak Lè sa a, 27th a pou apostwòf la -

146
00:10:25,410 --> 00:10:28,900
se konsa, sa a, se menm jan ak yon kalite pyebwa.

147
00:10:28,900 --> 00:10:34,070
Men, isit la, depi binè li a, nou sèlman gen de pwent timoun.

148
00:10:34,070 --> 00:10:37,880
>> Anplis sa a ne rasin ke nou te pale osijè de,

149
00:10:37,880 --> 00:10:41,470
nou te tou yo te voye bò kote tèm sa a 'timoun ou ye.

150
00:10:41,470 --> 00:10:44,470
Kisa sa vle di pou yon ne yo dwe yon pitit nan yon lòt ne?

151
00:10:44,470 --> 00:10:54,060
Li literalman vle di ke yon ne timoun se yon timoun nan yon lòt ne

152
00:10:54,060 --> 00:10:58,760
si sa ne lòt la gen youn nan pwent pitit li yo mete nan pwen ak sa yo ki ne.

153
00:10:58,760 --> 00:11:01,230
Pou mete sa a nan plis tèm konkrè,

154
00:11:01,230 --> 00:11:11,170
si 3 Yo pwente pa youn nan pwent yo pitit nan 7, lè sa a 3 se yon pitit 7.

155
00:11:11,170 --> 00:11:14,510
Si nou te konnen sa ki timoun yo nan 7 yo se -

156
00:11:14,510 --> 00:11:18,510
byen, nou wè ke 7 an gen yon konsèy nan 3 ak yon konsèy a 9,

157
00:11:18,510 --> 00:11:22,190
Se konsa 9 ak 3 se timoun yo nan 7.

158
00:11:22,190 --> 00:11:26,650
Nèf pa gen okenn timoun yo paske endikasyon pitit li yo ki ap nil,

159
00:11:26,650 --> 00:11:30,940
ak 3 gen sèlman yon timoun, 6.

160
00:11:30,940 --> 00:11:37,430
Sis tou pa gen okenn timoun yo paske tou de pwent li yo ki ap nil, ki nou pral trase kounye a.

161
00:11:37,430 --> 00:11:45,010
>> Anplis de sa, nou menm tou nou pale sou paran yo nan yon ne an patikilye,

162
00:11:45,010 --> 00:11:51,100
ak sa a se, menm jan ou ta atann, reverse sa a deskripsyon timoun.

163
00:11:51,100 --> 00:11:58,620
Chak ne la gen sèlman youn nan paran yo - olye pou yo de kòm ou ta ka atann ak moun.

164
00:11:58,620 --> 00:12:03,390
Pou egzanp, paran an nan 3 se 7.

165
00:12:03,390 --> 00:12:10,800
Paran an nan 9 tou se 7, epi paran an nan 6 se 3. Pa anpil li.

166
00:12:10,800 --> 00:12:15,720
Nou genyen tou tèm pale sou granparan ak pitit pitit,

167
00:12:15,720 --> 00:12:18,210
ak plis ankò jeneralman nou pale de zansèt yo

168
00:12:18,210 --> 00:12:20,960
ak pitit pitit nan yon ne an patikilye.

169
00:12:20,960 --> 00:12:25,710
Zansèt a nan yon ne - oswa zansèt, olye, nan yon ne -

170
00:12:25,710 --> 00:12:32,730
yo tout nan nœuds yo ki kouche sou chemen an soti nan rasin lan ak sa yo ki ne.

171
00:12:32,730 --> 00:12:36,640
Pou egzanp, si m ap gade 6 a ne,

172
00:12:36,640 --> 00:12:46,430
Lè sa a, zansèt yo ap pral fè tou de 3 ak 7.

173
00:12:46,430 --> 00:12:55,310
Zansèt yo nan 9, pou egzanp, se - si m ap gade 9 nan ne -

174
00:12:55,310 --> 00:12:59,990
Lè sa a, zansèt a nan 9 se jis 7.

175
00:12:59,990 --> 00:13:01,940
Ak pitit pitit yo se egzakteman do a.

176
00:13:01,940 --> 00:13:05,430
Si m 'vle fè yon gade nan tout pitit pitit yo nan 7,

177
00:13:05,430 --> 00:13:11,020
Lè sa a, mwen gen fè yon gade nan tout nœuds yo anba li a.

178
00:13:11,020 --> 00:13:16,950
Se konsa, mwen gen 3, 9, ak 6 tout kòm pitit ak pitit pitit 7.

179
00:13:16,950 --> 00:13:24,170
>> Tèm nan final ke nou pral pale sou sa a nosyon ki se yon frè oswa sè.

180
00:13:24,170 --> 00:13:27,980
Frè ak Sè - kalite swiv ansanm sou tèm sa yo fanmi -

181
00:13:27,980 --> 00:13:33,150
yo se nœuds ki nan menm nivo nan pyebwa sa a.

182
00:13:33,150 --> 00:13:42,230
Se konsa,, 3 ak 9 se frè ak sè yo paske yo te nan menm nivo nan pyebwa sa a.

183
00:13:42,230 --> 00:13:46,190
Yo tou de gen paran an menm, 7.

184
00:13:46,190 --> 00:13:51,400
6 la pa gen okenn frè ak sè paske 9 pa gen okenn timoun yo.

185
00:13:51,400 --> 00:13:55,540
Ak 7 pa gen okenn frè ak sè paske li nan rasin nan pyebwa nou yo,

186
00:13:55,540 --> 00:13:59,010
ak gen nan sèlman tout tan 1 rasin.

187
00:13:59,010 --> 00:14:02,260
Pou 7 a gen frè ak sè ke ta dwe gen yon ne pi wo a 7.

188
00:14:02,260 --> 00:14:07,480
Gen ta dwe yon paran nan 7, nan ka sa a 7 pa ta rasin nan pyebwa sa a.

189
00:14:07,480 --> 00:14:10,480
Lè sa a, ki nouvo paran nan 7 ta tou gen gen yon timoun,

190
00:14:10,480 --> 00:14:16,480
e ke pitit ta Lè sa a, dwe frè ak sè a nan 7.

191
00:14:16,480 --> 00:14:21,040
>> Byen. Deplase sou.

192
00:14:21,040 --> 00:14:24,930
Lè nou te kòmanse discussion nou nan pyebwa binè,

193
00:14:24,930 --> 00:14:28,790
nou te pale sou fason nou te ale nan sèvi ak yo nan

194
00:14:28,790 --> 00:14:32,800
jwenn yon avantaj sou tou de ranje e li bay lis lye.

195
00:14:32,800 --> 00:14:37,220
Ak fason an ke nou ap pwal fè sa se ak pwopriyete sa a kòmande.

196
00:14:37,220 --> 00:14:41,080
Nou di ke se yon pye bwa binè te bay lòd, dapre spesifikasyon la,

197
00:14:41,080 --> 00:14:45,740
si pou chak ne nan pyebwa nou yo, tout pitit pitit li yo sou bò gòch la -

198
00:14:45,740 --> 00:14:48,670
timoun nan bò gòch ak tout pitit pitit pitit gòch la a -

199
00:14:48,670 --> 00:14:54,510
gen pi piti valè, ak tout nœuds yo sou bò dwat la -

200
00:14:54,510 --> 00:14:57,770
timoun nan dwa ak tout pitit pitit pitit an dwa a -

201
00:14:57,770 --> 00:15:02,800
gen nœuds pi gran pase valè a ne aktyèl la ke nou ap chèche a.

202
00:15:02,800 --> 00:15:07,850
Jis pou senplisite, nou ap ale nan asime ke pa gen okenn nœuds kopi nan pyebwa nou yo.

203
00:15:07,850 --> 00:15:11,180
Pou egzanp, nan pye bwa sa a nou pa ale fè fas ak ka a

204
00:15:11,180 --> 00:15:13,680
kote nou gen valè a 7 nan rasin lan

205
00:15:13,680 --> 00:15:16,720
 ak Lè sa a, nou menm tou nou gen menm valè a 7 lòt kote nan pyebwa sa a.

206
00:15:16,720 --> 00:15:24,390
Nan ka sa a, ou pral avi ke se pye bwa sa a tout bon òdone.

207
00:15:24,390 --> 00:15:26,510
Nou gen valè a 7 nan rasin lan.

208
00:15:26,510 --> 00:15:29,720
Tout nan kite nan 7 -

209
00:15:29,720 --> 00:15:35,310
si mwen defèt tout moun sa yo mak ti kras isit la -

210
00:15:35,310 --> 00:15:40,450
tout bagay sa yo bò gòch la nan 7 - 3 an ak 6 an -

211
00:15:40,450 --> 00:15:49,410
valè sa yo, yo toulède yo mwens pase 7, ak tout bagay sa yo dwa pou - ki se jis sa a 9 -

212
00:15:49,410 --> 00:15:53,450
se pi gran pase 7.

213
00:15:53,450 --> 00:15:58,650
>> Sa a se pa pye bwa a sèlman te bay lòd ki gen valè sa yo,

214
00:15:58,650 --> 00:16:03,120
Men, kite a trase yon pi plis kèk nan yo.

215
00:16:03,120 --> 00:16:05,030
Gen se aktyèlman yon pakèt antye nan fason ke nou ka fè sa.

216
00:16:05,030 --> 00:16:09,380
Mwen pral sèvi ak yon steno jis kenbe bagay sa senp kote -

217
00:16:09,380 --> 00:16:11,520
olye ke desen soti tout la bwat-ak-flèch -

218
00:16:11,520 --> 00:16:14,220
Mwen jis ale nan trase nimewo yo epi ajoute flèch ki konekte yo.

219
00:16:14,220 --> 00:16:22,920
Pou yo kòmanse, nou pral jis ekri pyebwa orijinal nou an ankò kote nou te gen 7yèm, ak Lè sa a, yon 3,

220
00:16:22,920 --> 00:16:25,590
ak Lè sa a, 3 pwente tounen sou bò dwat la a 6 an,

221
00:16:25,590 --> 00:16:30,890
ak 7 te gen yon pitit dwa sa yo ki te 9.

222
00:16:30,890 --> 00:16:33,860
Byen. Ki sa ki nan yon lòt fason ke nou ta ka ekri pye bwa sa a?

223
00:16:33,860 --> 00:16:38,800
Olye pou yo gen 3 dwe timoun nan gòch nan 7,

224
00:16:38,800 --> 00:16:41,360
nou ta ka tou gen 6 a rete toujou la timoun nan gòch nan 7,

225
00:16:41,360 --> 00:16:44,470
ak Lè sa a, 3 pou timoun nan bò gòch nan 6 a.

226
00:16:44,470 --> 00:16:48,520
Sa ta sanble pye bwa sa a isit la kote mwen te gen 7,

227
00:16:48,520 --> 00:16:57,860
Lè sa a, 6, Lè sa a, 3, ak yon 9 sou bò dwat la.

228
00:16:57,860 --> 00:17:01,490
Nou menm tou nou pa bezwen gen 7 kòm ne rasin nou an.

229
00:17:01,490 --> 00:17:03,860
Nou ta ka tou gen 6 kòm ne rasin nou an.

230
00:17:03,860 --> 00:17:06,470
Ki sa ki ta ki sanble?

231
00:17:06,470 --> 00:17:09,230
Si nou ap ale nan kenbe pwopriyete sa a te bay lòd,

232
00:17:09,230 --> 00:17:12,970
tout bagay sa yo bò gòch la nan 6 la gen li dwe mwens pase l '.

233
00:17:12,970 --> 00:17:16,540
Genyen sèlman yon sèl posiblite, ak sa a, se 3.

234
00:17:16,540 --> 00:17:19,869
Men, Lè sa a, kòm timoun nan dwa a 6, nou gen de posiblite yo.

235
00:17:19,869 --> 00:17:25,380
Premyèman, nou te kapab gen 7 an ak Lè sa a, 9 la,

236
00:17:25,380 --> 00:17:28,850
oubyen nou te kapab rale l '- tankou m pral fè isit la -

237
00:17:28,850 --> 00:17:34,790
kote nou gen 9 an kòm timoun nan dwa nan 6 a,

238
00:17:34,790 --> 00:17:39,050
ak Lè sa a, 7 an kòm timoun nan bò gòch nan 9 lan.

239
00:17:39,050 --> 00:17:44,240
>> Koulye a, 7 ak 6 yo pa valè yo sèlman posib pou rasin lan.

240
00:17:44,240 --> 00:17:50,200
Nou ta ka tou gen 3 fèt nan rasin lan.

241
00:17:50,200 --> 00:17:52,240
Kisa kap rive si 3 se nan rasin lan?

242
00:17:52,240 --> 00:17:54,390
Isit la, bagay sa yo jwenn yon ti jan ki enteresan.

243
00:17:54,390 --> 00:17:58,440
Twa pa gen okenn valè ki pi piti pase li,

244
00:17:58,440 --> 00:18:02,070
pou ke tout bò gòch nan pyebwa a se jis ale nan pral nil.

245
00:18:02,070 --> 00:18:03,230
Gen pa k ap pase yo dwe anyen la.

246
00:18:03,230 --> 00:18:07,220
Sou bò dwat la, nou te kapab lis bagay sa yo nan moute lòd.

247
00:18:07,220 --> 00:18:15,530
Nou te kapab gen 3, Lè sa a, 6, Lè sa a, 7, Lè sa a, 9.

248
00:18:15,530 --> 00:18:26,710
Oswa, nou ta ka fè 3, Lè sa a, 6, Lè sa a, 9, Lè sa a, 7.

249
00:18:26,710 --> 00:18:35,020
Oswa, nou ta ka fè 3, Lè sa a, 7, Lè sa a, 6, Lè sa a, 9.

250
00:18:35,020 --> 00:18:40,950
Oswa, 3, 7 - aktyèlman pa gen okenn, nou pa kapab fè yon 7 ankò.

251
00:18:40,950 --> 00:18:43,330
Sa a se yon bagay nou la.

252
00:18:43,330 --> 00:18:54,710
Nou ka fè 9, ak Lè sa a, soti nan 9 a nou ka fè 6 ak Lè sa a, 7.

253
00:18:54,710 --> 00:19:06,980
Oswa, nou ka fè 3, Lè sa a, 9, Lè sa a, 7yèm, ak Lè sa a, 6.

254
00:19:06,980 --> 00:19:12,490
>> Youn nan bagay trase atansyon ou a isit la se

255
00:19:12,490 --> 00:19:14,510
ke sa yo pye bwa yo se yon ti kras etranj-ap chèche.

256
00:19:14,510 --> 00:19:17,840
An patikilye, si nou gade nan 4 pyebwa yo sou bò dwat la -

257
00:19:17,840 --> 00:19:20,930
Mwen pral sèkle yo, isit la -

258
00:19:20,930 --> 00:19:28,410
pyebwa sa yo gade prèske egzakteman menm jan ak yon lis lye.

259
00:19:28,410 --> 00:19:32,670
Chak ne la gen sèlman yon timoun,

260
00:19:32,670 --> 00:19:38,950
epi pou nou pa gen nenpòt nan estrikti sa a pye bwa-tankou sa nou wè, pou egzanp,

261
00:19:38,950 --> 00:19:44,720
 nan yon sèl sa a pye bwa Lone sou isit la sou bò gòch anba a.

262
00:19:44,720 --> 00:19:52,490
Pyebwa sa yo yo aktyèlman rele bonjan pyebwa binè,

263
00:19:52,490 --> 00:19:54,170
epi n ap pale sou sa yo plis nan lavni an -

264
00:19:54,170 --> 00:19:56,730
espesyalman si ou ale nan pran kou lòt syans òdinatè.

265
00:19:56,730 --> 00:19:59,670
Pyebwa sa yo se bonjan.

266
00:19:59,670 --> 00:20:03,780
Yo ap pa trè itil paske, tout bon, estrikti sa a prèt tèt li

267
00:20:03,780 --> 00:20:08,060
 Passage fwa menm jan ak sa yon lis lye.

268
00:20:08,060 --> 00:20:13,050
Nou pa pran pran avantaj nan memwa siplemantè a - sa a konsèy siplemantè -

269
00:20:13,050 --> 00:20:18,840
paske nan estrikti nou an ke yo te move nan fason sa.

270
00:20:18,840 --> 00:20:24,700
Olye de ale sou yo ak sou trase soti pyebwa yo binè ki gen 9 nan rasin la,

271
00:20:24,700 --> 00:20:27,220
ki se ka a final ke nou ta genyen,

272
00:20:27,220 --> 00:20:32,380
nou ap olye de sa, nan pwen sa a, pral pale yon ti kras sou tèm sa a lòt

273
00:20:32,380 --> 00:20:36,150
ke nou itilize lè w ap pale sou pye bwa, ki te rele wotè a.

274
00:20:36,150 --> 00:20:45,460
>> Wotè nan yon pyebwa se distans ki soti nan rasin nan ne la ki pi-byen lwen,

275
00:20:45,460 --> 00:20:48,370
ou pito ki kantite so ke ou ta gen fè yo nan lòd yo

276
00:20:48,370 --> 00:20:53,750
kòmanse soti nan rasin lan ak Lè sa a, fini nan ne la ki pi-byen lwen nan pyebwa sa a.

277
00:20:53,750 --> 00:20:57,330
Si nou gade nan kèk nan pyebwa sa yo ke nou te trase dwa isit la,

278
00:20:57,330 --> 00:21:07,870
nou ka wè ke si nou pran pye bwa sa a nan kwen gòch anwo ak nou kòmanse a 3 an,

279
00:21:07,870 --> 00:21:14,510
Lè sa a, nou gen fè 1 hop pou li ale nan 6 an, yon hop dezyèm pou li ale nan 7 la,

280
00:21:14,510 --> 00:21:20,560
ak yon hop twazyèm pou li ale nan 9 lan.

281
00:21:20,560 --> 00:21:26,120
Se konsa, wotè a nan pyebwa sa a se 3.

282
00:21:26,120 --> 00:21:30,640
Nou ka fè egzèsis an menm pou pyebwa yo lòt souliye ak sa-a vèt,

283
00:21:30,640 --> 00:21:40,100
e nou wè ke wotè nan tout moun sa yo pyebwa tou se tout bon 3.

284
00:21:40,100 --> 00:21:45,230
Sa a se yon pati nan sa ki fè yo bonjan -

285
00:21:45,230 --> 00:21:53,750
ki wotè yo se jis yon pi piti pase kantite nœuds nan pyebwa a tout antye.

286
00:21:53,750 --> 00:21:58,400
Si nou gade nan pye bwa sa a lòt ki nan antoure ak wouj, sou la lòt bò,

287
00:21:58,400 --> 00:22:03,920
nou wè ke nœuds yo fèy pi-byen lwen yo se 6 la ak 9 la -

288
00:22:03,920 --> 00:22:06,940
kite a ke yo te sa yo nœuds ke pa gen okenn timoun yo.

289
00:22:06,940 --> 00:22:11,760
Se konsa, nan lòd jwenn soti nan ne an rasin swa 6 a oswa 9 la,

290
00:22:11,760 --> 00:22:17,840
nou dwe fè yon sèl hop pou li ale nan 7 a ak Lè sa a, yon hop dezyèm pou li ale nan 9 la,

291
00:22:17,840 --> 00:22:21,240
ak menm jan an tou, se sèlman yon hop dezyèm, nan lè 7 a pou li ale nan 6 a.

292
00:22:21,240 --> 00:22:29,080
Se konsa, wotè a nan pyebwa sa a sou isit la se sèlman 2.

293
00:22:29,080 --> 00:22:35,330
Ou ka ale retounen lakay yo epi fè sa pou tout nan pyebwa yo, lòt ke nou te diskite anvan

294
00:22:35,330 --> 00:22:37,380
kòmanse ak 7 an ak 6 an,

295
00:22:37,480 --> 00:22:42,500
epi ou ap jwenn ki wotè nan tout nan tout sa yo pyebwa tou se 2.

296
00:22:42,500 --> 00:22:46,320
>> Rezon ki fè nou ve yo te ap pale de bay lòd pyebwa binè

297
00:22:46,320 --> 00:22:50,250
epi poukisa yo ap fre a se paske ou kapab fè rechèch nan yo nan

298
00:22:50,250 --> 00:22:53,810
yon fason anpil menm jan ak chèche sou yon etalaj Ranje.

299
00:22:53,810 --> 00:22:58,720
Sa a se kote nou pale sou kesyon pran tan sa a Passage amelyore

300
00:22:58,720 --> 00:23:02,730
sou senp lis la lye.

301
00:23:02,730 --> 00:23:05,010
Avèk yon lis lye - si ou vle jwenn yon eleman an patikilye -

302
00:23:05,010 --> 00:23:07,470
w ap nan pi bon pral fè kèk sòt de rechèch lineyè

303
00:23:07,470 --> 00:23:10,920
ki kote ou kòmanse nan kòmansman an nan yon lis ak hop youn-pa-youn -

304
00:23:10,920 --> 00:23:12,620
yon sèl ne pa youn ne -

305
00:23:12,620 --> 00:23:16,060
nan lis la tout antye jiskaske ou jwenn kèlkeswa sa w ap chèche pou.

306
00:23:16,060 --> 00:23:19,440
Lè nou konsidere ke, si ou gen yon pye bwa binè ki nan ki estoke nan fòma sa a bèl,

307
00:23:19,440 --> 00:23:23,300
ou ka aktyèlman jwenn plis nan yon rechèch binè ale sou

308
00:23:23,300 --> 00:23:25,160
ki kote ou separe ak konkeri

309
00:23:25,160 --> 00:23:29,490
ak rechèch nan mwatye ki apwopriye a nan pye bwa a nan chak etap.

310
00:23:29,490 --> 00:23:32,840
Ann gade pou wè ki jan sa travay.

311
00:23:32,840 --> 00:23:38,850
>> Si nou gen - ankò, pral tounen nan pyebwa orijinal nou yo -

312
00:23:38,850 --> 00:23:46,710
nou kòmanse a 7, nou gen 3 sou bò gòch la, 9 sou bò dwat la,

313
00:23:46,710 --> 00:23:51,740
ak anba 3 a nou gen 6 an.

314
00:23:51,740 --> 00:24:01,880
Si nou vle pou fè rechèch pou nimewo 6 la nan pye bwa sa a, nou ta kòmanse nan rasin lan.

315
00:24:01,880 --> 00:24:08,910
Nou ta konpare valè an ke nou ap chèche pou yo, di, 6,

316
00:24:08,910 --> 00:24:12,320
valè a ki estoke nan ne an ke nou ap kounye a chèche a, 7,

317
00:24:12,320 --> 00:24:21,200
jwenn ke 6 se vre mwens pase 7, se konsa nou ta deplase li nan yon bò gòch li.

318
00:24:21,200 --> 00:24:25,530
Si te valè a nan 6 te pi gran pase 7, nou ta gen olye demenaje ale rete nan bò dwat la.

319
00:24:25,530 --> 00:24:29,770
Depi nou konnen ke - akòz estrikti nan te bay lòd pyebwa binè nou yo -

320
00:24:29,770 --> 00:24:33,910
tout valè yo a mwens pase 7 yo ale nan dwe estoke nan kite nan 7,

321
00:24:33,910 --> 00:24:40,520
gen nan pa gen bezwen menm bezwen deranje kap nan bò dwat la pyebwa sa a.

322
00:24:40,520 --> 00:24:43,780
Yon fwa nou deplase a gòch la ak nou ap kounye a nan ne la, ki gen 3,

323
00:24:43,780 --> 00:24:48,110
nou ka fè sa konparezon menm ankò kote nou konpare 3 an ak 6 an.

324
00:24:48,110 --> 00:24:52,430
Ak nou jwenn ke pandan y ap 6 - valè a nou ap chèche pou - se pi plis pase 3,

325
00:24:52,430 --> 00:24:58,580
nou ka ale nan bò dwat la ne la, ki gen 3.

326
00:24:58,580 --> 00:25:02,670
Gen nan pa gen bò gòch isit la, se konsa nou te ka genyen inyore sa.

327
00:25:02,670 --> 00:25:06,510
Men, nou ka konnen sèlman ke paske nou menm nou ap chèche nan pye bwa a li menm,

328
00:25:06,510 --> 00:25:08,660
epi nou ka wè ke pyebwa a pa gen okenn timoun yo.

329
00:25:08,660 --> 00:25:13,640
>> Li la tou trè fasil yo gade jiska 6 an pye bwa sa a si n ap fè li tèt nou kòm moun,

330
00:25:13,640 --> 00:25:16,890
Men, kite a swiv pwosesis sa a mekanikman tankou yon òdinatè ta fè

331
00:25:16,890 --> 00:25:18,620
reyèlman konprann algorithm a.

332
00:25:18,620 --> 00:25:26,200
Nan pwen sa a, nou ap kounye a kap nan yon ne ki gen 6,

333
00:25:26,200 --> 00:25:29,180
epi nou ap chèche pou valè a 6,

334
00:25:29,180 --> 00:25:31,740
se konsa, vrèman vre, nou te jwenn ne ki apwopriye a.

335
00:25:31,740 --> 00:25:35,070
Nou jwenn valè a 6 nan pyebwa nou, epi nou ka sispann rechèch nou an.

336
00:25:35,070 --> 00:25:37,330
Nan pwen sa a, depann sou sa ki ap pase,

337
00:25:37,330 --> 00:25:41,870
nou ka di, wi, nou te jwenn valè a 6, li egziste nan pyebwa nou yo.

338
00:25:41,870 --> 00:25:47,640
Oswa, si nou ap planifye yo insert yon ne oswa fè yon bagay, nou ka fè sa nan pwen sa.

339
00:25:47,640 --> 00:25:53,010
>> Se pou nou fè yon koup plis rchèrch jis yo wè ki jan sa a travay.

340
00:25:53,010 --> 00:25:59,390
Se pou yo gade nan ki sa ki rive si nou te eseye ak gade moute valè a 10.

341
00:25:59,390 --> 00:26:02,970
Si nou te yo gade jiska valè a 10, nou ta kòmanse nan rasin lan.

342
00:26:02,970 --> 00:26:07,070
Nou ta wè ke 10 se pi gran pase 7, se konsa nou ta deplase a dwat la.

343
00:26:07,070 --> 00:26:13,640
Nou ta jwenn a 9 la epi konpare 9 a 10 an ak wè ke 9 se vre mwens pase 10.

344
00:26:13,640 --> 00:26:16,210
Se konsa, ankò, nou ta eseye pou avanse pou pi a dwat la.

345
00:26:16,210 --> 00:26:20,350
Men, nan pwen sa a, nou ta remake ke nou ap nan yon ne nil.

346
00:26:20,350 --> 00:26:23,080
Pa gen anyen la a. Pa gen anyen ki kote 10 nan yo ta dwe.

347
00:26:23,080 --> 00:26:29,360
Sa a se kote nou ka rapòte echèk - ke gen se vre pa gen okenn 10 nan pyebwa sa a.

348
00:26:29,360 --> 00:26:35,420
Epi finalman, se pou yo ale nan ka a kote nou ap eseye yo gade jiska 1 nan pyebwa sa a.

349
00:26:35,420 --> 00:26:38,790
Sa a se menm jan ak sa k ap pase si nou gade moute 10, eksepte olye pou yo ale sou bò dwat la,

350
00:26:38,790 --> 00:26:41,260
nou pral pou yo ale nan bò gòch li.

351
00:26:41,260 --> 00:26:46,170
Nou kòmanse nan 7 a ak wè ke 1 se mwens pase 7, konsa nou deplase li nan yon bò gòch li.

352
00:26:46,170 --> 00:26:51,750
Nou jwenn nan 3 a ak wè ke 1 se mwens pase 3, kifè, ankò nou eseye pou yo avanse pou bò gòch li.

353
00:26:51,750 --> 00:26:59,080
Nan pwen sa a nou gen yon ne nil, se konsa ankò nou ka rapòte echèk.

354
00:26:59,080 --> 00:27:10,260
>> Si ou vle aprann plis sou pye bwa binè,

355
00:27:10,260 --> 00:27:14,420
gen tout yon seri nan pwoblèm plezi ti kras ke ou ka fè avèk yo.

356
00:27:14,420 --> 00:27:19,450
Mwen sijere pratike desen an soti nan dyagram sa yo youn-pa-youn

357
00:27:19,450 --> 00:27:21,910
epi suiv nan tout etap yo diferan,

358
00:27:21,910 --> 00:27:25,060
paske sa a ap vini nan super sou la men-

359
00:27:25,060 --> 00:27:27,480
pa sèlman lè w ap fè kodaj mete nan pwoblèm Huffman

360
00:27:27,480 --> 00:27:29,390
men tou nan kou lavni -

361
00:27:29,390 --> 00:27:32,220
jis pou aprann jan pou trase soti estrikti sa yo done ak panse atravè pwoblèm yo

362
00:27:32,220 --> 00:27:38,000
yo ak plim ak papye, oubyen, nan ka sa a, iPad ak dyaman.

363
00:27:38,000 --> 00:27:41,000
>> Nan pwen sa a menm si, nou pral pou avanse pou sou fè kèk pratik kodaj

364
00:27:41,000 --> 00:27:44,870
ak aktyèlman jwe ak pyebwa sa yo binè ak wè.

365
00:27:44,870 --> 00:27:52,150
Mwen pral chanje tounen sou nan òdinatè mwen an.

366
00:27:52,150 --> 00:27:58,480
Pou pati sa a nan seksyon an, olye pou yo lè l sèvi avèk CS50 Run oswa CS50 Espas,

367
00:27:58,480 --> 00:28:01,500
Mwen pral sèvi ak aparèy la.

368
00:28:01,500 --> 00:28:04,950
>> Apre ansanm ak spesifikasyon la Set Pwoblèm,

369
00:28:04,950 --> 00:28:07,740
Mwen wè ke mwen sipoze louvri moute aparèy la,

370
00:28:07,740 --> 00:28:11,020
ale nan folder Dropbox m 'yo, kreye yon folder rele Seksyon 7,

371
00:28:11,020 --> 00:28:15,730
ak Lè sa a, kreye yon dosye rele binary_tree.c.

372
00:28:15,730 --> 00:28:22,050
Isit la nou ale. Mwen te gen aparèy la deja louvri.

373
00:28:22,050 --> 00:28:25,910
Mwen pral rale moute yon tèminal.

374
00:28:25,910 --> 00:28:38,250
Mwen pral pou yo ale nan folder nan Dropbox, fè yon anyè rele section7,

375
00:28:38,250 --> 00:28:42,230
epi wè li nan totalman vid.

376
00:28:42,230 --> 00:28:48,860
Koulye a, mwen pral louvri moute binary_tree.c.

377
00:28:48,860 --> 00:28:51,750
Byen. Isit la nou ale - vid dosye-a.

378
00:28:51,750 --> 00:28:54,330
>> Se pou nou tounen nan spesifikasyon la.

379
00:28:54,330 --> 00:28:59,850
Spesifikasyon la mande yo kreye yon definisyon kalite nouvo

380
00:28:59,850 --> 00:29:03,080
pou yon ne pyebwa binè ki gen valè Int -

381
00:29:03,080 --> 00:29:07,110
jis tankou valè sa yo ke nou te trase soti nan diagramming nou an avan.

382
00:29:07,110 --> 00:29:11,740
Nou pral itilize sa a boilerplate tipedèf ke nou te fè isit la

383
00:29:11,740 --> 00:29:14,420
ke ou ta dwe rekonèt nan Set Pwoblèm 5 -

384
00:29:14,420 --> 00:29:19,190
si ou te fè wout la tab regle nan viktwa pwogram nan ortograf.

385
00:29:19,190 --> 00:29:22,540
Ou ta dwe tou rekonèt li nan seksyon semèn pase a nan

386
00:29:22,540 --> 00:29:23,890
kote nou te pale osijè de lye lis.

387
00:29:23,890 --> 00:29:27,870
Nou gen sa a tipedèf nan yon ne struct,

388
00:29:27,870 --> 00:29:34,430
e nou te bay sa a ne struct non sa a ne struct davans

389
00:29:34,430 --> 00:29:39,350
pou nou ka Lè sa a, gade nan li depi nou pral vle gen endikasyon ne struct

390
00:29:39,350 --> 00:29:45,740
kòm yon pati nan struct nou an, men nou te Lè sa a, antoure sa a -

391
00:29:45,740 --> 00:29:47,700
ou pito, fèmen sa a - nan yon tipedèf

392
00:29:47,700 --> 00:29:54,600
pou ke, pita nan kòd la, nou ka al gade nan sa a struct kòm jis ne yon olye de yon ne struct.

393
00:29:54,600 --> 00:30:03,120
>> Sa a se pral fè anpil menm jan ak definisyon an lis separeman ki lye ak ke nou te wè semèn pase a.

394
00:30:03,120 --> 00:30:20,070
Pou fè sa, kite la jis kòmanse pa ekri soti boilerplate la.

395
00:30:20,070 --> 00:30:23,840
Nou konnen nou gen gen yon valè nonb antye relatif,

396
00:30:23,840 --> 00:30:32,170
se konsa nou pral mete an valè Int, ak Lè sa a, olye pou yo gen sèlman yon sèl konsèy eleman nan pwochen -

397
00:30:32,170 --> 00:30:33,970
tankou nou te fè ak separeman ki lye ak lis -

398
00:30:33,970 --> 00:30:38,110
nou pwal gen endikasyon kite la ak dwa timoun.

399
00:30:38,110 --> 00:30:42,880
Sa a se trè senp twò - struct ne pitit * gòch;

400
00:30:42,880 --> 00:30:51,190
ak struct ne * dwa timoun;. Fre.

401
00:30:51,190 --> 00:30:54,740
Ki sanble yon kòmansman trè bon.

402
00:30:54,740 --> 00:30:58,530
Se pou nou tounen nan spesifikasyon la.

403
00:30:58,530 --> 00:31:05,030
>> Koulye a, nou bezwen deklare yon ne mondyal varyab * pou rasin lan yon pye bwa.

404
00:31:05,030 --> 00:31:10,590
Nou pwal fè sa a mondyal jis tankou nou te fè premye konsèy nan lye lis nou an tou mondyal.

405
00:31:10,590 --> 00:31:12,690
Sa a te tèlman ke nan fonksyon sa yo ke nou ekri

406
00:31:12,690 --> 00:31:16,180
nou pa gen kenbe pase alantou sa a rasin -

407
00:31:16,180 --> 00:31:19,620
menm si nou pral wè ke si ou fè vle ekri sa yo fonksyon recursive,

408
00:31:19,620 --> 00:31:22,830
li ta ka pi bon pa menm pase l 'nan kòm yon mondyal an plas an premye

409
00:31:22,830 --> 00:31:28,090
ak olye inisyalize li lokalman nan fonksyon prensipal ou an.

410
00:31:28,090 --> 00:31:31,960
Men, nou pwal fè li globalman yo kòmanse.

411
00:31:31,960 --> 00:31:39,920
Yon fwa ankò, nou pral bay yon koup la espas, ak mwen pral deklare yon rasin * ne.

412
00:31:39,920 --> 00:31:46,770
Jis asire w ke mwen pa kite sa-a uninitialized, mwen pral mete l 'egal a nil.

413
00:31:46,770 --> 00:31:52,210
Koulye a, nan fonksyon prensipal - ki nou pral ekri vrèman byen vit dwa isit la -

414
00:31:52,210 --> 00:32:00,450
int prensipal (Int arg, Konstitisyon Char * argv []) -

415
00:32:00,450 --> 00:32:10,640
ak mwen pral kòmanse deklare etalaj argv mwen kòm Konstitisyon jis pou m 'konnen

416
00:32:10,640 --> 00:32:14,550
ki sa yo agiman yo se agiman ke mwen pwobableman pa vle modifye.

417
00:32:14,550 --> 00:32:18,390
Si m 'vle li modifye yo mwen ta pwobableman ap fè kopi yo.

418
00:32:18,390 --> 00:32:21,740
Ou pral wè sa a yon anpil nan kòd.

419
00:32:21,740 --> 00:32:25,440
Li nan amann swa fason. Li nan amann yo kite li kòm - retire okenn pati konstitisyon an si ou ta renmen.

420
00:32:25,440 --> 00:32:28,630
Mwen tipikman mete l 'nan jis pou m' fè sonje tèt mwen

421
00:32:28,630 --> 00:32:33,650
 ke mwen pwobableman pa vle modifye sa yo agiman.

422
00:32:33,650 --> 00:32:39,240
>> Kòm toujou, mwen pral gen ladan yo sa a retou 0 liy nan fen prensipal la.

423
00:32:39,240 --> 00:32:45,730
Isit la, mwen pral inisyalize ne rasin m 'yo.

424
00:32:45,730 --> 00:32:48,900
Kòm li vle di kounye a, mwen te gen yon konsèy ki nan mete nil,

425
00:32:48,900 --> 00:32:52,970
Se konsa, li lonje dwèt nan pa gen anyen.

426
00:32:52,970 --> 00:32:57,480
Yo nan lòd yo aktyèlman kòmanse bati ne la,

427
00:32:57,480 --> 00:32:59,250
M 'premye bezwen asiyen memwa pou li a.

428
00:32:59,250 --> 00:33:05,910
Mwen pral fè sa pa fè memwa sou pil wòch la lè l sèvi avèk malok.

429
00:33:05,910 --> 00:33:10,660
Mwen pral mete rasin egal a rezilta a nan malok,

430
00:33:10,660 --> 00:33:19,550
ak mwen pral sèvi ak operatè a sizof kalkile gwosè a nan yon ne.

431
00:33:19,550 --> 00:33:24,990
Rezon ki fè mwen sèvi ak sizof ne kòm opoze a, di,

432
00:33:24,990 --> 00:33:37,020
fè yon bagay tankou sa a - malok (4 + 4 +4) oswa malok 12 -

433
00:33:37,020 --> 00:33:40,820
se paske mwen vle kòd mwen yo dwe kòm konpatib ke posib.

434
00:33:40,820 --> 00:33:44,540
Mwen vle pou kapab pran sa a. C ranpli, konpile l 'sou aparèy la,

435
00:33:44,540 --> 00:33:48,820
epi konpile l 'sou 64-bit Mac mwen an -

436
00:33:48,820 --> 00:33:52,040
oswa sou yon achitekti konplètman diferan -

437
00:33:52,040 --> 00:33:54,640
e mwen vle sa a tout moun nan travay menm bagay la.

438
00:33:54,640 --> 00:33:59,510
>> Si mwen fè panse de gwosè a nan varyab -

439
00:33:59,510 --> 00:34:02,070
gwosè a nan yon int oswa gwosè a nan yon konsèy -

440
00:34:02,070 --> 00:34:06,070
Lè sa a, mwen tou fè sipozisyon sou kalite ki nan architectures

441
00:34:06,070 --> 00:34:10,440
ki te sou kòd mwen ka avèk siksè konpile lè kouri.

442
00:34:10,440 --> 00:34:15,030
Toujou itilize sizof tankou yo te opoze a manuelman adisyon jaden yo struct.

443
00:34:15,030 --> 00:34:20,500
Rezon ki fè lòt la se ke gen ta ka tou pou kouvèti ki du a mete nan struct la.

444
00:34:20,500 --> 00:34:26,570
Menm jis adisyon jaden yo endividyèl se pa yon bagay ke ou tipikman vle fè a,

445
00:34:26,570 --> 00:34:30,340
se konsa, efase ke liy.

446
00:34:30,340 --> 00:34:33,090
Koulye a, reyèlman inisyalize sa a ne rasin,

447
00:34:33,090 --> 00:34:36,489
Mwen pral oblije ploge nan valè pou chak nan jaden diferan li yo.

448
00:34:36,489 --> 00:34:41,400
Pou egzanp, pou valè Mwen konnen mwen vle inisyalize a 7,

449
00:34:41,400 --> 00:34:46,920
ak pou kounye a mwen pral mete timoun nan bò gòch yo dwe nil

450
00:34:46,920 --> 00:34:55,820
ak pitit an dwa tou pral nil. Gwo!

451
00:34:55,820 --> 00:35:02,670
Nou te fè pati sa a nan espèk a.

452
00:35:02,670 --> 00:35:07,390
>> Spesifikasyon la desann nan fon an nan paj 3 mande m 'yo kreye twa plis nœuds -

453
00:35:07,390 --> 00:35:10,600
yon sèl ki gen 3, yon sèl ki gen 6, ak yon sèl ak 9 -

454
00:35:10,600 --> 00:35:14,210
ak Lè sa a, fil elektrik yo moute pou li sanble egzakteman menm jan ak dyagram pyebwa nou

455
00:35:14,210 --> 00:35:17,120
ke nou te pale de deja a.

456
00:35:17,120 --> 00:35:20,450
Se pou nou fè sa byen vit isit la.

457
00:35:20,450 --> 00:35:26,270
Ou pral wè vrèman byen vit ke mwen pral kòmanse ekri yon pakèt moun sou kòd kopi.

458
00:35:26,270 --> 00:35:32,100
Mwen pral kreye yon * ne ak mwen pral rele li twa.

459
00:35:32,100 --> 00:35:36,000
Mwen pral mete l 'egal a malok (sizof (ne)).

460
00:35:36,000 --> 00:35:41,070
Mwen pral mete twa-> valè = 3.

461
00:35:41,070 --> 00:35:54,780
Twa -> left_child = nil; twa -> dwa _child = nil; kòm byen.

462
00:35:54,780 --> 00:36:01,150
Ki sanble trè sanblab yo inisyalizin rasin lan, ak sa a, se ekzakteman ki sa

463
00:36:01,150 --> 00:36:05,760
Mwen pral oblije fè si mwen kòmanse inisyalizin 6 ak 9 kòm byen.

464
00:36:05,760 --> 00:36:20,720
M pral fè sa vrèman byen vit isit la - aktyèlman, mwen pral fè yon kopi ti kras ak keratin,

465
00:36:20,720 --> 00:36:46,140
ak asire w ke mwen - byen.

466
00:36:46,470 --> 00:37:09,900
 Koulye a, mwen te gen li kopye e mwen ka ale pi devan epi mete sa egal a 6.

467
00:37:09,900 --> 00:37:14,670
Ou ka wè ke sa a pran ti tan epi li pa super-efikas.

468
00:37:14,670 --> 00:37:22,610
Nan jis ti jan yon ti kras, nou pral ekri yon fonksyon ki pral fè sa a pou nou.

469
00:37:22,610 --> 00:37:32,890
Mwen vle ranplase sa a ak yon 9, ranplase sa ki gen yon 6.

470
00:37:32,890 --> 00:37:37,360
>> Koulye a, nou te gen tout nœuds nou kreye epi inisyalizèd.

471
00:37:37,360 --> 00:37:41,200
Nou gen rasin nou mete egal a 7, oswa ki gen valè a 7,

472
00:37:41,200 --> 00:37:46,510
ne nou ki gen 3, ne nou ki gen 6, epi ne nou ki gen 9.

473
00:37:46,510 --> 00:37:50,390
Nan pwen sa a, tout sa nou dwe fè se tout bagay fil leve.

474
00:37:50,390 --> 00:37:53,020
Rezon ki fè mwen inisyalizèd tout endikasyon yo nan nil se jis pou m 'fè si ke

475
00:37:53,020 --> 00:37:56,260
Mwen pa gen okenn endikasyon uninitialized an gen pa aksidan.

476
00:37:56,260 --> 00:38:02,290
Epi tou li depi, nan pwen sa a, mwen gen sèlman yo aktyèlman konekte nœuds yo nan chak lòt -

477
00:38:02,290 --> 00:38:04,750
nan sa yo ke yo ap aktyèlman konekte nan - Mwen pa gen yo ale nan, epi fè

478
00:38:04,750 --> 00:38:08,240
asire w ke tout nulls yo se nan la nan kote ki apwopriye yo.

479
00:38:08,240 --> 00:38:15,630
>> Kòmanse nan rasin lan, mwen konnen ke pitit gòch rasin lan se 3.

480
00:38:15,630 --> 00:38:21,250
Mwen konnen ke pitit dwa rasin lan a se 9.

481
00:38:21,250 --> 00:38:24,880
Apre sa, se sèlman lòt timoun nan ke mwen te kite enkyete sou

482
00:38:24,880 --> 00:38:39,080
se pitit dwa 3 a, ki se 6.

483
00:38:39,080 --> 00:38:44,670
Nan pwen sa a, li tout sanble trè bon.

484
00:38:44,670 --> 00:38:54,210
Nou pral efase kèk nan liy sa yo.

485
00:38:54,210 --> 00:38:59,540
Koulye a, tout bagay sanble trè bon.

486
00:38:59,540 --> 00:39:04,240
Se pou nou tounen nan spesifikasyon nou yo ak wè sa ki nou gen yo dwe fè pwochen.

487
00:39:04,240 --> 00:39:07,610
>> Nan pwen sa a, nou gen yo ekri yon fonksyon rele 'gen'

488
00:39:07,610 --> 00:39:14,150
ak yon pwototip nan 'konprann bouleen (Int valè)'.

489
00:39:14,150 --> 00:39:17,060
Lè sa a gen fonksyon ki pral retounen vre

490
00:39:17,060 --> 00:39:21,200
 si pye bwa a pwente ke varyab mondyal rasin nou

491
00:39:21,200 --> 00:39:26,950
 gen valè a te pase nan fonksyon an ak fo otreman.

492
00:39:26,950 --> 00:39:29,000
Se pou nou ale pi devan epi fè sa.

493
00:39:29,000 --> 00:39:35,380
Sa a se pral fè egzakteman menm jan ak Passage a ke nou te fè nan men sou iPad a jis yon ti jan de sa.

494
00:39:35,380 --> 00:39:40,130
A Se pou rale tounen nan yon ti jan ak woulo liv la.

495
00:39:40,130 --> 00:39:43,130
Nou pral mete sa a fonksyon dwa pi wo a fonksyon prensipal nou an

496
00:39:43,130 --> 00:39:48,990
pou nou pa bezwen fè nenpòt ki sòt de Prototype.

497
00:39:48,990 --> 00:39:55,960
Se konsa, bouleen gen (Int valè).

498
00:39:55,960 --> 00:40:00,330
Gen nou ale. Genyen nan deklarasyon boilerplate nou an.

499
00:40:00,330 --> 00:40:02,900
Jis asire w ke sa a pral konpile,

500
00:40:02,900 --> 00:40:06,820
Mwen pral ale pi devan ak jis mete l 'egal a retounen fo.

501
00:40:06,820 --> 00:40:09,980
Kounye a sa a fonksyon jis pa pral fè anyen ak toujou rapòte ke

502
00:40:09,980 --> 00:40:14,010
valè a ke nou ap chèche pou se pa nan pyebwa sa a.

503
00:40:14,010 --> 00:40:16,280
>> Nan pwen sa a, li la pwobableman yon bon lide -

504
00:40:16,280 --> 00:40:19,600
depi nou te ekri yon pakèt antye nan kòd epi nou pa gen menm te eseye tès li ankò -

505
00:40:19,600 --> 00:40:22,590
asire w ke li tout compiles.

506
00:40:22,590 --> 00:40:27,460
Gen yon koup de bagay sa yo ke nou gen pou fè pou asire w ke sa a pral aktyèlman konpile.

507
00:40:27,460 --> 00:40:33,530
Premyèman, wè si nou ve yo te lè l sèvi avèk nenpòt ki fonksyon nan nenpòt bibliyotèk ke nou pa gen ankò enkli ladan li.

508
00:40:33,530 --> 00:40:37,940
Fonksyon yo nou te itilize byen lwen tèlman yo se malok,

509
00:40:37,940 --> 00:40:43,310
ak Lè sa a, nou te tou yo te lè l sèvi avèk sa a ki kalite - sa a ki kalite san estanda rele 'bool' -

510
00:40:43,310 --> 00:40:45,750
ki se enkli nan dosye a estanda header bouleen.

511
00:40:45,750 --> 00:40:53,250
Nou definitivman vle gen ladan estanda bool.h pou di ki kalite a bouleen,

512
00:40:53,250 --> 00:40:59,230
ak nou menm tou nou vle # enkli estanda lib.h pou bibliyotèk yo estanda

513
00:40:59,230 --> 00:41:03,530
ki gen ladan malok, ak gratis, epi nan tout sa.

514
00:41:03,530 --> 00:41:08,660
Se konsa, rale soti, nou pwal kite fimen.

515
00:41:08,660 --> 00:41:14,190
Ann eseye ak asire w ke sa sa a aktyèlman te fè konpile.

516
00:41:14,190 --> 00:41:18,150
Nou wè ke li fè sa, se konsa nou ap sou track dwat la.

517
00:41:18,150 --> 00:41:22,990
>> Se pou nou louvri moute binary_tree.c ankò.

518
00:41:22,990 --> 00:41:34,530
Li compiles. Ann al desann, epi fè sèten ke nou insert kèk apèl fonksyone konprann nou yo -

519
00:41:34,530 --> 00:41:40,130
jis asire w ke ki nan tout sa byen epi li bon.

520
00:41:40,130 --> 00:41:43,170
Pou egzanp, lè nou te fè kèk rchèrch nan pyebwa nou pi bonè,

521
00:41:43,170 --> 00:41:48,500
nou te eseye yo gade jiska valè yo 6, 10, ak 1, epi nou te konnen ke 6 te nan pyebwa a,

522
00:41:48,500 --> 00:41:52,220
10 pa t 'nan pye bwa a, ak 1 pa t' nan pye bwa a swa.

523
00:41:52,220 --> 00:41:57,230
Se pou nou sèvi ak apèl sa yo echantiyon yo kòm yon fason kalkile si ou pa

524
00:41:57,230 --> 00:41:59,880
fonksyon konprann nou an ap travay.

525
00:41:59,880 --> 00:42:05,210
Yo nan lòd yo fè sa, mwen pral sèvi avèk fonksyon an printf,

526
00:42:05,210 --> 00:42:10,280
epi nou ap ale nan enprime soti rezilta nan apèl la gen.

527
00:42:10,280 --> 00:42:13,280
Mwen pral mete nan yon fisèl "gen (% d) = paske

528
00:42:13,280 --> 00:42:20,470
 nou pwal ploge nan valè a ke nou ap ale nan gade pou li a,

529
00:42:20,470 --> 00:42:27,130
ak =% s \ n "epi sèvi ak sa kòm fisèl fòma nou an.

530
00:42:27,130 --> 00:42:30,720
Nou jis ap pral wè - literalman enprime soti sou ekran an -

531
00:42:30,720 --> 00:42:32,060
sa ki sanble yon apèl fonksyon.

532
00:42:32,060 --> 00:42:33,580
Sa a se pa aktyèlman rele nan fonksyon.

533
00:42:33,580 --> 00:42:36,760
 Sa a se jis yon fisèl ki fèt yo gade tankou yon apèl fonksyon.

534
00:42:36,760 --> 00:42:41,140
>> Koulye a, nou ap ale nan ploge nan valè yo.

535
00:42:41,140 --> 00:42:43,580
Nou pral eseye gen sou 6,

536
00:42:43,580 --> 00:42:48,340
ak Lè sa a, sa n ap pral fè isit la se sèvi ak ke operatè tèrsyèr.

537
00:42:48,340 --> 00:42:56,340
Ann wè - gen 6 - se konsa, koulye a, mwen te genyen 6 ak si gen 6 an se laverite,

538
00:42:56,340 --> 00:43:01,850
fisèl la ke nou ap ale nan voye bay karaktè fòma% nan yo

539
00:43:01,850 --> 00:43:04,850
a pwal fisèl la "vre".

540
00:43:04,850 --> 00:43:07,690
Se pou nou woulo liv sou yon ti kras.

541
00:43:07,690 --> 00:43:16,210
Sinon, nou vle voye fisèl la "fo" si gen 6 retounen fo.

542
00:43:16,210 --> 00:43:19,730
Sa a se yon ti kras so-ap chèche, men mwen kalkile mwen ta ka kòm byen ilistre

543
00:43:19,730 --> 00:43:23,780
ki sa operatè a tèrsyèr sanble depi nou pa t 'wè li pou ti tan.

544
00:43:23,780 --> 00:43:27,670
Sa se va yon bèl, sou la men fason yo detèminen si fonksyon konprann nou an ap travay.

545
00:43:27,670 --> 00:43:30,040
Mwen pral woulo liv tounen sou bò goch la,

546
00:43:30,040 --> 00:43:39,900
ak mwen pral fè kopi ak keratin liy sa a yon fwa kèk.

547
00:43:39,900 --> 00:43:44,910
Li chanje kèk nan valè sa yo otou,

548
00:43:44,910 --> 00:43:59,380
kidonk sa a se pral 1, ak sa a ki pral gen 10.

549
00:43:59,380 --> 00:44:02,480
>> Nan pwen sa a nou te gen yon bèl konprann fonksyon.

550
00:44:02,480 --> 00:44:06,080
Nou te gen kèk tès yo, epi nou pral wè si sa a tout travay.

551
00:44:06,080 --> 00:44:08,120
Nan pwen sa a nou te ekri kèk plis kòd.

552
00:44:08,120 --> 00:44:13,160
Tan kite fimen deyò epi yo asire w ke tout bagay toujou compiles.

553
00:44:13,160 --> 00:44:20,360
Kite soti, epi kounye a kite a eseye fè pyebwa binè ankò.

554
00:44:20,360 --> 00:44:22,260
Oke, li sanble nou te gen yon erè,

555
00:44:22,260 --> 00:44:26,930
epi nou te gen sa a klèman deklare fonksyon bibliyotèk la printf.

556
00:44:26,930 --> 00:44:39,350
Li sanble ke nou bezwen ale nan ak # enkli standardio.h.

557
00:44:39,350 --> 00:44:45,350
Se avèk sa, tout bagay ta dwe konpile. Nou tout se bon.

558
00:44:45,350 --> 00:44:50,420
Koulye a, kite nan eseye kouri binè pye bwa yo epi wè kisa k ap rive.

559
00:44:50,420 --> 00:44:53,520
Isit la nou ye a,. / Binary_tree,

560
00:44:53,520 --> 00:44:55,190
e nou wè ke, menm jan nou espere -

561
00:44:55,190 --> 00:44:56,910
paske nou pa te aplike gen ankò,

562
00:44:56,910 --> 00:44:59,800
oswa olye, nou te jis mete an retou fo -

563
00:44:59,800 --> 00:45:03,300
nou wè ke li jis retounen fo pou tout nan yo,

564
00:45:03,300 --> 00:45:06,180
Se konsa se te tout ap travay pou pati ki pi san patipri byen.

565
00:45:06,180 --> 00:45:11,860
>> Ann al tounen nan ak aktyèlman aplike gen nan pwen sa.

566
00:45:11,860 --> 00:45:17,490
Mwen pral desann, rale nan, ak -

567
00:45:17,490 --> 00:45:22,330
sonje, algorithm a ke nou te itilize ke nou te kòmanse nan ne an rasin

568
00:45:22,330 --> 00:45:28,010
ak Lè sa a, nan chak ne ke nou rankontre, nou fè yon konparezon,

569
00:45:28,010 --> 00:45:32,380
ak ki baze sou ki konparezon nou swa deplase li nan yon timoun nan gòch la oswa ak pitit la dwat.

570
00:45:32,380 --> 00:45:39,670
Sa a se pral gade trè menm jan ak kòd la rechèch binè ke nou te ekri byen bonè nan tèm nan.

571
00:45:39,670 --> 00:45:47,810
Lè nou kòmanse desann, nou konnen ke nou vle kenbe fèm nan fè ne aktyèl la

572
00:45:47,810 --> 00:45:54,050
ke nou ap chèche a, ak ne li ye kounye a yo pral inisyalizèd ne nan rasin.

573
00:45:54,050 --> 00:45:56,260
Epi, koulye a, nou pwal kenbe ale atravè tout pyebwa a,

574
00:45:56,260 --> 00:45:58,140
epi sonje ke kondisyon kanpe nou yo -

575
00:45:58,140 --> 00:46:01,870
 lè nou aktyèlman te travay nan egzanp lan nan men -

576
00:46:01,870 --> 00:46:03,960
se te lè nou rankontre yon ne nil,

577
00:46:03,960 --> 00:46:05,480
pa lè nou te gade yon timoun nil,

578
00:46:05,480 --> 00:46:09,620
men pito lè nou aktyèlman demenaje ale rete nan yon ne nan pye bwa a

579
00:46:09,620 --> 00:46:12,640
epi li te jwenn ke nou se nan yon ne nil.

580
00:46:12,640 --> 00:46:20,720
Nou pral répétèr jouk akt se pa egal a nil.

581
00:46:20,720 --> 00:46:22,920
E kisa nou pral fè?

582
00:46:22,920 --> 00:46:31,610
Nou pral teste si (akt -> valè == valè),

583
00:46:31,610 --> 00:46:35,160
Lè sa a, nou konnen ke nou te aktyèlman te jwenn ne a ke nou ap chèche pou.

584
00:46:35,160 --> 00:46:40,450
Se konsa, isit la, nou ka retounen vre.

585
00:46:40,450 --> 00:46:49,830
Sinon, nou ta renmen wè si wi ou non valè a se mwens pase valè li a.

586
00:46:49,830 --> 00:46:53,850
Si valè ne yo ye a se mwens pase valè an ke nou ap chèche pou yo,

587
00:46:53,850 --> 00:46:57,280
nou pral pou avanse pou pi a dwat la.

588
00:46:57,280 --> 00:47:10,600
Se konsa, akt = akt -> right_child; ak otreman, nou pwal pou yo avanse pou bò gòch li.

589
00:47:10,600 --> 00:47:17,480
akt = akt -> left_child;. Trè senp.

590
00:47:17,480 --> 00:47:22,830
>> Ou pwobableman rekonèt riban an ki sanble anpil menm jan ak sa a soti nan

591
00:47:22,830 --> 00:47:27,580
rechèch binè pi bonè nan tèm nan, eksepte Lè sa a, nou te fè fas ak nan mitan ki ba,, ak segondè.

592
00:47:27,580 --> 00:47:30,000
Isit la, nou jis gen gade nan yon valè ye kounye a,

593
00:47:30,000 --> 00:47:31,930
Se konsa li bèl ak senp.

594
00:47:31,930 --> 00:47:34,960
Se pou nou asire ou ke sa a kòd ap travay.

595
00:47:34,960 --> 00:47:42,780
Premyèman, asire w ke li compiles. Sanble li fè sa.

596
00:47:42,780 --> 00:47:47,920
Ann eseye kouri li.

597
00:47:47,920 --> 00:47:50,160
Ak tout bon, li simagri soti tout bagay ke nou espere.

598
00:47:50,160 --> 00:47:54,320
Li jwenn 6 nan pye bwa a, pa jwenn 10 paske 10 se pa nan pyebwa a,

599
00:47:54,320 --> 00:47:57,740
epi yo pa jwenn 1, swa paske 1 la tou pa nan pyebwa sa a.

600
00:47:57,740 --> 00:48:01,420
Cool bagay.

601
00:48:01,420 --> 00:48:04,470
>> Byen. Se pou nou tounen nan spesifikasyon nou yo ak wè sa ki nan pwochen.

602
00:48:04,470 --> 00:48:07,990
Koulye a, li vle ajoute kèk plis nœuds bò pyebwa nou yo.

603
00:48:07,990 --> 00:48:11,690
Li vle ajoute 5, 2, ak 8yèm ane, ak asire w ke nou gen kòd

604
00:48:11,690 --> 00:48:13,570
toujou ap travay jan yo espere.

605
00:48:13,570 --> 00:48:14,900
Ann al fè sa.

606
00:48:14,900 --> 00:48:19,430
Nan pwen sa a, olye ke fè sa kopi annwiyeu ak keratin ankò,

607
00:48:19,430 --> 00:48:23,770
kite a ekri yon fonksyon aktyèlman kreye yon ne.

608
00:48:23,770 --> 00:48:27,740
Si nou desann tout wout la prensipal yo, nou wè ke nou te toujou ap fè sa a

609
00:48:27,740 --> 00:48:31,210
anpil menm jan kòd sou yo ak sou ankò chak fwa ke nou vle kreye yon ne.

610
00:48:31,210 --> 00:48:39,540
>> Se pou nou ekri yon fonksyon ki pral konstwi aktyèlman yon ne pou nou epi retounen li.

611
00:48:39,540 --> 00:48:41,960
Mwen pral rele li build_node.

612
00:48:41,960 --> 00:48:45,130
Mwen pral bati yon ne ki gen yon valè patikilye.

613
00:48:45,130 --> 00:48:51,040
Rale nan isit la.

614
00:48:51,040 --> 00:48:56,600
Premye bagay mwen pral fè se aktyèlman kreye espas pou ne la sou pil la.

615
00:48:56,600 --> 00:49:05,400
Se konsa, ne * n = malok (sizof (ne)); n -> valè = valè;

616
00:49:05,400 --> 00:49:14,960
ak Lè sa a, isit la, mwen jis ale nan inisyalize tout jaden yo yo dwe valè ki apwopriye yo.

617
00:49:14,960 --> 00:49:22,500
Ak nan fen a trè, nou pral retounen ne nou an.

618
00:49:22,500 --> 00:49:28,690
Byen. Youn nan bagay a nòt la ki fonksyon sa a isit la

619
00:49:28,690 --> 00:49:34,320
ki pral retounen yon konsèy memwa ki te pil-affecte.

620
00:49:34,320 --> 00:49:38,880
Ki sa ki nan bon sou sa a se ke sa a ne kounye a -

621
00:49:38,880 --> 00:49:42,420
nou dwe deklare l 'sou pil wòch la, paske si nou te deklare l' sou chemine a

622
00:49:42,420 --> 00:49:45,050
nou pa ta dwe ka fè l 'nan sa a fonksyon tankou sa a.

623
00:49:45,050 --> 00:49:47,690
Sa memwa ta ale soti nan dimansyon

624
00:49:47,690 --> 00:49:51,590
ak ta dwe valab si nou te eseye gen aksè a li pita sou.

625
00:49:51,590 --> 00:49:53,500
Depi nou yo deklare pil-affecte memwa,

626
00:49:53,500 --> 00:49:55,830
nou pral dwe pran swen nan libere li pita

627
00:49:55,830 --> 00:49:58,530
pou pwogram nou an pa genyen fuit nenpòt memwa.

628
00:49:58,530 --> 00:50:01,270
Nou te ap punting sou sa pou Tout Lòt Bagay nan kòd la

629
00:50:01,270 --> 00:50:02,880
jis pou dedomajman pou senplisite a nan moman an,

630
00:50:02,880 --> 00:50:05,610
Men, si ou te janm ekri yon fonksyon ki sanble tankou sa a

631
00:50:05,610 --> 00:50:10,370
kote ou te gen - kèk rele li yon malok oswa realloc andedan -

632
00:50:10,370 --> 00:50:14,330
ou vle asire w ke ou mete kèk sòt de kòmantè moute isit la ki di,

633
00:50:14,330 --> 00:50:29,970
hey, ou konnen, retounen yon ne pil-affecte inisyalizèd ak valè an te pase-a.

634
00:50:29,970 --> 00:50:33,600
Lè sa a, ou vle asire w ke ou mete nan kèk sòt de nòt ki di

635
00:50:33,600 --> 00:50:41,720
moun kap rele a dwe libere memwa a retounen.

636
00:50:41,720 --> 00:50:45,450
Nan fason sa a, si yon moun tout tan ale epi li sèvi ak sa fonksyon,

637
00:50:45,450 --> 00:50:48,150
yo konnen tou sa yo gen pou retounen nan sa fonksyon

638
00:50:48,150 --> 00:50:50,870
nan kèk pwen pral bezwen dwe libere.

639
00:50:50,870 --> 00:50:53,940
>> Nou asime ke tout bagay byen epi li bon isit la,

640
00:50:53,940 --> 00:51:02,300
nou ka ale desann nan kòd nou yo ak ranplase tout nan liy sa yo isit la

641
00:51:02,300 --> 00:51:05,410
ak apèl fonksyone bati ne nou an.

642
00:51:05,410 --> 00:51:08,170
Se pou nou fè sa vrèman byen vit.

643
00:51:08,170 --> 00:51:15,840
Pati nan yon sèl ke nou pa ap ale nan ranplase se nan pati sa a desann isit la

644
00:51:15,840 --> 00:51:18,520
nan pati anba a kote nou aktyèlman WIRE moute nœuds yo nan pwen nan chak lòt,

645
00:51:18,520 --> 00:51:21,030
paske nou pa ka fè nan fonksyon nou an.

646
00:51:21,030 --> 00:51:37,400
Men, kite a fè rasin = build_node (7); ne * twa = build_node (3);

647
00:51:37,400 --> 00:51:47,980
ne * sis = build_node (6); ne * nèf = build_node (9);.

648
00:51:47,980 --> 00:51:52,590
Epi, koulye a, nou menm tou nou te vle ajoute nœuds pou -

649
00:51:52,590 --> 00:52:03,530
ne * senk = build_node (5); ne * uit = build_node (8);

650
00:52:03,530 --> 00:52:09,760
ak ki sa ki te ne lòt yo? Ann wè isit la. Nou te vle tou ajoute yon 2 -

651
00:52:09,760 --> 00:52:20,280
ne * de = build_node (2);.

652
00:52:20,280 --> 00:52:26,850
Byen. Nan pwen sa a, nou konnen ke nou te gen 7 an, 3 an, 9 la, ak 6 an

653
00:52:26,850 --> 00:52:30,320
tout câblé moute kòmsadwa, men sa ki sou 5 an, 8 la, ak 2 a?

654
00:52:30,320 --> 00:52:33,550
Pou kenbe tout bagay yo nan lòd ki apwopriye a,

655
00:52:33,550 --> 00:52:39,230
nou konnen ke pitit dwa twa a se 6.

656
00:52:39,230 --> 00:52:40,890
Se konsa, si nou pwal ajoute 5 an,

657
00:52:40,890 --> 00:52:46,670
5 a tou ki dwe nan bò dwat la pyebwa ki fè moun ki 3 se rasin lan,

658
00:52:46,670 --> 00:52:50,440
Se konsa 5 ki dwe kòm timoun nan gòch nan 6.

659
00:52:50,440 --> 00:52:58,650
Nou ka fè sa a lè li di, sis -> left_child = senk;

660
00:52:58,650 --> 00:53:10,790
ak Lè sa a, 8 la ki dwe kòm timoun nan bò gòch nan 9, se konsa nèf -> left_child = uit;

661
00:53:10,790 --> 00:53:22,190
ak Lè sa a, 2 a se timoun nan bò gòch nan 3, konsa nou ka fè sa moute isit la - ou -> left_child = de;.

662
00:53:22,190 --> 00:53:27,730
Si ou pa t 'byen swiv ansanm ak sa, mwen sijere ou rale yo mete deyò tèt ou.

663
00:53:27,730 --> 00:53:35,660
>> Byen. Se pou nou sove sa a. Ann al deyò epi yo asire w ke li compiles,

664
00:53:35,660 --> 00:53:40,760
ak Lè sa a, nou ka ajoute nan konprann apèl nou yo.

665
00:53:40,760 --> 00:53:44,120
Sanble tout bagay toujou compiles.

666
00:53:44,120 --> 00:53:51,790
Ann al nan epi ajoute nan kèk gen apèl.

667
00:53:51,790 --> 00:53:59,640
Yon fwa ankò, mwen pral fè yon ti kras nan kopi ak keratin.

668
00:53:59,640 --> 00:54:15,860
Koulye a, kite l 'nan rechèch pou 5 8,, epi 2. Byen.

669
00:54:15,860 --> 00:54:28,330
Se pou nou asire w ke sa a tout moun sanble bon toujou. Gwo! Save ak kite fimen.

670
00:54:28,330 --> 00:54:33,220
Koulye a, kite a fè, konpile, ak kounye a kite a kouri.

671
00:54:33,220 --> 00:54:37,540
Soti nan rezilta yo, li sanble tout bagay ap travay jis bèl ak byen.

672
00:54:37,540 --> 00:54:41,780
Gwo! Se konsa, kounye a nou te gen konprann nou fonksyon ekri.

673
00:54:41,780 --> 00:54:46,160
Kite yo deplase sou yo ak sou kòmanse travay sou ki jan yo insert nœuds nan pye bwa a

674
00:54:46,160 --> 00:54:50,000
depi, jan n ap fè li kounye a, bagay yo pa trè bèl.

675
00:54:50,000 --> 00:54:52,280
>> Si nou tounen nan spesifikasyon la,

676
00:54:52,280 --> 00:55:00,540
li mande nou yo ekri yon fonksyon rele insert - ankò, retounen yon bouleen

677
00:55:00,540 --> 00:55:04,400
pou si ou pa nou te ka aktyèlman insert ne la nan pye bwa a -

678
00:55:04,400 --> 00:55:07,710
ak Lè sa a, se valè a insert nan pye bwa a ki espesifye kòm

679
00:55:07,710 --> 00:55:11,060
agiman la sèlman nan fonksyon insert nou an.

680
00:55:11,060 --> 00:55:18,180
Nou pral retounen vre si nou te ka tout bon insert ne valè a ki gen nan pyebwa a,

681
00:55:18,180 --> 00:55:20,930
ki vle di ke nou menm, yon sèl, te gen ase memwa,

682
00:55:20,930 --> 00:55:24,840
ak Lè sa a, de, ki ne pa t 'deja egziste nan pyebwa a depi -

683
00:55:24,840 --> 00:55:32,170
sonje, nou pa yo ale nan yo gen valè kopi nan pye bwa a, jis fè bagay sa yo ki senp.

684
00:55:32,170 --> 00:55:35,590
Byen. Retounen nan kòd la.

685
00:55:35,590 --> 00:55:44,240
Louvri li. Zoom nan yon ti jan, lè sa a desann.

686
00:55:44,240 --> 00:55:47,220
Ann mete fonksyon an insert dwa pi wo a konprann yo.

687
00:55:47,220 --> 00:55:56,360
Yon fwa ankò, li pral yo dwe rele bouleen insert (Int valè).

688
00:55:56,360 --> 00:56:01,840
Ba li yon ti kras pi plis espas, ak lè sa a, kòm yon default,

689
00:56:01,840 --> 00:56:08,870
kite a mete an retou fo nan fen an trè.

690
00:56:08,870 --> 00:56:22,620
Koulye a, desann nan pati anba a, se pou yo ale pi devan ak olye pou yo manyèlman bati nœuds yo

691
00:56:22,620 --> 00:56:27,900
nan prensipal tèt nou ak fil elektrik yo moute nan pwen nan chak lòt tankou n ap fè,

692
00:56:27,900 --> 00:56:30,600
nou pral konte sou fonksyon insert nou fè sa.

693
00:56:30,600 --> 00:56:35,510
Nou pa pral konte sou fonksyon insert nou yo bati pyebwa a tout antye nan grafouyen jis ankò,

694
00:56:35,510 --> 00:56:39,970
men pito nou pral debarase m de liy sa yo - we'll kòmantè soti liy sa yo -

695
00:56:39,970 --> 00:56:43,430
ki bati nœuds yo 5, 8, ak 2.

696
00:56:43,430 --> 00:56:55,740
Ak olye de sa, nou pral insert apèl fonksyone insert nou

697
00:56:55,740 --> 00:57:01,280
asire w ke ki aktyèlman ap travay.

698
00:57:01,280 --> 00:57:05,840
Isit la nou ale.

699
00:57:05,840 --> 00:57:09,300
>> Koulye a, nou te kòmante soti liy sa yo.

700
00:57:09,300 --> 00:57:13,700
Nou sèlman gen 7, 3, 9, ak 6 nan pyebwa nou an nan pwen sa a.

701
00:57:13,700 --> 00:57:18,870
Pou fè sèten ke sa a se tout travay,

702
00:57:18,870 --> 00:57:25,050
nou ka rale soti, fè pyebwa binè nou an,

703
00:57:25,050 --> 00:57:30,750
kouri li, epi nou ka wè ke gen se kounye a di nou ke nou se totalman dwa -

704
00:57:30,750 --> 00:57:33,110
5, 8, ak 2 yo pa nan pyebwa sa a.

705
00:57:33,110 --> 00:57:37,960
Ale tounen nan kòd la,

706
00:57:37,960 --> 00:57:41,070
ak ki jan nou pral insert?

707
00:57:41,070 --> 00:57:46,290
Sonje sa nou te fè sa lè nou te aktyèlman mete 5, 8, ak 2 deja a.

708
00:57:46,290 --> 00:57:50,100
Nou jwe jwèt sa Plinko kote nou te kòmanse nan rasin la,

709
00:57:50,100 --> 00:57:52,780
desann yon sèl nan pyebwa pa youn pa youn

710
00:57:52,780 --> 00:57:54,980
jiskaske nou jwenn diferans ki apwopriye a,

711
00:57:54,980 --> 00:57:57,570
ak Lè sa a, nou branche nan ne an nan plas la ki apwopriye yo.

712
00:57:57,570 --> 00:57:59,480
Nou pwal fè menm bagay la.

713
00:57:59,480 --> 00:58:04,070
Sa a se fondamantalman tankou ekri kòd la ke nou te itilize nan gen nan fonksyon

714
00:58:04,070 --> 00:58:05,910
jwenn plas nan kote ne a ta dwe,

715
00:58:05,910 --> 00:58:10,560
ak Lè sa a, nou ap jis pral insert ne an dwa a.

716
00:58:10,560 --> 00:58:17,000
Se pou nou kòmanse fè sa.

717
00:58:17,000 --> 00:58:24,200
>> Se konsa, nou gen yon ne * akt = rasin; nou ap jis pral swiv gen kòd sa a

718
00:58:24,200 --> 00:58:26,850
jiskaske nou jwenn ke li pa byen travay pou nou.

719
00:58:26,850 --> 00:58:32,390
Nou pral yo ale nan pye bwa a pandan y ap eleman aktyèl la se pa nil,

720
00:58:32,390 --> 00:58:45,280
epi si nou jwenn valè ki akt a ki egal a valè a ke nou ap eseye insert -

721
00:58:45,280 --> 00:58:49,600
byen, sa a se youn nan ka yo nan ki nou pa t 'kapab aktyèlman insert ne la

722
00:58:49,600 --> 00:58:52,730
nan pye bwa a paske sa vle di nou gen yon valè kopi.

723
00:58:52,730 --> 00:58:59,010
Isit la nou ap aktyèlman pral retounen fo.

724
00:58:59,010 --> 00:59:08,440
Koulye a, lòt bagay si valè akt a se mwens pase valè li,

725
00:59:08,440 --> 00:59:10,930
kounye a nou konnen ke nou deplase a dwat a

726
00:59:10,930 --> 00:59:17,190
 paske valè a ki dwe nan mwatye nan dwa nan pyebwa a akt.

727
00:59:17,190 --> 00:59:30,110
Sinon, nou pwal pou yo avanse pou bò gòch li.

728
00:59:30,110 --> 00:59:37,980
Sa a se fondamantalman konprann nou fonksyone ki la a.

729
00:59:37,980 --> 00:59:41,820
>> Nan pwen sa a, yon fwa nou te ranpli sa a pandan y ap riban,

730
00:59:41,820 --> 00:59:47,350
konsèy akt nou yo pral montre nil

731
00:59:47,350 --> 00:59:51,540
si fonksyon an pa te deja retounen.

732
00:59:51,540 --> 00:59:58,710
Nou ap Se poutèt sa gen akt nan plas la kote nou vle insert ne nan nouvo.

733
00:59:58,710 --> 01:00:05,210
Ki sa ki rete yo dwe fè se konstwi aktyèlman ne nan nouvo,

734
01:00:05,210 --> 01:00:08,480
ki nou ka fè bèl fasil.

735
01:00:08,480 --> 01:00:14,930
Nou ka sèvi avèk fonksyon super-sou la men nou ne bati,

736
01:00:14,930 --> 01:00:17,210
ak yon bagay ke nou pa t 'fè pi bonè -

737
01:00:17,210 --> 01:00:21,400
nou jis kalite te pran pou yo akòde men kounye a nou pwal fè jis asire ou ke -

738
01:00:21,400 --> 01:00:27,130
nou pral teste a asire w ke valè a tounen pa ne nouvo te aktyèlman

739
01:00:27,130 --> 01:00:33,410
pa nil, paske nou pa vle kòmanse aksè ki memwa si li se nil.

740
01:00:33,410 --> 01:00:39,910
Nou ka fè tès a asire w ke ne nouvo se pa egal a nil.

741
01:00:39,910 --> 01:00:42,910
Oswa olye de sa, nou ka jis wè si li aktyèlman se nil,

742
01:00:42,910 --> 01:00:52,120
ak si li se nil, lè sa a nou ka jis retounen fo bonè.

743
01:00:52,120 --> 01:00:59,090
>> Nan pwen sa a, nou gen nan pwent fil nouvo ne nan plas ki apwopriye li yo nan pyebwa sa a.

744
01:00:59,090 --> 01:01:03,510
Si nou gade tounen nan prensipal ak ki kote nou te aktyèlman fil elektrik nan valè anvan,

745
01:01:03,510 --> 01:01:08,470
nou wè ke fason an nou te fè li lè nou te vle mete 3 nan pye bwa a

746
01:01:08,470 --> 01:01:11,750
te nou jwenn aksè timoun nan gòch nan rasin.

747
01:01:11,750 --> 01:01:14,920
Lè nou mete 9 nan pye bwa a, nou te gen gen aksè a timoun nan dwa a rasin lan.

748
01:01:14,920 --> 01:01:21,030
Nou te gen gen yon konsèy bay paran an yo nan lòd yo mete yon valè nouvo nan pyebwa sa a.

749
01:01:21,030 --> 01:01:24,430
Defile tounen jiska insert, ki pa a pral byen travay isit la

750
01:01:24,430 --> 01:01:27,550
paske nou pa gen yon konsèy paran yo.

751
01:01:27,550 --> 01:01:31,650
Ki sa nou vle pou kapab fè se, nan pwen sa a,

752
01:01:31,650 --> 01:01:37,080
tcheke valè paran an ak wè - byen, bondye papa,

753
01:01:37,080 --> 01:01:41,990
si valè paran an a se mwens pase valè aktyèl la,

754
01:01:41,990 --> 01:01:54,440
Lè sa a, dwa timoun paran an ta dwe ne nan nouvo;

755
01:01:54,440 --> 01:02:07,280
otreman, bò gòch pitit paran an ta dwe ne nan nouvo.

756
01:02:07,280 --> 01:02:10,290
Men, nou pa gen sa a konsèy paran byen ankò.

757
01:02:10,290 --> 01:02:15,010
>> Yo nan lòd yo jwenn li, n ap aktyèlman pral fè yo swiv li kòm nou ale nan pye bwa a

758
01:02:15,010 --> 01:02:18,440
epi jwenn plas ki apwopriye a nan riban nou pi wo a.

759
01:02:18,440 --> 01:02:26,840
Nou ka fè sa pa defile tounen moute nan tèt la nan fonksyon insert nou

760
01:02:26,840 --> 01:02:32,350
ak swiv yon lòt varyab konsèy rele paran an.

761
01:02:32,350 --> 01:02:39,340
Nou pral mete l 'egal a nil okòmansman,

762
01:02:39,340 --> 01:02:43,640
ak Lè sa a, chak fwa nou ale nan pye bwa a,

763
01:02:43,640 --> 01:02:51,540
nou pwal mete konsèy paran an matche ak konsèy aktyèl la.

764
01:02:51,540 --> 01:02:59,140
Fikse paran egal a akt.

765
01:02:59,140 --> 01:03:02,260
Fason sa a, chak fwa nou ale nan,

766
01:03:02,260 --> 01:03:05,550
nou pwal asire ke kòm konsèy aktyèl la vin enkremante

767
01:03:05,550 --> 01:03:12,640
konsèy paran an swiv li - jis yon nivo pi wo pase konsèy aktyèl la nan pye bwa an.

768
01:03:12,640 --> 01:03:17,370
Ke tout sanble trè bon.

769
01:03:17,370 --> 01:03:22,380
>> Mwen panse ke bagay la yon sèl ke nou pral vle ajiste sa a bati ne retounen nil.

770
01:03:22,380 --> 01:03:25,380
Yo nan lòd jwenn bati ne aktyèlman avèk siksè retounen nil,

771
01:03:25,380 --> 01:03:31,060
nou pral oblije modifye ki kòd,

772
01:03:31,060 --> 01:03:37,270
paske isit la, nou pa janm fè tès a asire w ke malok tounen yon konsèy ki valid.

773
01:03:37,270 --> 01:03:53,390
Se konsa, si (n = nil!), Lè sa a -

774
01:03:53,390 --> 01:03:55,250
si malok tounen yon konsèy ki valab, Lè sa a, nou pral inisyalize li;

775
01:03:55,250 --> 01:04:02,540
otreman, nou pral jis retounen ak ki pral fini retounen nil pou nou.

776
01:04:02,540 --> 01:04:13,050
Koulye a, tout sanble trè bon. Se pou nou asire ou ke sa sa a aktyèlman compiles.

777
01:04:13,050 --> 01:04:22,240
Fè pyebwa binè, ak oh, nou te gen kèk bagay pral sou isit la.

778
01:04:22,240 --> 01:04:29,230
>> Nou gen yon deklarasyon enplisit nan fonksyon bati ne.

779
01:04:29,230 --> 01:04:31,950
Yon fwa ankò, ak sa yo konpilateur, nou pwal kòmanse nan tèt la.

780
01:04:31,950 --> 01:04:36,380
Ki sa ki ki dwe vle di se ke m ap rele bati ne mwen anvan m 'te aktyèlman te deklare li.

781
01:04:36,380 --> 01:04:37,730
Se pou nou tounen nan kòd la reyèlman byen vit.

782
01:04:37,730 --> 01:04:43,510
Scroll down, ak asire w ase, se fonksyon insert mwen te deklare

783
01:04:43,510 --> 01:04:47,400
pi wo a fonksyon an ne bati,

784
01:04:47,400 --> 01:04:50,070
men mwen m 'ap eseye sèvi ak bati ne anndan insert.

785
01:04:50,070 --> 01:05:06,610
Mwen pral ale nan ak kopi - ak Lè sa a, keratin ne wout la fonksyon bati isit la nan tèt la.

786
01:05:06,610 --> 01:05:11,750
Nan fason sa a, èspere ke sa pwal mache. Se pou nou bay sa a yon lòt ale.

787
01:05:11,750 --> 01:05:18,920
Kounye a li tout compiles. Tout se yon bon bagay.

788
01:05:18,920 --> 01:05:21,640
>> Men, nan pwen sa a, nou pa gen aktyèlman rele fonksyon insert nou an.

789
01:05:21,640 --> 01:05:26,510
Nou jis konnen ke li compiles, se konsa kite yo ale nan epi li mete kèk apèl pous

790
01:05:26,510 --> 01:05:28,240
Se pou nou fè sa nan yon fonksyon prensipal nou an.

791
01:05:28,240 --> 01:05:32,390
Isit la, nou kòmante soti 5, 8, ak 2,

792
01:05:32,390 --> 01:05:36,680
ak Lè sa a, nou pa t 'WIRE yo moute desann isit la.

793
01:05:36,680 --> 01:05:41,640
Se pou nou fè kèk apèl insert,

794
01:05:41,640 --> 01:05:46,440
e kite yo sèvi tou ak kalite a menm nan bagay ke nou itilize

795
01:05:46,440 --> 01:05:52,810
lè nou te fè sa yo apèl printf a asire w ke tout bagay t 'jwenn eleman byen.

796
01:05:52,810 --> 01:06:00,550
Mwen pral voye yon kopi bay ak keratin,

797
01:06:00,550 --> 01:06:12,450
ak olye pou yo gen nou ap pral fè insert.

798
01:06:12,450 --> 01:06:30,140
Ak olye pou yo 6 10,, ak 1, nou pwal sèvi ak 5, 8, ak 2.

799
01:06:30,140 --> 01:06:37,320
Sa a ta dwe èspere ke insert 5, 8, ak 2 nan pyebwa sa a.

800
01:06:37,320 --> 01:06:44,050
Sanble tout. Tout se yon bon bagay. Koulye a, nou pral aktyèlman kouri pwogram nou an.

801
01:06:44,050 --> 01:06:47,330
>> Tout tounen fo.

802
01:06:47,330 --> 01:06:53,830
Se konsa,, 5, 8, ak 2 pa t 'ale, epi li sanble pa gen t' kapab jwenn yo pou yo swa.

803
01:06:53,830 --> 01:06:58,890
Kisa ki ale sou? Se pou nou rale soti.

804
01:06:58,890 --> 01:07:02,160
Pwoblèm nan premye te ke insert te sanble ke yo retounen fo,

805
01:07:02,160 --> 01:07:08,750
ak li sanble sa a, se paske nou te kite nan rele retounen nou fo,

806
01:07:08,750 --> 01:07:14,590
epi nou pa janm aktyèlman tounen vre.

807
01:07:14,590 --> 01:07:17,880
Nou ka mete ki moute.

808
01:07:17,880 --> 01:07:25,290
Pwoblèm nan dezyèm se, kounye a menm si nou fè - sove sa a, kite sa a,

809
01:07:25,290 --> 01:07:34,530
kouri fè ankò, te li konpile, lè sa a kouri li -

810
01:07:34,530 --> 01:07:37,670
nou wè ke yon lòt bagay ki te pase isit la.

811
01:07:37,670 --> 01:07:42,980
5 nan, 8, ak 2 yo te toujou pa janm yo te jwenn nan pyebwa sa a.

812
01:07:42,980 --> 01:07:44,350
Se konsa, sa k ap pase sou?

813
01:07:44,350 --> 01:07:45,700
>> Se pou nou pran yon gade nan sa a nan kòd la.

814
01:07:45,700 --> 01:07:49,790
Se pou nou wè si nou ka figi sa a soti.

815
01:07:49,790 --> 01:07:57,940
Nou kòmanse avèk paran an pa ke yo te nil.

816
01:07:57,940 --> 01:07:59,510
Nou mete konsèy aktyèl la egal a konsèy nan rasin,

817
01:07:59,510 --> 01:08:04,280
e nou pral nan travay wout nou desann nan pyebwa sa a.

818
01:08:04,280 --> 01:08:08,650
Si ne aktyèl la se pa nil, lè sa a nou konnen ke nou ka deplase desann yon ti jan.

819
01:08:08,650 --> 01:08:12,330
Nou mete konsèy paran nou an yo dwe egal a konsèy aktyèl la,

820
01:08:12,330 --> 01:08:15,420
tcheke valè a - si valè yo se menm bagay la nou tounen fo.

821
01:08:15,420 --> 01:08:17,540
Si valè yo yo gen mwens nou demenaje ale rete nan dwa a;

822
01:08:17,540 --> 01:08:20,399
otreman, nou demenaje ale rete nan bò gòch li.

823
01:08:20,399 --> 01:08:24,220
Lè sa a, nou bati yon ne. Mwen pral rale nan yon ti jan.

824
01:08:24,220 --> 01:08:31,410
Ak isit la, nou pwal pou yo eseye WIRE moute valè yo yo dwe menm bagay la.

825
01:08:31,410 --> 01:08:37,250
Kisa ki ale sou? Ann wè si posib Valgrind ka ban nou yon allusion.

826
01:08:37,250 --> 01:08:43,910
>> Mwen renmen itilize Valgrind jis paske Valgrind vrèman byen vit kouri

827
01:08:43,910 --> 01:08:46,729
epi li di ou si gen nenpòt ki erè memwa.

828
01:08:46,729 --> 01:08:48,300
Lè nou kouri Valgrind sou kòd la,

829
01:08:48,300 --> 01:08:55,859
kòm ou kapab wè dwa frape here--Valgrind./binary_tree--and antre.

830
01:08:55,859 --> 01:09:03,640
Ou wè ke nou pa t 'gen nenpòt erè memwa, se konsa li sanble tankou tout bagay nan oke byen lwen tèlman.

831
01:09:03,640 --> 01:09:07,529
Nou fè gen kèk fwit memwa, ki nou konnen, paske nou pa

832
01:09:07,529 --> 01:09:08,910
pase libere nenpòt nan nœuds nou an.

833
01:09:08,910 --> 01:09:13,050
Ann eseye kouri gdb yo wè sa ki la aktyèlman pral sou.

834
01:09:13,050 --> 01:09:20,010
Nou pral fè gdb. / Binary_tree. Li demare moute jis anfòm.

835
01:09:20,010 --> 01:09:23,670
Se pou nou mete yon pwen repo nan sipleman.

836
01:09:23,670 --> 01:09:28,600
Se pou nou kouri.

837
01:09:28,600 --> 01:09:31,200
Li sanble ke nou pa janm aktyèlman rele insert.

838
01:09:31,200 --> 01:09:39,410
Li sanble ke pwoblèm nan te jis ke lè mwen chanje desann isit la nan prensipal -

839
01:09:39,410 --> 01:09:44,279
tout moun sa yo apèl printf soti nan gen -

840
01:09:44,279 --> 01:09:56,430
Mwen pa janm aktyèlman chanje sa yo yo rele insert.

841
01:09:56,430 --> 01:10:01,660
Koulye a, kite a bay li yon eseye. Se pou nou konpile.

842
01:10:01,660 --> 01:10:09,130
Tout sanble bon la. Koulye a, kite nan eseye kouri li, wè sa ki rive.

843
01:10:09,130 --> 01:10:13,320
Oke! Tout sanble trè bon la.

844
01:10:13,320 --> 01:10:18,130
>> Bagay la final bezwen panse osijè de se, èske genyen kèk ka kwen sa a insert?

845
01:10:18,130 --> 01:10:23,170
Epi li sanble ke, byen, ka a kwen youn ki se toujou enteresan panse osijè de

846
01:10:23,170 --> 01:10:26,250
se, ki sa ki pral rive si pyebwa ou ki vid e san ou rele sa a fonksyon insert?

847
01:10:26,250 --> 01:10:30,330
Èske li travay? Oke, kite la bay li yon eseye.

848
01:10:30,330 --> 01:10:32,110
- Binary_tree c. -

849
01:10:32,110 --> 01:10:35,810
Nan fason nou ap ale nan teste sa a se, nou pwal desann ale nan fonksyon prensipal nou an,

850
01:10:35,810 --> 01:10:41,690
ak olye ke fil elektrik sa yo nœuds moute tankou sa a,

851
01:10:41,690 --> 01:10:56,730
Nou jis ap pral fè kòmantè soti bagay la an antye,

852
01:10:56,730 --> 01:11:02,620
ak olye pou yo fil elektrik moute nœuds yo tèt nou,

853
01:11:02,620 --> 01:11:09,400
nou ka aktyèlman jis ale pi devan epi efase tout bagay sa yo.

854
01:11:09,400 --> 01:11:17,560
Nou pwal fè tout bagay yon apèl insert.

855
01:11:17,560 --> 01:11:49,020
Se konsa, kite a fè - olye pou yo 5, 8, ak 2, nou ap ale nan insert 7, 3, ak 9.

856
01:11:49,020 --> 01:11:58,440
Lè sa a, nou pral vle tou insert 6 kòm byen.

857
01:11:58,440 --> 01:12:05,190
Sove. Kite fimen. Fè pyebwa binè.

858
01:12:05,190 --> 01:12:08,540
Li tout compiles.

859
01:12:08,540 --> 01:12:10,320
Nou ka jis kouri li kòm se ak wè sa ki rive,

860
01:12:10,320 --> 01:12:12,770
men li la tou pral fè vrèman enpòtan a asire w ke

861
01:12:12,770 --> 01:12:14,740
nou pa gen nenpòt ki erè memwa,

862
01:12:14,740 --> 01:12:16,840
depi sa a se youn nan ka kwen nou an ke nou konnen sou yo.

863
01:12:16,840 --> 01:12:20,150
>> Se pou nou asire w ke li travay byen anba Valgrind,

864
01:12:20,150 --> 01:12:28,310
ki n ap fè pa jis kouri Valgrind. / binary_tree.

865
01:12:28,310 --> 01:12:31,110
Li sanble ke nou menm se gen yon sèl erè soti nan yon kontèks -

866
01:12:31,110 --> 01:12:33,790
nou gen sa a fòt segmentation.

867
01:12:33,790 --> 01:12:36,690
Ki sa ki te pase?

868
01:12:36,690 --> 01:12:41,650
Valgrind aktyèlman di nou ki kote li ye.

869
01:12:41,650 --> 01:12:43,050
Rale soti yon ti jan.

870
01:12:43,050 --> 01:12:46,040
Li sanble tankou li k ap pase nan fonksyon insert nou an,

871
01:12:46,040 --> 01:12:53,420
kote nou gen yon Read envalid nan gwosè 4 nan insert, liy 60.

872
01:12:53,420 --> 01:13:03,590
Ann al retounen lakay yo epi wè sa k ap pase sou isit la.

873
01:13:03,590 --> 01:13:05,350
Rale soti vrèman rapid.

874
01:13:05,350 --> 01:13:14,230
Mwen vle asire w ke li pa ale nan kwen an nan ekran an pou nou ka wè tout bagay.

875
01:13:14,230 --> 01:13:18,760
Rale ke nan yon ti jan. Byen.

876
01:13:18,760 --> 01:13:35,030
Scroll down, ak pwoblèm nan se dwa isit la.

877
01:13:35,030 --> 01:13:40,120
Kisa k ap pase si nou jwenn desann ak ne nou an ki ajou a deja nil,

878
01:13:40,120 --> 01:13:44,010
ne paran nou an se nil, kidonk si nou gade moute nan anpil tèt, isit la nan dwa -

879
01:13:44,010 --> 01:13:47,340
si sa a riban pandan y ap pa janm aktyèlman ègzekutra

880
01:13:47,340 --> 01:13:52,330
paske valè aktyèl nou an, se nil - rasin nou an, se nil konsa akt se nil -

881
01:13:52,330 --> 01:13:57,810
Lè sa a, paran nou an pa janm vin mete akt oswa nan yon valè ki valab,

882
01:13:57,810 --> 01:14:00,580
se konsa, paran ap tou ap nil.

883
01:14:00,580 --> 01:14:03,700
Nou bezwen sonje yo tcheke pou ki

884
01:14:03,700 --> 01:14:08,750
pa tan an nou jwenn desann isit la, epi nou kòmanse gen aksè nan valè paran an.

885
01:14:08,750 --> 01:14:13,190
Se konsa, sa k ap pase? Byen, si paran an se nil -

886
01:14:13,190 --> 01:14:17,990
si (paran == nil) - Lè sa a, nou konnen ke

887
01:14:17,990 --> 01:14:19,530
gen pa dwe anyen nan pyebwa sa a.

888
01:14:19,530 --> 01:14:22,030
Nou dwe eseye insert li nan rasin lan.

889
01:14:22,030 --> 01:14:32,570
Nou ka fè sa pa jis mete rasin lan egal a ne a nouvo.

890
01:14:32,570 --> 01:14:40,010
Lè sa a, nan pwen sa a, nou pa aktyèlman vle ale nan tout bagay sa yo ak lòt.

891
01:14:40,010 --> 01:14:44,780
Olye de sa, dwa isit la, nou ka fè swa yon lòt bagay-si-lòt bagay,

892
01:14:44,780 --> 01:14:47,610
oswa nou te ka konbine tout bagay moute isit la nan yon lòt bagay,

893
01:14:47,610 --> 01:14:56,300
men isit la nou pral jis itilize lòt moun, e fè li fason sa.

894
01:14:56,300 --> 01:14:59,030
Koulye a, nou ap ale nan teste a asire w ke paran nou an se pa nil

895
01:14:59,030 --> 01:15:02,160
anvan Lè sa a, aktyèlman ap eseye gen aksè a jaden li yo.

896
01:15:02,160 --> 01:15:05,330
Sa a ap ede nou evite fay la segmentation.

897
01:15:05,330 --> 01:15:14,740
Se konsa, nou kite fimen, rale soti, konpile, kouri.

898
01:15:14,740 --> 01:15:18,130
>> Pa gen erè, men nou toujou gen yon pakèt moun sou fwit memwa

899
01:15:18,130 --> 01:15:20,650
paske nou pa t 'libere nenpòt nan nœuds nou an.

900
01:15:20,650 --> 01:15:24,350
Men, si n 'al jwenn moute isit la epi nou gade kopi enprime nou an,

901
01:15:24,350 --> 01:15:30,880
nou wè ke, byen, sanble tout mete anndan nou yo te retounen vre, ki se bon.

902
01:15:30,880 --> 01:15:33,050
Mete anndan yo, yo tout verite a,

903
01:15:33,050 --> 01:15:36,670
ak Lè sa a, konprann ki apwopriye apèl yo se verite tou.

904
01:15:36,670 --> 01:15:41,510
>> Bon travay! Li sanble ke nou te avèk siksè ekri insert.

905
01:15:41,510 --> 01:15:47,430
Sa a tout nou gen pou Specification Set Pwoblèm semèn sa a la.

906
01:15:47,430 --> 01:15:51,720
Youn nan defi plezi panse sou ki jan pou ou ta aktyèlman ale nan

907
01:15:51,720 --> 01:15:55,340
ak gratis nan tout nœuds yo nan pyebwa sa a.

908
01:15:55,340 --> 01:15:58,830
Nou ka fè sa yon nimewo nan diferan fason,

909
01:15:58,830 --> 01:16:01,930
men m ap kite sa jiska ou eksperyans,

910
01:16:01,930 --> 01:16:06,080
epi kòm yon defi plezi, eseye, epi fè sèten ke ou ka asire ou ke

911
01:16:06,080 --> 01:16:09,490
ki rapò sa a Valgrind retounen pa gen okenn erè e pa gen fwit.

912
01:16:09,490 --> 01:16:12,880
>> Bon chans sou Huffman seri semèn sa a nan pwoblèm kodaj,

913
01:16:12,880 --> 01:16:14,380
epi n ap wè ou semèn pwochen!

914
01:16:14,380 --> 01:16:17,290
[CS50.TV]