1
00:00:00,000 --> 00:00:02,770
[Powered by Google Translate] [Sekcio 7: Pli Vasta]

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

3
00:00:05,090 --> 00:00:07,930
[Jen CS50] [CS50.TV]

4
00:00:07,930 --> 00:00:10,110
Bone. Do kiel mi diris en mia retpoŝto,

5
00:00:10,110 --> 00:00:14,060
ĉi tiu tuj estos duuma arbo-intensivaj sekcio.

6
00:00:14,060 --> 00:00:16,820
Sed estas ne, ke multaj demandoj.

7
00:00:16,820 --> 00:00:18,920
Do ni provos kaj nudigos ĉiu demando

8
00:00:18,920 --> 00:00:25,430
kaj iru al dolora detalo de ĉiuj bonaj manieroj de fari tion.

9
00:00:25,430 --> 00:00:31,200
Do ĝuste en la komenco, ni iru tra specimeno desegnoj de duumaj arboj kaj aĵoj.

10
00:00:31,200 --> 00:00:35,970
Do jen, "Memoru ke duuma arbo havas nodoj simila al tiuj de ligitaj listo,

11
00:00:35,970 --> 00:00:38,150
krom anstataŭ unu puntero estas du: unu por la maldekstra 'infano'

12
00:00:38,150 --> 00:00:41,950
kaj unu por la rajto 'infano'. "

13
00:00:41,950 --> 00:00:45,630
Do duuma arbo estas simple kiel ligillisto,

14
00:00:45,630 --> 00:00:47,910
krom la struct tuj havos du punteros.

15
00:00:47,910 --> 00:00:51,390
Estas trinary arboj, kiuj estas tuj havas tri punteros,

16
00:00:51,390 --> 00:00:56,540
estas N-_ary_ arboj, kiuj nur devas genérico puntero

17
00:00:56,540 --> 00:01:00,320
ke vi tiam devas malloc esti sufiĉe granda por havi

18
00:01:00,320 --> 00:01:04,840
sufiĉe punteros al ĉiuj eblaj infanoj.

19
00:01:04,840 --> 00:01:08,200
Do duuma arbo ĝuste okazas havi konstantan numeron de du.

20
00:01:08,200 --> 00:01:11,260
Se vi volas, vi povas doni ligillisto kiel unuloka arbo,

21
00:01:11,260 --> 00:01:15,360
sed mi ne kredas al neniu nomas ĝin tiel.

22
00:01:15,360 --> 00:01:18,060
"Desegnu skatoloj-kaj-sagojn diagramon de binara arbo nodo

23
00:01:18,060 --> 00:01:24,110
enhavanta Nate preferataj numeron, 7, kie ĉiu infano puntero estas nula. "

24
00:01:24,110 --> 00:01:27,780
Do iPad modo.

25
00:01:27,780 --> 00:01:30,280
>> Ĝi tuj estos bela simpla.

26
00:01:30,280 --> 00:01:36,150
Ni nur havos nodo, mi desegnas ĝin kiel kvadrato.

27
00:01:36,150 --> 00:01:38,730
Kaj mi desegni la valorojn en ĉi tie.

28
00:01:38,730 --> 00:01:41,090
Do la valoro iros en tie,

29
00:01:41,090 --> 00:01:44,770
kaj tiam ĉi tie ni havos la maldekstra puntero sur la maldekstra kaj la dekstra puntero dekstre.

30
00:01:44,770 --> 00:01:50,430
Kaj estas tre tiom konvencio nomi ĝin maldekstren kaj dekstren la puntero nomoj.

31
00:01:50,430 --> 00:01:52,460
Ambaŭ tuj estos nula.

32
00:01:52,460 --> 00:01:57,870
Tio nur estas nula, kaj tio nur esti nula.

33
00:01:57,870 --> 00:02:03,630
Okay. Do apogi ĉi tien.

34
00:02:03,630 --> 00:02:05,700
"Kun ligitaj listo, ni nur devis stoki puntero

35
00:02:05,700 --> 00:02:09,639
al la unua nodo en la listo por memori la tuta ligitaj listo, aŭ la tuta listo.

36
00:02:09,639 --> 00:02:11,650
Same, kun arboj, ni nur devas stoki puntero

37
00:02:11,650 --> 00:02:13,420
al sola nodo por memori la tuta arbo.

38
00:02:13,420 --> 00:02:15,980
Ĉi nodo estas strato la 'radikon' el la arbo.

39
00:02:15,980 --> 00:02:18,320
Konstruu sur via diagramon de antaŭ aŭ desegni nova

40
00:02:18,320 --> 00:02:21,690
tia, ke vi havas skatolojn-kaj-sagojn priskribo de duuma arbo

41
00:02:21,690 --> 00:02:25,730
kun la la valoron 7, tiam 3 en la maldekstra,

42
00:02:25,730 --> 00:02:32,760
tiam 9 sur la dekstra, kaj tiam 6 dekstre de la 3. "

43
00:02:32,760 --> 00:02:34,810
Ni vidu se mi povas memori ĉiuj, ke en mia kapo.

44
00:02:34,810 --> 00:02:37,670
Do tiu tuj estos nia radiko tien.

45
00:02:37,670 --> 00:02:41,600
Ni havas iom puntero ie, iu kiun ni vokos radiko,

46
00:02:41,600 --> 00:02:45,140
kaj ĝin indikante ĉi ulo.

47
00:02:45,140 --> 00:02:48,490
Nun fari novan nodo,

48
00:02:48,490 --> 00:02:52,870
Kion ni havas, 3 en la maldekstra?

49
00:02:52,870 --> 00:02:57,140
Do nova nodo kun 3, kaj ĝi komence notas nula.

50
00:02:57,140 --> 00:02:59,190
Mi ĵus metis N.

51
00:02:59,190 --> 00:03:02,250
Nun ni volas fari tiu iru al la maldekstra de 7.

52
00:03:02,250 --> 00:03:06,840
Do ni ŝanĝi ĉi puntero nun notas al ĉi ulo.

53
00:03:06,840 --> 00:03:12,420
Kaj ni fari same. Ni volas 9 pli tie

54
00:03:12,420 --> 00:03:14,620
kiu komence nur diras nula.

55
00:03:14,620 --> 00:03:19,600
Ni tuj ŝanĝos ĉi pointer, punkto al 9,

56
00:03:19,600 --> 00:03:23,310
kaj nun ni volas meti 6 al la rajto de 3.

57
00:03:23,310 --> 00:03:32,170
Do tuj - fari 6.

58
00:03:32,170 --> 00:03:34,310
Kaj tiu ulo notos tie.

59
00:03:34,310 --> 00:03:38,320
Okay. Do jen ĉio petas al ni fari.

60
00:03:38,320 --> 00:03:42,770
>> Nun ni iru super iu terminaro.

61
00:03:42,770 --> 00:03:46,690
Ni jam parolis pri kiel la radiko de la arbo estas la supre-pli nodo en la arbo.

62
00:03:46,690 --> 00:03:54,720
Tiu, kiu enhavis 7. La nodoj ĉe la malsupro de la arbo estas nomitaj la folioj.

63
00:03:54,720 --> 00:04:01,240
Ajna nodo kiu nur havas nula kiel liaj filoj estas folio.

64
00:04:01,240 --> 00:04:03,680
Do ĝi estas ebla, se nia duuma arbo estas nur simpla nodo,

65
00:04:03,680 --> 00:04:10,130
ke arbo estas folio, kaj tio estas ĝi.

66
00:04:10,130 --> 00:04:12,060
"La 'alteco' de la arbo estas la nombro de lupolo vi devas fari

67
00:04:12,060 --> 00:04:16,620
akiri de la supro al folio. "

68
00:04:16,620 --> 00:04:18,640
Ni ricevos en, en dua, la diferenco

69
00:04:18,640 --> 00:04:21,940
inter ekvilibrigita kaj desequilibradas duumaj arboj,

70
00:04:21,940 --> 00:04:29,470
sed nuntempe, la tuta alteco de ĉi tiu arbo

71
00:04:29,470 --> 00:04:34,520
Mi dirus estas 3, kvankam se oni kalkulu la numeron de lupolo

72
00:04:34,520 --> 00:04:39,710
vi devas fari por atingi al 9, tiam ĝi estas vere nur altecon de 2.

73
00:04:39,710 --> 00:04:43,340
Ĝuste nun ĉi tiu estas desequilibrado duuma arbo,

74
00:04:43,340 --> 00:04:49,840
sed ni parolis pri ekvilibra kiam alvenas al esti grava.

75
00:04:49,840 --> 00:04:52,040
Do nun ni povas paroli pri nodoj en arbo en terminoj

76
00:04:52,040 --> 00:04:54,700
relativa al la aliaj nodoj en la arbo.

77
00:04:54,700 --> 00:04:59,730
Do nun ni havas gepatrojn, infanojn, gefratoj, prapatroj, kaj posteuloj.

78
00:04:59,730 --> 00:05:05,650
Ili estas belaj komuna senco, kion ili signifas.

79
00:05:05,650 --> 00:05:09,610
Se ni petas - tio la gepatroj.

80
00:05:09,610 --> 00:05:12,830
Do kio estas la patro de 3?

81
00:05:12,830 --> 00:05:16,090
[Studentoj] 7. >> Jes. La patro estas ĝuste tuj estos kio notas al vi.

82
00:05:16,090 --> 00:05:20,510
Do kion estas la infanoj de 7?

83
00:05:20,510 --> 00:05:23,860
[Studentoj] 3 kaj 9. >> Jes.

84
00:05:23,860 --> 00:05:26,460
Rimarku ke "infanoj" laŭvorte signifas infanoj,

85
00:05:26,460 --> 00:05:31,010
tiel 6 ne apliki, ĉar ĝi estas kiel pranepo.

86
00:05:31,010 --> 00:05:35,540
Sed tiam, se ni iros posteuloj, do kio estas la posteuloj de 7?

87
00:05:35,540 --> 00:05:37,500
[Studentoj] 3, 6 kaj 9. >> Jes.

88
00:05:37,500 --> 00:05:42,330
La posteuloj de la radika vertico tuj estos ĉio en la arbo,

89
00:05:42,330 --> 00:05:47,950
krom eble la radika vertico mem, se vi ne volas konsideri ke posteulo.

90
00:05:47,950 --> 00:05:50,750
Kaj fine, prapatroj, do tio estas la kontraŭa direkto.

91
00:05:50,750 --> 00:05:55,740
Do kio estas la prapatroj de 6?

92
00:05:55,740 --> 00:05:58,920
[Studentoj] 3 kaj 7. >> Jes. 9 ne estas inkluditaj.

93
00:05:58,920 --> 00:06:02,520
Estas nur la rekta kasto reen al la radiko

94
00:06:02,520 --> 00:06:13,230
tuj estos viaj prapatroj.

95
00:06:13,230 --> 00:06:16,300
>> "Ni diros ke duuma arbo estas 'ordigitaj' se por ĉiu nodo en la arbo,

96
00:06:16,300 --> 00:06:19,530
ĉiuj liaj posteuloj maldekstre havas malpli valoroj

97
00:06:19,530 --> 00:06:22,890
kaj ĉiuj sur la dekstra havas pli granda valoroj.

98
00:06:22,890 --> 00:06:27,060
Ekzemple, la arbo super estas ordigita sed ĝi ne estas la sola ebla ordigita aranĝo. "

99
00:06:27,060 --> 00:06:30,180
Antaŭ ol ni atingos tion,

100
00:06:30,180 --> 00:06:36,420
ordigita duuma arbo estas konata ankaŭ kiel duuma serĉarbo.

101
00:06:36,420 --> 00:06:38,660
Ĉi tie ni okazi esti nomante ĝin ordigita duuma arbo,

102
00:06:38,660 --> 00:06:41,850
sed mi neniam aŭdis ĝin nomis ordita duuma arbo antaŭe,

103
00:06:41,850 --> 00:06:46,650
kaj sur kvizon ni estas multe pli emas meti duuma serĉarbo.

104
00:06:46,650 --> 00:06:49,250
Ili estas unu kaj la sama,

105
00:06:49,250 --> 00:06:54,580
kaj gravas vin rekoni la distingon inter duuma arbo kaj duuma serĉarbo.

106
00:06:54,580 --> 00:06:58,830
A duuma arbo estas nur arbo kiu antaŭ du aĵojn.

107
00:06:58,830 --> 00:07:02,120
Ĉiu nodo notas al du aĵoj.

108
00:07:02,120 --> 00:07:06,310
Ne estas rezonado pri la valoroj kiuj notas al.

109
00:07:06,310 --> 00:07:11,370
Do kiel ĉi tie, ĉar ĝi estas duuma serĉo arbo,

110
00:07:11,370 --> 00:07:14,030
Ni scias, ke se ni iros restis el 7,

111
00:07:14,030 --> 00:07:16,670
tiam ĉiuj el la valoroj kiujn ni povas eble atingi

112
00:07:16,670 --> 00:07:19,310
irante restis el 7 devas esti malpli ol 7.

113
00:07:19,310 --> 00:07:24,070
Rimarku ke ĉiuj valoroj malpli ol 7 estas 3 kaj 6.

114
00:07:24,070 --> 00:07:26,040
Tiuj estas ĉiuj maldekstre de 7.

115
00:07:26,040 --> 00:07:29,020
Se ni iras al la dekstra de 7, ĉio devas esti pli granda ol 7,

116
00:07:29,020 --> 00:07:33,220
tiel 9 estas dekstre de 7, tial ni estas bonaj.

117
00:07:33,220 --> 00:07:36,150
Ĉi tiu ne estas la kazo por duuma arbo,

118
00:07:36,150 --> 00:07:40,020
por regula duuma arbo povas nur havi 3 ĉe la supro, 7 al la maldekstra,

119
00:07:40,020 --> 00:07:47,630
9 al la maldekstra de 7; ne estas ordo de valoroj ajn.

120
00:07:47,630 --> 00:07:56,140
Nun, ni ne vere faras tion, ĉar ĝi estas teda kaj nenecesa,

121
00:07:56,140 --> 00:07:59,400
sed "provi desegni multajn ordigis arboj kiel vi povas pensi pri

122
00:07:59,400 --> 00:08:01,900
uzante la numeroj 7, 3, 9, kaj 6.

123
00:08:01,900 --> 00:08:06,800
Kiom da distingaj aranĝoj estas tie? Kio estas la alteco de ĉiu tiu? "

124
00:08:06,800 --> 00:08:10,480
>> Ni faros paro, sed la ĉefa ideo estas,

125
00:08:10,480 --> 00:08:16,530
ĉi estas neniel unika prezento de duuma arbo kiu enhavas tiujn valorojn.

126
00:08:16,530 --> 00:08:22,760
Ĉiuj ni bezonas estas iuj duuma arbo kiu enhavas 7, 3, 6, kaj 9.

127
00:08:22,760 --> 00:08:25,960
Alia ebla valida tiu estus la radiko estas 3,

128
00:08:25,960 --> 00:08:30,260
iru al la maldekstra kaj ĝi estas 6, iru al la maldekstra kaj estas 7,

129
00:08:30,260 --> 00:08:32,730
iri al la maldekstra kaj estas 9.

130
00:08:32,730 --> 00:08:36,169
Tio estas perfekte valida duuma serĉarbo.

131
00:08:36,169 --> 00:08:39,570
Ne tre helpema, ĉar ĝi estas nur kiel ligitaj listo

132
00:08:39,570 --> 00:08:43,750
kaj ĉiuj el tiuj indikoj estas nur nula.

133
00:08:43,750 --> 00:08:48,900
Sed ĝi estas valida arbo. Yeah?

134
00:08:48,900 --> 00:08:51,310
[Studenta] Do ne la valorojn devas esti pli granda ĉe la dekstra?

135
00:08:51,310 --> 00:08:56,700
Aŭ ĉu tio -? >> Tiuj Mi intencis iri al la alia vojo.

136
00:08:56,700 --> 00:09:00,960
Ekzistas ankaux - jes, ni ŝanĝos tion.

137
00:09:00,960 --> 00:09:07,770
9, 7, 6, 3. Bonan catch.

138
00:09:07,770 --> 00:09:11,730
Ĝi ankoraŭ devas obei kion duuma arbo serĉo supozas fari.

139
00:09:11,730 --> 00:09:15,650
Do ĉio al la maldekstra devas esti malpli ol iu donita vertico.

140
00:09:15,650 --> 00:09:23,180
Ni povus simple movi, diru, ĉi 6 kaj metis ĝin ĉi tie.

141
00:09:23,180 --> 00:09:26,880
Ne, ni ne povas. Kial mi daŭre fari tion?

142
00:09:26,880 --> 00:09:35,350
Ni do - jen 6, tie estas 7, 6 poentojn al 3.

143
00:09:35,350 --> 00:09:39,290
Ĉi tiu estas ankoraŭ valida duuma serĉarbo.

144
00:09:39,290 --> 00:09:49,260
Kio estas erara se mi - ni vidu se mi povas veni supren kun aranĝo.

145
00:09:49,260 --> 00:09:52,280
Yeah, okay. Do kio estas malbone en ĉi tiu arbo?

146
00:09:52,280 --> 00:10:08,920
Mi supozas Mi jam donis al vi aludo, ke estas io malĝusta kun ĝi.

147
00:10:08,920 --> 00:10:14,430
Kial mi daŭre fari tion?

148
00:10:14,430 --> 00:10:18,510
Okay. Ĉi aspektas racia.

149
00:10:18,510 --> 00:10:22,590
Se ni rigardas ĉiu nodo, kiel 7, tiam al la maldekstra de 7 estas 3.

150
00:10:22,590 --> 00:10:24,960
Do ni havas 3, la aĵo kiu estas dekstre de 3 estas 6.

151
00:10:24,960 --> 00:10:27,750
Kaj se vi rigardas 6, la afero dekstre de 6 estas 9.

152
00:10:27,750 --> 00:10:30,910
Do kial estas ĉi ne estas valida duuma serĉo arbo?

153
00:10:30,910 --> 00:10:36,330
[Studentoj] 9 estas ankoraŭ al la maldekstra de 7. >> Jes.

154
00:10:36,330 --> 00:10:43,710
Ĝi devas esti vera, ke ĉiuj valoroj povas eble atingi irante al la maldekstra de 7 estas malpli ol 7.

155
00:10:43,710 --> 00:10:49,120
Se ni iras restis el 7, ni atingos 3 kaj ni povas ankoraŭ atingos 6,

156
00:10:49,120 --> 00:10:52,520
ni povas ankoraŭ ricevi al 9, sed por esti irinta malpli ol 7,

157
00:10:52,520 --> 00:10:55,070
ni ne povos alveni al cifero kiu estas pli granda ol 7.

158
00:10:55,070 --> 00:10:59,830
Do tiu estas ne valida duuma serĉarbo.

159
00:10:59,830 --> 00:11:02,330
>> Mia frato efektive havis intervjuon demando

160
00:11:02,330 --> 00:11:07,760
kiu estis esence tion, nur kodo ion por validigi

161
00:11:07,760 --> 00:11:10,500
ĉu arbo estas duuma serĉo arbo,

162
00:11:10,500 --> 00:11:13,580
kaj do la unua kiu faris estis nur kontroli por vidi

163
00:11:13,580 --> 00:11:17,020
se la maldekstra kaj dekstra estas ĝustaj, kaj tiam persisti tie malsupre.

164
00:11:17,020 --> 00:11:19,700
Sed vi povas ne nur fari tion, vi devas konservi trako

165
00:11:19,700 --> 00:11:22,550
de la fakto ke nun ke mi foriris restis el 7,

166
00:11:22,550 --> 00:11:26,340
ĉio en ĉi subárbol devas esti malpli ol 7.

167
00:11:26,340 --> 00:11:28,430
La ĝentila algoritmo bezonas konservi trako

168
00:11:28,430 --> 00:11:35,970
de la baroj ke la valoroj povas eble falos in

169
00:11:35,970 --> 00:11:38,360
Ni ne iros tra ĉiuj el ili.

170
00:11:38,360 --> 00:11:41,630
Estas bela rekursieca rilato,

171
00:11:41,630 --> 00:11:44,810
kvankam ni ne alvenis al tiuj, aux ni ne atingos tiujn,

172
00:11:44,810 --> 00:11:47,030
difinanta kiom tie efektive estas.

173
00:11:47,030 --> 00:11:53,180
Do estas 14 el ili.

174
00:11:53,180 --> 00:11:56,020
La ideo pri kiel vi farus matematike estas kiel,

175
00:11:56,020 --> 00:11:59,770
vi povas elekti ajnan sola unu al esti la radiko nodo,

176
00:11:59,770 --> 00:12:03,160
kaj poste, se mi elektas 7 esti la radiko nodo,

177
00:12:03,160 --> 00:12:08,150
tiam estas, ekzemple, iuj nombroj kiu povas iri estos mia maldekstra nodo,

178
00:12:08,150 --> 00:12:10,440
kaj tie estas kelkaj nombroj kiuj povas esti mia dekstra nodo,

179
00:12:10,440 --> 00:12:15,090
sed se mi n tuta nombroj, tiam la kvanto kiu povas iri al la maldekstra

180
00:12:15,090 --> 00:12:18,820
plus la kvanto kiu povas iri al la rajto estas n - 1.

181
00:12:18,820 --> 00:12:26,130
Do el la ceteraj nombroj, ili devas povi iri ĉu al la maldekstra aŭ la dekstra.

182
00:12:26,130 --> 00:12:31,580
Ŝajnas malfacile, ke se mi metis 3 unuaj tiam ĉio devas iri al la maldekstra,

183
00:12:31,580 --> 00:12:35,080
sed se mi metis 7, tiam iuj aferoj povas iri la la maldekstra kaj iuj aĵoj povas iri al la rajto.

184
00:12:35,080 --> 00:12:39,570
Kaj por '3 unue 'I meant ĉiu povas iri al la rajto.

185
00:12:39,570 --> 00:12:42,350
Estas vere, vi nur devas pensi pri ĝi kiel,

186
00:12:42,350 --> 00:12:47,980
kiom da aferoj povas iri la sekvantan nivelon de la arbo.

187
00:12:47,980 --> 00:12:50,420
Kaj temas esti 14; aŭ vi povas desegni ĉiuj ili,

188
00:12:50,420 --> 00:12:54,650
kaj poste vi ricevos 14.

189
00:12:54,650 --> 00:13:01,120
>> Reiros tien,

190
00:13:01,120 --> 00:13:03,510
"Mastro duumaj arboj estas cool ĉar ni povas serĉi per ili

191
00:13:03,510 --> 00:13:06,910
en tre simila maniero serĉado super ordo tabelo.

192
00:13:06,910 --> 00:13:10,120
Por tion fari, ni komencu en la radiko kaj labori nia vojo laŭ la arbo

193
00:13:10,120 --> 00:13:13,440
al folioj, kontrolanta ĉiu nodo de valoroj kontraŭ la valoroj ni sercxas.

194
00:13:13,440 --> 00:13:15,810
Se la nuna nodo valoro estas malpli ol la valoro ni serĉas,

195
00:13:15,810 --> 00:13:18,050
vi iros apud la nodo la dekstra infano.

196
00:13:18,050 --> 00:13:20,030
Alie, vi iru al la nodo la maldekstra infano.

197
00:13:20,030 --> 00:13:22,800
En iu momento, vi jam estas trovi la valoro kiun vi serĉas, vi kuros en nula,

198
00:13:22,800 --> 00:13:28,520
indikante la valoro ne estas en la arbo. "

199
00:13:28,520 --> 00:13:32,450
Mi devas redesegni la arbo ni havis antaŭe; ke prenos duan.

200
00:13:32,450 --> 00:13:38,280
Sed ni volas serĉi ĉu 6, 10, kaj 1 estas en la arbo.

201
00:13:38,280 --> 00:13:49,180
Do kio estis, 7, 9, 3, 6. Okay.

202
00:13:49,180 --> 00:13:52,730
La nombroj vi volas rigardi supren, ni volas serĉi 6.

203
00:13:52,730 --> 00:13:55,440
Kiel funkcias tiu algoritmo laboro?

204
00:13:55,440 --> 00:14:03,040
Nu, ni ankaŭ havas iun radikon puntero al nia arbo.

205
00:14:03,040 --> 00:14:12,460
Kaj ni irus al la radiko kaj diru, estas tiu valoro egalas al la valoro ni sercxas?

206
00:14:12,460 --> 00:14:15,000
Do ni serĉas 6, tiel ĝi ne estas egalaj.

207
00:14:15,000 --> 00:14:20,140
Do ni observu tuj, kaj nun ni diras, bone, do 6 estas malpli ol 7.

208
00:14:20,140 --> 00:14:23,940
Ĉu tio signifas ke ni volas iri al la maldekstra, aŭ ĉu ni volas iri al la dekstra?

209
00:14:23,940 --> 00:14:27,340
[Studenta] Maldekstra. >> Jes.

210
00:14:27,340 --> 00:14:33,340
Estas signife pli facila, ĉiuj vi devas fari estas desegni unu ebla nodo de la arbo

211
00:14:33,340 --> 00:14:37,760
kaj tiam vi ne batu - anstataŭ klopodi pensi en via kapo,

212
00:14:37,760 --> 00:14:40,020
estas bone, se ĝi estas malpli, mi iros maldekstren aŭ iri dekstren,

213
00:14:40,020 --> 00:14:43,030
nur rigardante ĉi tiun foton, estas tre klara, ke mi devas iri al la maldekstra

214
00:14:43,030 --> 00:14:47,700
se ĉi tiu nodo estas pli granda ol la valoro kiu Mi serĉas.

215
00:14:47,700 --> 00:14:52,600
Do vi iras al la maldekstra, nun mi estas ĉe 3.

216
00:14:52,600 --> 00:14:57,770
Mi volas - 3 estas malpli ol la valoro Mi serĉas, kiu estas 6.

217
00:14:57,770 --> 00:15:03,420
Do ni iru al la dekstra, kaj nun mi finas je 6,

218
00:15:03,420 --> 00:15:07,380
kiu estas la valoro Mi serĉas, do mi revenos vera.

219
00:15:07,380 --> 00:15:15,760
La sekvan valoron mi iros serĉi estas 10.

220
00:15:15,760 --> 00:15:23,230
Okay. Do 10, nun, tuj - ekstermigxos tiu - tuj sekvu la radiko.

221
00:15:23,230 --> 00:15:27,670
Nun, 10 tuj estos pli granda ol 7, do mi volas rigardi al la rajto.

222
00:15:27,670 --> 00:15:31,660
Mi tuj venos ĉi tien, 10 tuj estos pli granda ol 9,

223
00:15:31,660 --> 00:15:34,520
do mi tuj volas rigardi al la rajto.

224
00:15:34,520 --> 00:15:42,100
Mi venis ĉi tien, sed ĉi tien nun mi estas ĉe nula.

225
00:15:42,100 --> 00:15:44,170
Kion mi faru se mi batis nula?

226
00:15:44,170 --> 00:15:47,440
[Studenta] Reveno falsa? >> Jes. Mi ne trovis 10.

227
00:15:47,440 --> 00:15:49,800
1 tuj estos preskaŭ identa kazo,

228
00:15:49,800 --> 00:15:51,950
krom ĝi estas ĝuste tuj estos spegulita; anstataŭ serĉi

229
00:15:51,950 --> 00:15:56,540
malsupren la dekstra flanko, mi tuj rigardos la maldekstra flanko.

230
00:15:56,540 --> 00:16:00,430
>> Nun mi kredas ke ni fakte atingos kodo.

231
00:16:00,430 --> 00:16:04,070
Jen kie - malfermi la CS50 aparaton kaj navigi vian vojon tie,

232
00:16:04,070 --> 00:16:07,010
sed vi povas ankaŭ simple fari ĝin en la spaco.

233
00:16:07,010 --> 00:16:09,170
Estas probable ideala por fari ĝin en la spaco,

234
00:16:09,170 --> 00:16:13,760
ĉar ni povas labori en la spaco.

235
00:16:13,760 --> 00:16:19,170
"Unue ni bezonas novan tipon difino por duuma arbo nodo enhavanta int valoroj.

236
00:16:19,170 --> 00:16:21,400
Uzante la Boilerplate typedef sube,

237
00:16:21,400 --> 00:16:24,510
krei novan tipon difino por nodo en duuma arbo.

238
00:16:24,510 --> 00:16:27,930
Se vi pusxis. . . "Bla, bla, bla. Okay.

239
00:16:27,930 --> 00:16:30,380
Do ni metis la Boilerplate tie,

240
00:16:30,380 --> 00:16:41,630
typedef struct nodo, kaj nodo. Yeah, okay.

241
00:16:41,630 --> 00:16:44,270
Do kio estas la kampoj ni tuj volas en nia nodo?

242
00:16:44,270 --> 00:16:46,520
[Studenta] Mez kaj tiam du punteros?

243
00:16:46,520 --> 00:16:49,700
>> Mez valoro, du punteros? Kiel mi skribas la punteros?

244
00:16:49,700 --> 00:16:58,440
[Studenta] struct. >> Mi devus zoom in Yeah, do struct nodo * restis,

245
00:16:58,440 --> 00:17:01,320
kaj struct nodo * pravas.

246
00:17:01,320 --> 00:17:03,460
Kaj memoru la diskuto de la lasta fojo,

247
00:17:03,460 --> 00:17:15,290
ke tio ne havas senson, ĉi ne havas senson,

248
00:17:15,290 --> 00:17:18,270
ĉi ne havas senson.

249
00:17:18,270 --> 00:17:25,000
Vi bezonas cxion tie por difini ĉi rekursie struct.

250
00:17:25,000 --> 00:17:27,970
Okay, do tio estas kion niaj arbo tuj aspekti.

251
00:17:27,970 --> 00:17:37,670
Se ni faris trinary arbo, tiam nodo povus aspekti b1, b2, struct nodo * b3,

252
00:17:37,670 --> 00:17:43,470
kie b estas branĉo - fakte, mi pli aŭdas, ĝi forlasis mezo, rajto, sed kion ajn.

253
00:17:43,470 --> 00:17:55,610
Ni nur zorgas pri duuma, do bone, forlasis.

254
00:17:55,610 --> 00:17:59,110
"Nun deklari tutmonda nodo * variablo por la radiko de la arbo."

255
00:17:59,110 --> 00:18:01,510
Do ni ne faros tion.

256
00:18:01,510 --> 00:18:08,950
Por fari tion, iomete pli malfacila kaj pli ĝeneraligita,

257
00:18:08,950 --> 00:18:11,570
ni ne havas suman nodo variablo.

258
00:18:11,570 --> 00:18:16,710
Anstataŭe, en ĉefa ni rakontu pri cxiuj niaj nodo aferojn,

259
00:18:16,710 --> 00:18:20,500
kaj tio signifas ke sube, kiam ni komencos kuri

260
00:18:20,500 --> 00:18:23,130
nia enhavas funkcion kaj nia insert funkcio,

261
00:18:23,130 --> 00:18:27,410
anstataŭ nia enhavas funkcion nur uzante tiun tutmondan nodo variablo,

262
00:18:27,410 --> 00:18:34,280
ni havos ĝin prenu kiel argumento al la arbo, ke ni volas procesi.

263
00:18:34,280 --> 00:18:36,650
Havante la malloka variablo devis fari tion facile.

264
00:18:36,650 --> 00:18:42,310
Ni tuj faros tion pli malfacila.

265
00:18:42,310 --> 00:18:51,210
Nun prenu unu minuto aŭ tiel al nur fari ĉi tiajn aferojn,

266
00:18:51,210 --> 00:18:57,690
kie ene de ĉefa vi volas krei ĉi arbo, kaj jen ĉio vi volas fari.

267
00:18:57,690 --> 00:19:04,530
Provu kaj konstrui ĉi arbo en via ĉefa funkcio.

268
00:19:42,760 --> 00:19:47,610
>> Okay. Do, vi eĉ ne devos esti konstruinta la arbo en la tuta vojo ankoraŭ.

269
00:19:47,610 --> 00:19:49,840
Sed neniu havas ion mi povus tiri supren

270
00:19:49,840 --> 00:20:03,130
por montri kiel oni povas komenci konstrui tian arbon?

271
00:20:03,130 --> 00:20:08,080
[Studenta] Iu de banging, klopodante eliri.

272
00:20:08,080 --> 00:20:13,100
[Bowden] Anyone komforta kun sia arbo konstruo?

273
00:20:13,100 --> 00:20:15,520
[Studenta] Certe. Tio ne faris. >> Estas fajna. Ni povas nur fini -

274
00:20:15,520 --> 00:20:26,860
ho, vi povas konservi ĝin? Hura.

275
00:20:26,860 --> 00:20:32,020
Do jen ni havas - ho, mi iomete ekstermigxos.

276
00:20:32,020 --> 00:20:34,770
Mi zoomed en?

277
00:20:34,770 --> 00:20:37,730
Zomi, rulumi eksteren. >> Mi havas demandon. >> Jes?

278
00:20:37,730 --> 00:20:44,410
[Studenta] Kiam vi difinas struct, estas aĵoj kiel inicializado al nenio?

279
00:20:44,410 --> 00:20:47,160
[Bowden] No >> Bone. Do vi devus pravalorizi -

280
00:20:47,160 --> 00:20:50,450
[Bowden] No Kiam vi difinas, aŭ kiam vi deklaras struct,

281
00:20:50,450 --> 00:20:55,600
ĝi ne inicializado defaŭlte; ĝi estas ĵus kiel se vi rakontos al int.

282
00:20:55,600 --> 00:20:59,020
Estas ĝuste la sama aĵo. Estas kiel ĉiu el ĝiaj individuaj kampoj

283
00:20:59,020 --> 00:21:04,460
povas havi rubo valoron en ĝi. >> Kaj ĉu eblas difini - aŭ por deklari struct

284
00:21:04,460 --> 00:21:07,740
en maniero, ke ĝi pravalorizi ilin?

285
00:21:07,740 --> 00:21:13,200
[Bowden] Jes. Do, ŝparvojo inicialización sintakso

286
00:21:13,200 --> 00:21:18,660
tuj aspekti -

287
00:21:18,660 --> 00:21:22,200
Ekzistas du manieroj povas fari ĉi tion. Mi kredas ke ni devus kompili ĝin

288
00:21:22,200 --> 00:21:25,840
certigi Clang ankaŭ faras tion.

289
00:21:25,840 --> 00:21:28,510
La ordo de argumentoj kiu venas en la struct,

290
00:21:28,510 --> 00:21:32,170
vi metis al la ordo de argumentoj ene de tiuj buklaj krampoj.

291
00:21:32,170 --> 00:21:35,690
Do se vi volas pravalorizi ĝin al 9 kaj lasis esti nulaj kaj tiam dekstre esti nula,

292
00:21:35,690 --> 00:21:41,570
estus 9, nula, nula.

293
00:21:41,570 --> 00:21:47,890
La alternativo estas, kaj la redaktoro ne ŝatas tiun sintakson,

294
00:21:47,890 --> 00:21:50,300
kaj ĝi kredas mi volas novan blokon,

295
00:21:50,300 --> 00:22:01,800
sed la alternativo estas io kiel -

296
00:22:01,800 --> 00:22:04,190
ĉi tie, mi metos ĝin sur nova linio.

297
00:22:04,190 --> 00:22:09,140
Vi povas eksplicite diras, mi forgesas la ĝusta sintakso.

298
00:22:09,140 --> 00:22:13,110
Do vi povas eksplicite trakti ilin laŭnome, kaj diru:

299
00:22:13,110 --> 00:22:21,570
. C, aux. Valoro = 9,. Maldekstra = NULL.

300
00:22:21,570 --> 00:22:24,540
Mi konjektas tiuj bezonon esti komoj.

301
00:22:24,540 --> 00:22:29,110
. Dekstra = NULL, do tiamaniere vi ne

302
00:22:29,110 --> 00:22:33,780
vere bezonas scii la ordon de la struct,

303
00:22:33,780 --> 00:22:36,650
kaj kiam vi legas ĉi tion, ĝi estas multe pli eksplicita

304
00:22:36,650 --> 00:22:41,920
pri kio la valoro de esti inicializado al.

305
00:22:41,920 --> 00:22:44,080
>> Ĉi tio okazas al esti unu el la aĵoj kiuj -

306
00:22:44,080 --> 00:22:49,100
tiel, plejparte, C + + estas superaro de C.

307
00:22:49,100 --> 00:22:54,160
Vi povas preni C-kodo, movi ĝin al C + +, kaj ĝi devus kompili.

308
00:22:54,160 --> 00:22:59,570
Tiu estas unu el la aĵoj kiuj C + + ne ebligas, do homoj emas ne fari ĝin.

309
00:22:59,570 --> 00:23:01,850
Mi ne scias se tio estas la sola kialo homoj inklinas ne fari ĝin,

310
00:23:01,850 --> 00:23:10,540
sed la kazo kie mi bezonis uzi ĝin bezonas por labori per C + + kaj do mi ne povis uzi tiun.

311
00:23:10,540 --> 00:23:14,000
Alia ekzemplo de iu kiu ne funkcias kun C + + estas

312
00:23:14,000 --> 00:23:16,940
kiom malloc redonas "void *," teknike,

313
00:23:16,940 --> 00:23:20,200
sed vi povus nur diri char * x = malloc ajn,

314
00:23:20,200 --> 00:23:22,840
kaj ĝi estos aŭtomate estos jxetitaj al char *.

315
00:23:22,840 --> 00:23:25,450
Ke aŭtomata cast ne okazas en C + +.

316
00:23:25,450 --> 00:23:28,150
Tio ne kompili, kaj vi eksplicite devas eldiri

317
00:23:28,150 --> 00:23:34,510
char *, malloc, kion ajn, por elpeli ĝin al char *.

318
00:23:34,510 --> 00:23:37,270
Ne estas multaj aĵoj kiuj C kaj C + + malakordo plu,

319
00:23:37,270 --> 00:23:40,620
sed tiuj estas du.

320
00:23:40,620 --> 00:23:43,120
Do ni iros kun multaj lingvoj.

321
00:23:43,120 --> 00:23:46,150
Sed eĉ se ni ne iros kun tiu sintakso,

322
00:23:46,150 --> 00:23:49,470
kio estas - eble malbona tio?

323
00:23:49,470 --> 00:23:52,170
[Studenta] Mi ne bezonas dereference ĝin? >> Jes.

324
00:23:52,170 --> 00:23:55,110
Memoru ke la sago havas implicitan dereference,

325
00:23:55,110 --> 00:23:58,230
kaj tiel, kiam ni simple temas pri struct,

326
00:23:58,230 --> 00:24:04,300
ni volas uzi. akiri en kampo ene de la struct.

327
00:24:04,300 --> 00:24:07,200
Kaj la sola tempo ni uzas sago estas kiam ni volas fari -

328
00:24:07,200 --> 00:24:13,450
bone, sago estas ekvivalento al -

329
00:24:13,450 --> 00:24:17,020
Tio estas kio ĝi estus signifinta se mi uzis sago.

330
00:24:17,020 --> 00:24:24,600
Ĉiuj sagoj duona, dereference ĉi, nun mi estas ĉe struct, kaj mi povas ricevi la kampo.

331
00:24:24,600 --> 00:24:28,040
Ĉu akiri la kampo rekte aŭ dereference kaj akiri la kampo -

332
00:24:28,040 --> 00:24:30,380
Mi supozas ĉi devus esti valoro.

333
00:24:30,380 --> 00:24:33,910
Sed ĉi tie mi pritraktas nur struct, ne puntero al struct,

334
00:24:33,910 --> 00:24:38,780
kaj tial mi ne povas uzi la sago.

335
00:24:38,780 --> 00:24:47,510
Sed ĉi tiaj aferoj ni povas fari por ĉiuj nodoj.

336
00:24:47,510 --> 00:24:55,790
Ho mia Dio.

337
00:24:55,790 --> 00:25:09,540
Tiu estas 6, 7, kaj 3.

338
00:25:09,540 --> 00:25:16,470
Tiam ni povas starigi la branĉoj en nia arbo, ni povas havi 7 -

339
00:25:16,470 --> 00:25:21,650
ni povas esti, ĝia maldekstra devus celi 3.

340
00:25:21,650 --> 00:25:25,130
Nu do kiel ni faros tion?

341
00:25:25,130 --> 00:25:29,320
[Studentoj, nekomprenebla] >> Jes. La adreso de node3,

342
00:25:29,320 --> 00:25:34,170
kaj se vi ne havas adreson, tiam simple ne kompili.

343
00:25:34,170 --> 00:25:38,190
Sed memoru, ke tiuj estas punteros al la sekvanta nodoj.

344
00:25:38,190 --> 00:25:44,930
La rajto devus celi 9,

345
00:25:44,930 --> 00:25:53,330
kaj 3 devus celi la rajton 6.

346
00:25:53,330 --> 00:25:58,480
Mi kredas ke tiu estas la tuta aro. Ajna komentoj aŭ demandoj?

347
00:25:58,480 --> 00:26:02,060
[Studento, nekomprenebla] La radiko tuj estos 7.

348
00:26:02,060 --> 00:26:08,210
Ni povas nur diri nodo * ptr =

349
00:26:08,210 --> 00:26:14,160
aŭ radiko, = & node7.

350
00:26:14,160 --> 00:26:20,730
>> Por nia celo, ni tuj estos pritraktas insert,

351
00:26:20,730 --> 00:26:25,490
do ni tuj volas skribi funkcion por enmeti en tiun duuma arbo

352
00:26:25,490 --> 00:26:34,230
kaj insert estas neeviteble tuj voki malloc krei novan nodon por ĉi arbo.

353
00:26:34,230 --> 00:26:36,590
Do tion tuj akiri senorda kun la fakto ke iuj nodoj

354
00:26:36,590 --> 00:26:38,590
estas nuntempe en la stako

355
00:26:38,590 --> 00:26:43,680
kaj aliaj nodoj tuj finos la amason kiam ni enmetas ilin.

356
00:26:43,680 --> 00:26:47,640
Ĉi tiu estas perfekte valida, sed la sola kialo

357
00:26:47,640 --> 00:26:49,600
ni povas fari tion en la stako

358
00:26:49,600 --> 00:26:51,840
estas ĉar ĝi estas tia elpensita ekzemplo kiu ni scias

359
00:26:51,840 --> 00:26:56,360
la arbo estas supozata esti konstruita kiel 7, 3, 6, 9.

360
00:26:56,360 --> 00:27:02,970
Se ni ne havas tiun, tiam ni ne devus malloc en la unua loko.

361
00:27:02,970 --> 00:27:06,160
Kiel ni vidos iom poste, ni devus esti malloc'ing.

362
00:27:06,160 --> 00:27:08,570
Ĝuste nun ĝi estas perfekte racia meti sur la pilo,

363
00:27:08,570 --> 00:27:14,750
sed ni ŝanĝos ĉi tion al malloc efektivigo.

364
00:27:14,750 --> 00:27:17,160
Do ĉiu el tiuj estas nun tuj estos iu kiel

365
00:27:17,160 --> 00:27:24,240
nodo * node9 = malloc (sizeof (nodo)).

366
00:27:24,240 --> 00:27:28,040
Kaj nun ni tuj devas fari nian ĉeko.

367
00:27:28,040 --> 00:27:34,010
if (node9 == NULL) - Mi ne volis ke -

368
00:27:34,010 --> 00:27:40,950
revenu 1, kaj tiam ni povos fari node9-> ĉar nun ĝi estas puntero,

369
00:27:40,950 --> 00:27:45,300
valoro = 6, node9-> lasis = NULL,

370
00:27:45,300 --> 00:27:48,930
node9-> dekstra = NULL,

371
00:27:48,930 --> 00:27:51,410
kaj ni tuj devas fari tion por ĉiu el tiuj nodoj.

372
00:27:51,410 --> 00:27:57,490
Do anstataŭe, ni metis ĝin interne de aparta funkcio.

373
00:27:57,490 --> 00:28:00,620
Ni nomas ĝin nodo * build_node,

374
00:28:00,620 --> 00:28:09,050
kaj ĉi tiu estas iom simila al la API ni ofertas por Huffman kodigo.

375
00:28:09,050 --> 00:28:12,730
Ni donas vin initializer funkcioj por arbo

376
00:28:12,730 --> 00:28:20,520
kaj deconstructor "funkcioj" por tiuj arboj kaj la sama por arbaroj.

377
00:28:20,520 --> 00:28:22,570
>> Do jen ni tuj havos initializer funkcio

378
00:28:22,570 --> 00:28:25,170
justaj konstrui nodo por ni.

379
00:28:25,170 --> 00:28:29,320
Kaj tuj vidu preskaux precize kiel ĉi tio.

380
00:28:29,320 --> 00:28:32,230
Kaj mi eĉ tuj estos pigra kaj ne ŝanĝas la nomon de la variablo,

381
00:28:32,230 --> 00:28:34,380
kvankam node9 ne havas senson plu.

382
00:28:34,380 --> 00:28:38,610
Ho, mi supozas node9 valoro ne devus esti 6.

383
00:28:38,610 --> 00:28:42,800
Nun ni povas reveni node9.

384
00:28:42,800 --> 00:28:49,550
Kaj ĉi tie ni devas reveni nula.

385
00:28:49,550 --> 00:28:52,690
Ĉiuj konsentas en tiu muntaĵo-a-nodo funkcio?

386
00:28:52,690 --> 00:28:59,780
Do nun ni povas simple nomas tion konstrui ajna nodo kun donita valoro kaj nula punteros.

387
00:28:59,780 --> 00:29:09,750
Nun ni povas nomi tion, ni povas fari nodon * node9 = build_node (9).

388
00:29:09,750 --> 00:29:25,810
Kaj ni faru. . .

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

390
00:29:33,980 --> 00:29:39,330
Kaj nun ni volas starigi la saman punteros,

391
00:29:39,330 --> 00:29:42,470
krom nun ĉiu estas jam en terminoj de punteros

392
00:29:42,470 --> 00:29:48,480
tial ne plu bezonas la adreson de.

393
00:29:48,480 --> 00:29:56,300
Okay. Do kio estas la lasta afero mi volas fari?

394
00:29:56,300 --> 00:30:03,850
Estas eraro-kontrolanta ke mi ne faras.

395
00:30:03,850 --> 00:30:06,800
Kion konstrui nodo reveno?

396
00:30:06,800 --> 00:30:11,660
[Studento, nekomprenebla] >> Jes. Se malloc malsukcesis, ĝi revenos nula.

397
00:30:11,660 --> 00:30:16,460
Do mi tuj pigre metis ĝin ĉi tie anstataŭ fari kondiĉo por ĉiu.

398
00:30:16,460 --> 00:30:22,320
If (node9 == NULL, aŭ - eĉ pli simpla,

399
00:30:22,320 --> 00:30:28,020
ĉi tiu estas ekvivalento al nur se ne node9.

400
00:30:28,020 --> 00:30:38,310
Do, se ne node9, aŭ ne node6, aŭ ne node3, aŭ ne node7, revenu 1.

401
00:30:38,310 --> 00:30:42,850
Eble ni devus presi malloc malsukcesis, aŭ io.

402
00:30:42,850 --> 00:30:46,680
[Studenta] Is falsa egala al nula tiel?

403
00:30:46,680 --> 00:30:51,290
[Bowden] Ajna nula valoro estas falsaj.

404
00:30:51,290 --> 00:30:53,920
Do nula estas nulo valoro.

405
00:30:53,920 --> 00:30:56,780
Nulo estas nulo valoro. Falsa estas nulo valoro.

406
00:30:56,780 --> 00:31:02,130
Ajna - preskaux la sola 2 nulo valoroj estas nulaj kaj nulo,

407
00:31:02,130 --> 00:31:07,900
falsa estas nur hash difinita kiel nulo.

408
00:31:07,900 --> 00:31:13,030
Tio ankaŭ validas se ni deklarus malloka variablo.

409
00:31:13,030 --> 00:31:17,890
Se ni faris havas nodo * radiko tien,

410
00:31:17,890 --> 00:31:24,150
tiam - la bela afero pri tutmonda variabloj estas, ke ili ĉiam havas komencan valoron.

411
00:31:24,150 --> 00:31:27,500
Tio ne validas por la funkcioj, kiel interne de ĉi tie,

412
00:31:27,500 --> 00:31:34,870
se ni havas, kiel, nodo * aŭ nodo x.

413
00:31:34,870 --> 00:31:37,380
Ni ne havas ideon kion x.value, x.whatever,

414
00:31:37,380 --> 00:31:40,700
aŭ ni povus presi ilin kaj ili povis esti arbitra.

415
00:31:40,700 --> 00:31:44,980
Tio ne validas por la tutmonda variabloj.

416
00:31:44,980 --> 00:31:47,450
Do nodo radiko aŭ nodo x.

417
00:31:47,450 --> 00:31:53,410
Implicite, ĉio tio estas tutmonda, se ne eksplicite inicializado al iu valoro,

418
00:31:53,410 --> 00:31:57,390
havas nula valoro kiel ĝia valoro.

419
00:31:57,390 --> 00:32:01,150
Do jen, nodo * radiko, ni ne eksplicite pravalorizi ĝin al nenion,

420
00:32:01,150 --> 00:32:06,350
do ĝia defaŭlta valoro estos nula, kiu estas la nula valoro de punteros.

421
00:32:06,350 --> 00:32:11,870
La defaŭlta valoro de x tuj signifas ke x.value estas nulo,

422
00:32:11,870 --> 00:32:14,260
x.left estas nula, kaj x.right estas nula.

423
00:32:14,260 --> 00:32:21,070
Do pro tio ke estas struct, ĉiuj el la kampoj de la struct estos nulo valoroj.

424
00:32:21,070 --> 00:32:24,410
Ni ne bezonas uzi tiun ĉi tie, tamen.

425
00:32:24,410 --> 00:32:27,320
[Studenta] La structs estas malsamaj ol aliaj variabloj, kaj la aliaj variabloj estas

426
00:32:27,320 --> 00:32:31,400
rubo valoroj; tiuj estas nuloj?

427
00:32:31,400 --> 00:32:36,220
[Bowden] Aliaj valoroj tro. Do en x, x estos nulo.

428
00:32:36,220 --> 00:32:40,070
Se estas al suma amplekso, ĝi havas komencan valoron. >> Bone.

429
00:32:40,070 --> 00:32:48,950
[Bowden] Aŭ la komenca valoro Vi donis ĝin aŭ nulo.

430
00:32:48,950 --> 00:32:53,260
Mi kredas ke ĝi atentas ĉiujn ĉi.

431
00:32:53,260 --> 00:32:58,390
>> Okay. Do la sekva parto de la demando petas,

432
00:32:58,390 --> 00:33:01,260
"Nun ni volas skribi funkcio nomita enhavas

433
00:33:01,260 --> 00:33:04,930
kun prototipo de bool enhavas int valoro. "

434
00:33:04,930 --> 00:33:08,340
Ni ne faros bool enhavas int valoro.

435
00:33:08,340 --> 00:33:15,110
Nia prototipo tuj aspekti

436
00:33:15,110 --> 00:33:22,380
bool enhavas (int valoro.

437
00:33:22,380 --> 00:33:24,490
Kaj tiam ni ankaŭ tuj pasi ĝin la arbo

438
00:33:24,490 --> 00:33:28,870
kiun ĝi devus esti kontrolanta por vidi se ĝi havas tiun valoron.

439
00:33:28,870 --> 00:33:38,290
Do nodo * arbo). Okay.

440
00:33:38,290 --> 00:33:44,440
Kaj tiam ni povas nomi ĝin per io kiel,

441
00:33:44,440 --> 00:33:46,090
eble ni volos printf aŭ iu.

442
00:33:46,090 --> 00:33:51,040
Enhavas 6, nia radiko.

443
00:33:51,040 --> 00:33:54,300
Tio devus reveni, aŭ vera,

444
00:33:54,300 --> 00:33:59,390
dum enhavas 5 radiko devus reveni falsaj.

445
00:33:59,390 --> 00:34:02,690
Do prenu la duan apliki ĉi.

446
00:34:02,690 --> 00:34:06,780
Vi povas fari tion aŭ ripete aŭ rekursie.

447
00:34:06,780 --> 00:34:09,739
La belan afero pri la maniero ni starigis aĵojn estas ke

448
00:34:09,739 --> 00:34:12,300
ĝi pruntas al nia rekursie solvo multe pli simpla

449
00:34:12,300 --> 00:34:14,719
ol la tutmonda-variablo maniero faris.

450
00:34:14,719 --> 00:34:19,750
Ĉar se ni nur devas enhavas int valoro, tiam ni ne havas manieron de recursing malsupren subárboles.

451
00:34:19,750 --> 00:34:24,130
Ni devus havi apartan helpanto funkcio kiu recurses malsupren la subárboles por ni.

452
00:34:24,130 --> 00:34:29,610
Sed ĉar ni ŝanĝis ĝin por porti la arbon kiel argumento,

453
00:34:29,610 --> 00:34:32,760
kiuj devus esti ĉiam en la unua loko,

454
00:34:32,760 --> 00:34:35,710
nun ni povas recurse pli facile.

455
00:34:35,710 --> 00:34:38,960
Do ripeta aŭ rekursie, ni transiru ambaŭ,

456
00:34:38,960 --> 00:34:46,139
sed ni vidos ke rekursie finas esti sufiĉe facila.

457
00:34:59,140 --> 00:35:02,480
Okay. Ĉu iu havas ion ni povas laboro kun?

458
00:35:02,480 --> 00:35:12,000
>> [Studenta] Mi havas ripeta solvo. >> Bone, ripeta.

459
00:35:12,000 --> 00:35:16,030
Konsentite, ĉi aspektas bona.

460
00:35:16,030 --> 00:35:18,920
Do, volas promeni ni per ĝi?

461
00:35:18,920 --> 00:35:25,780
[Studenta] Certe. Do mi metis temp variablo por akiri la unua nodo de la arbo.

462
00:35:25,780 --> 00:35:28,330
Kaj tiam mi nur looped tra dum temp ne egala nula,

463
00:35:28,330 --> 00:35:31,700
tiel dum estis ankoraŭ en la arbo, mi supozas.

464
00:35:31,700 --> 00:35:35,710
Kaj se la valoro egalas al la valoro kiu temp notas al,

465
00:35:35,710 --> 00:35:37,640
tiam ĝi redonas tiun valoron.

466
00:35:37,640 --> 00:35:40,210
Alie, ĝi kontrolas se estas cxe la dekstra flanko aŭ la maldekstra flanko.

467
00:35:40,210 --> 00:35:43,400
Se vi iam ricevi situacio kie mankas pli arbo,

468
00:35:43,400 --> 00:35:47,330
tiam li revenas - ĝi eliroj la ciklo kaj revenas falsaj.

469
00:35:47,330 --> 00:35:52,190
[Bowden] Okay. Do kiu ŝajnas bona.

470
00:35:52,190 --> 00:35:58,470
Iu havas komentoj pri io?

471
00:35:58,470 --> 00:36:02,400
Mi havas neniun praveco komentojn ĉe ĉiuj.

472
00:36:02,400 --> 00:36:11,020
La unu afero ni povas fari estas ĉi ulo.

473
00:36:11,020 --> 00:36:21,660
Ho, ĝi estas tuj iros iom longish.

474
00:36:21,660 --> 00:36:33,460
Mi havigos ke ĝis. Okay.

475
00:36:33,460 --> 00:36:37,150
>> Ĉiuj devus memori kiom triargumenta funkcias.

476
00:36:37,150 --> 00:36:38,610
Tie ili definitive estis kvizojn en la estinteco

477
00:36:38,610 --> 00:36:41,170
ke al vi funkcio kun triargumenta operatoro,

478
00:36:41,170 --> 00:36:45,750
kaj diru traduki ĉi tion, faru ion, kiu ne uzas triargumenta.

479
00:36:45,750 --> 00:36:49,140
Do ĉi tiu estas tre komuna kazo de kiam mi pensus uzi triargumenta,

480
00:36:49,140 --> 00:36:54,610
kie se iu kondiĉo establis variablo al iu,

481
00:36:54,610 --> 00:36:58,580
alie agordi tiu sama variablo por io alia.

482
00:36:58,580 --> 00:37:03,390
Tio estas iu kiu tre ofte povas esti konvertita enen ĉi tiaj aferoj

483
00:37:03,390 --> 00:37:14,420
kie establis ke variablo al tio - aŭ, bone, tio validas? Tiam ĉi, alie tion ĉi.

484
00:37:14,420 --> 00:37:18,550
[Studenta] La unua estas, se vera, ĉu ne?

485
00:37:18,550 --> 00:37:25,570
[Bowden] Yeah. La maniero Mi ĉiam legas estas, temp egalas valoron pli granda ol temp valoro,

486
00:37:25,570 --> 00:37:30,680
tiam ĉi, alie tion ĉi. Oni demandas demandon.

487
00:37:30,680 --> 00:37:35,200
Ĉu granda? Poste faru la unuan aferon. Else do la dua afero.

488
00:37:35,200 --> 00:37:41,670
Mi preskaŭ ĉiam - la dupunkto, mi nur - en mia kapo, mi legis kiel alia.

489
00:37:41,670 --> 00:37:47,180
>> Ĉu iu havas rekursia solvo?

490
00:37:47,180 --> 00:37:49,670
Okay. Ĉi tiu nin tuj - ĝi povus jam esti granda,

491
00:37:49,670 --> 00:37:53,990
sed ni tuj faros eĉ pli bona.

492
00:37:53,990 --> 00:37:58,720
Ĉi tiu estas preskaux la samo ĝustan ideon.

493
00:37:58,720 --> 00:38:03,060
Estas nur, nu, ĉu vi volas klarigi?

494
00:38:03,060 --> 00:38:08,340
[Studenta] Certe. Do ni certigante ke la arbo estas ne nula unua,

495
00:38:08,340 --> 00:38:13,380
ĉar se la arbo estas nula tiam tuj revenos malvera ĉar ni ne trovis ĝin.

496
00:38:13,380 --> 00:38:19,200
Kaj se estas ankoraŭ arbo, ni iru en - ni unue kontroli, ĉu la valoro estas la nuna nodo.

497
00:38:19,200 --> 00:38:23,740
Reveno vera se ĝi estas, kaj se ni ne recurse sur la maldekstra aŭ dekstra.

498
00:38:23,740 --> 00:38:25,970
Ĉu tio sonas taŭga? >> MM-hmm. (Akordo)

499
00:38:25,970 --> 00:38:33,880
Do rimarki ke ĉi tio estas preskaŭ - strukture tre simila al la ripeta solvo.

500
00:38:33,880 --> 00:38:38,200
Estas nur ke anstataŭ recursing, ni havis dum ciklo.

501
00:38:38,200 --> 00:38:40,840
Kaj la bazo ĉi tie kie arbo ne egala nula

502
00:38:40,840 --> 00:38:44,850
estis la kondiĉo sub kiu ni rompis el la dum ciklo.

503
00:38:44,850 --> 00:38:50,200
Ili estas tre similaj. Sed ni tuj por preni tiun unu paŝon.

504
00:38:50,200 --> 00:38:54,190
Nun, ni faros la samon ĉi tie.

505
00:38:54,190 --> 00:38:57,680
Rimarku ni reveni al la sama afero en ambaŭ el ĉi tiuj linioj,

506
00:38:57,680 --> 00:39:00,220
krom unu argumento estas malsama.

507
00:39:00,220 --> 00:39:07,950
Do ni tuj faros ke en triargumenta.

508
00:39:07,950 --> 00:39:13,790
Mi batis eblo ion, kaj tio faris simbolo. Okay.

509
00:39:13,790 --> 00:39:21,720
Do ni tuj revenos enhavas tion.

510
00:39:21,720 --> 00:39:28,030
Ĉi farigxas multnombraj linioj, nu, zoomed en ĝi estas.

511
00:39:28,030 --> 00:39:31,060
Kutime, kiel stila afero, mi ne pensas multaj homoj

512
00:39:31,060 --> 00:39:38,640
metu spacon post la sago, sed mi supozas, se vi estas kohera, estas fajna.

513
00:39:38,640 --> 00:39:44,320
Se valoro estas malpli ol arbo valoro, ni volas recurse sur arbo maldekstren,

514
00:39:44,320 --> 00:39:53,890
alie ni volas recurse sur arbo dekstre.

515
00:39:53,890 --> 00:39:58,610
Por ke estis paŝo unu el farante ĉi rigardo pli malgranda.

516
00:39:58,610 --> 00:40:02,660
Paŝo du de fari ĉi rigardo pli malgranda -

517
00:40:02,660 --> 00:40:09,150
ni povas apartigi tion al multnombraj linioj.

518
00:40:09,150 --> 00:40:16,500
Okay. Paŝo du de farante ĝi aspektos pli malgranda estas ĉi tie,

519
00:40:16,500 --> 00:40:25,860
tial reveno valoro egalas arbo valoron, nek enhavas ajn.

520
00:40:25,860 --> 00:40:28,340
>> Tio estas grava afero.

521
00:40:28,340 --> 00:40:30,860
Mi ne certas, ĉu li diris eksplicite en klaso,

522
00:40:30,860 --> 00:40:34,740
sed ĝi estas nomata mallonga cirkvito pritakso.

523
00:40:34,740 --> 00:40:41,060
La ideo cxi tie estas valoro == arbo valoron.

524
00:40:41,060 --> 00:40:49,960
Se tio estas vera, tiam ĉi tiu estas vera, kaj ni volas 'aŭ' kiu kun kio ajn super tie.

525
00:40:49,960 --> 00:40:52,520
Do eĉ sen pensi kio ajn ĉi tie,

526
00:40:52,520 --> 00:40:55,070
kio estas la tuta esprimo tuj revenos?

527
00:40:55,070 --> 00:40:59,430
[Studenta] Vera? >> Jes, ĉar veran de io,

528
00:40:59,430 --> 00:41:04,990
or'd - aŭ vera or'd kun nenio estas bezone vera.

529
00:41:04,990 --> 00:41:08,150
Tuj, kiam ni vidas reveno valoro = arbo valoron,

530
00:41:08,150 --> 00:41:10,140
ni ĵus tuj revenos vera.

531
00:41:10,140 --> 00:41:15,710
Eĉ tuj recurse plu enhavas laŭ la linio.

532
00:41:15,710 --> 00:41:20,980
Ni povas preni ĉi unu paŝon.

533
00:41:20,980 --> 00:41:29,490
Reiri arbo ne egala nula kaj ĉiuj tion ĉi.

534
00:41:29,490 --> 00:41:32,650
Ĝi faris ĝin unu-linia funkcio.

535
00:41:32,650 --> 00:41:36,790
Tiu estas ankaŭ ekzemplo de mallonga cirkvito pritakso.

536
00:41:36,790 --> 00:41:40,680
Sed nun ĝi estas la sama ideo -

537
00:41:40,680 --> 00:41:47,320
anstataŭ - do se arbo ne egala nula - aŭ, bone,

538
00:41:47,320 --> 00:41:49,580
se arbo faras egalaj nula, kiu estas la malbona kazo,

539
00:41:49,580 --> 00:41:54,790
se arbo egalas nula, tiam la unua kondiĉo tuj estos falsaj.

540
00:41:54,790 --> 00:42:00,550
Do falsa anded kun nenio tuj estos kio?

541
00:42:00,550 --> 00:42:04,640
[Studenta] Falsa. >> Jes. Tio estas la alia duono de mallonga cirkvito pritakso,

542
00:42:04,640 --> 00:42:10,710
kie se arbo ne egala nula, tiam ni ne tuj eĉ iri -

543
00:42:10,710 --> 00:42:14,930
aŭ se arbo faras egalaj nula, tiam ni ne faros valoro == arbo valoron.

544
00:42:14,930 --> 00:42:17,010
Ni nur tuj tuj revenos falsaj.

545
00:42:17,010 --> 00:42:20,970
Kio estas grava, ĉar se tio ne mallonga cirkvito taksi,

546
00:42:20,970 --> 00:42:25,860
tiam se arbo faras egalaj nula, tiu dua kondiĉo tuj seg kulpo,

547
00:42:25,860 --> 00:42:32,510
ĉar arbo-> valoro estas dereferencing nula.

548
00:42:32,510 --> 00:42:40,490
Do jen tiel. Povas fari ĉi - ŝanĝi iam finita.

549
00:42:40,490 --> 00:42:44,840
Ĉi tiu estas tre komuna afero, ne farante ĉi tiu linio kun tio,

550
00:42:44,840 --> 00:42:49,000
sed estas komuna aĵo en kondiĉoj, eble ne rajtas ĉi tie,

551
00:42:49,000 --> 00:42:59,380
sed se (arbo! = NULL, kaj arbo-> valoro == valoro), faru kion ajn.

552
00:42:59,380 --> 00:43:01,560
Ĉi tiu estas tre komuna kondiĉo, kie anstataŭ havi

553
00:43:01,560 --> 00:43:06,770
rompi tiun en du IFS, kie kiel, estas la arbo nula?

554
00:43:06,770 --> 00:43:11,780
Okay, ne nula, tial nun estas la arbo valoro egalas al valoro? Fari ĉi tion.

555
00:43:11,780 --> 00:43:17,300
Anstataŭe, ĉi tiu kondiĉo, ĉi tio neniam seg kulpo

556
00:43:17,300 --> 00:43:21,220
ĉar rompos, ĉu ĉi tio okazas al esti nula.

557
00:43:21,220 --> 00:43:24,000
Nu, mi supozas se via arbo estas tute nevalida pointer, ĝi povas ankoraŭ seg kulpo,

558
00:43:24,000 --> 00:43:26,620
sed ĝi ne povas seg kulpo se arbo estas nula.

559
00:43:26,620 --> 00:43:32,900
Se estis nula, tio rompus antaux vi iam dereferenced la puntero en la unua loko.

560
00:43:32,900 --> 00:43:35,000
[Studenta] Is this nomita pigra pritakso?

561
00:43:35,000 --> 00:43:40,770
>> [Bowden] Lazy pritakso estas aparta afero.

562
00:43:40,770 --> 00:43:49,880
Pigra pritakso estas pli kiel vi peti valoron,

563
00:43:49,880 --> 00:43:54,270
vi demandos al kalkuli valoron, speco de, sed vi ne bezonas ĝin tuj.

564
00:43:54,270 --> 00:43:59,040
Do ĝis vi vere bezonas ĝin, tio ne estas taksita.

565
00:43:59,040 --> 00:44:03,920
Tio ne estas ekzakte la sama afero, sed en la kodigo pset,

566
00:44:03,920 --> 00:44:06,520
diras, ke ni "pigre" skribi.

567
00:44:06,520 --> 00:44:08,670
La kialo ni faru tion estas ĉar ni vere buffering la skribo -

568
00:44:08,670 --> 00:44:11,820
ni ne volas skribi individuajn bitojn samtempe,

569
00:44:11,820 --> 00:44:15,450
aŭ individuaj bitokoj samtempe, ni anstataŭ volas eron de bajtoj.

570
00:44:15,450 --> 00:44:19,270
Tiam fojon ni havas eron de bajtoj, tiam ni skribi ĝin.

571
00:44:19,270 --> 00:44:22,640
Kvankam vi demandas ĝin por skribi - kaj fwrite kaj fread fari same tiaj aferoj.

572
00:44:22,640 --> 00:44:26,260
Ili buffer vian legas kaj skribas.

573
00:44:26,260 --> 00:44:31,610
Kvankam vi demandas ĝin skribi tuj, ĝi probable ne estos.

574
00:44:31,610 --> 00:44:34,540
Kaj vi ne povas esti certa, ke la vojo por esti skribita

575
00:44:34,540 --> 00:44:37,540
ĝis vi nomas hfclose aŭ kio ajn ĝi estas,

576
00:44:37,540 --> 00:44:39,620
kiuj tiam diras, bone, mi fermas mian dosieron,

577
00:44:39,620 --> 00:44:43,450
kiu signifu mi prefere skribu ĉion, kion mi ne skribis ankoraŭ.

578
00:44:43,450 --> 00:44:45,770
Ĝi ne bezonas skribi cxion ekster

579
00:44:45,770 --> 00:44:49,010
ĝis vi fermas la dosiero, kaj poste ĝi bezonas.

580
00:44:49,010 --> 00:44:56,220
Do tio estas nur kion pigra - ĝi atendas ĝis ĝi devas okazi.

581
00:44:56,220 --> 00:44:59,990
Ĉi - prenu 51 kaj vi iros en ĝin pli detale,

582
00:44:59,990 --> 00:45:05,470
ĉar Ocaml kaj ĉiu en 51, ĉiu estas rekursio.

583
00:45:05,470 --> 00:45:08,890
Ne estas ripeta solvojn, esence.

584
00:45:08,890 --> 00:45:11,550
Ĉiu estas rekursio kaj pigra pritakso

585
00:45:11,550 --> 00:45:14,790
tuj estos gravaj por multaj cirkonstancoj

586
00:45:14,790 --> 00:45:19,920
kie, se vi ne pigre taksi, kiu signifus -

587
00:45:19,920 --> 00:45:24,760
La ekzemplo estas riveretoj, kiuj estas malfinie longa.

588
00:45:24,760 --> 00:45:30,990
En teorio, vi povas pensi pri la naturaj nombroj kiel la kurento de 1-2-3-4-5-6-7,

589
00:45:30,990 --> 00:45:33,090
Do pigre taksita aĵoj estas fajna.

590
00:45:33,090 --> 00:45:37,210
Se mi diras Mi volas la deka numero, tiam mi povas taksi ĝis la deka cifero.

591
00:45:37,210 --> 00:45:40,300
Se mi volas la centa numero, tiam mi povas taksi ĝis la centa numero.

592
00:45:40,300 --> 00:45:46,290
Sen pigra pritakso, tiam tuj provas taksi ĉiuj nombroj tuj.

593
00:45:46,290 --> 00:45:50,000
Vi taksi malfinie multaj nombroj, kaj tio estas ĝuste ne eblas.

594
00:45:50,000 --> 00:45:52,080
Estas do multaj cirkonstancoj kie pigra pritakso

595
00:45:52,080 --> 00:45:57,840
estas nur esenca por atingi tion por labori.

596
00:45:57,840 --> 00:46:05,260
>> Ni nun volas skribi insert kie insert tuj estos

597
00:46:05,260 --> 00:46:08,430
simile ŝanĝanta en lia difino.

598
00:46:08,430 --> 00:46:10,470
Do nun estas bool insert (int valoro).

599
00:46:10,470 --> 00:46:23,850
Ni tuj ŝanĝu tion al bool insert (int valoro, nodo * arbo).

600
00:46:23,850 --> 00:46:29,120
Ni efektive tuj ŝanĝi tion denove en iom, ni vidos kial.

601
00:46:29,120 --> 00:46:32,210
Kaj estu la movi build_node, nur por la heck pri tio,

602
00:46:32,210 --> 00:46:36,730
supre enmeti do ni ne devas skribi funkcion prototipo.

603
00:46:36,730 --> 00:46:42,450
Kiu estas aludo, ke vi tuj estos uzante build_node en insert.

604
00:46:42,450 --> 00:46:49,590
Okay. Prenu unu minuto por tio.

605
00:46:49,590 --> 00:46:52,130
Mi kredas ke mi savis la revizio se vi volas tiri el tio,

606
00:46:52,130 --> 00:47:00,240
aŭ, almenaŭ, mi faris nun.

607
00:47:00,240 --> 00:47:04,190
Mi volis iomete ripozon por pensi pri la logiko de insert,

608
00:47:04,190 --> 00:47:08,750
se vi ne povas pensi pri ĝi.

609
00:47:08,750 --> 00:47:12,860
Esence, vi nur iam esti enmeto en folioj.

610
00:47:12,860 --> 00:47:18,640
Kiel, se mi enmetas 1, tiam mi nepre tuj estos enmeto 1 -

611
00:47:18,640 --> 00:47:21,820
Mi ŝanĝos al nigra - I'll esti enmeto 1 pli tie.

612
00:47:21,820 --> 00:47:28,070
Aŭ se mi enmetas 4, mi volas esti enmeto 4 pli tie.

613
00:47:28,070 --> 00:47:32,180
Do ne gravas kion vi faras, vi tuj estos enmeto en folio.

614
00:47:32,180 --> 00:47:36,130
Vi nur devas fari estas persisti malsupren de la arbo ĝis vi atingos la nodo

615
00:47:36,130 --> 00:47:40,890
kiuj devus esti la nodo patro, la nova nodo patro,

616
00:47:40,890 --> 00:47:44,560
kaj poste ŝanĝi lian maldekstran aŭ dekstren pointer, depende de ĉu

617
00:47:44,560 --> 00:47:47,060
ĝi estas pli granda ol aŭ malpli ol la aktuala nodo.

618
00:47:47,060 --> 00:47:51,180
Ŝanĝi tion puntero atentigi al via nova nodo.

619
00:47:51,180 --> 00:48:05,490
Do persisti malsupren de la arbo, fari la folio punkto al la nova nodo.

620
00:48:05,490 --> 00:48:09,810
Ankaŭ pensas ke kial malpermesas la tipo de situacio antaŭ,

621
00:48:09,810 --> 00:48:17,990
kie mi konstruis la duuma arbo kie estis ĝentila

622
00:48:17,990 --> 00:48:19,920
se vi nur rigardis unu nodo,

623
00:48:19,920 --> 00:48:24,830
sed 9 estis ĉe la maldekstra de 7 se vi ripetis cxiujn vojo.

624
00:48:24,830 --> 00:48:29,770
Por ke estas neebla en ĉi tiu scenejo, ĉar -

625
00:48:29,770 --> 00:48:32,530
kredas pri enmeto 9 aŭ io; ke je la unua nodo,

626
00:48:32,530 --> 00:48:35,350
Mi iros vidi 7 kaj mi simple tuj iros al dekstre.

627
00:48:35,350 --> 00:48:38,490
Do ne gravas, kion mi faru, se mi enmeto irante al folio,

628
00:48:38,490 --> 00:48:40,790
kaj folion per la taŭga algoritmo,

629
00:48:40,790 --> 00:48:43,130
ĝi tuj estos neebla por mi enŝovu 9 al la maldekstra el 7

630
00:48:43,130 --> 00:48:48,250
ĉar kiam mi batis 7 Mi tuj iros dekstren.

631
00:48:59,740 --> 00:49:02,070
Ĉu iu havas ion por starti kun?

632
00:49:02,070 --> 00:49:05,480
[Studenta] I do. >> Certe.

633
00:49:05,480 --> 00:49:09,200
[Studento, nekomprenebla]

634
00:49:09,200 --> 00:49:14,390
[Aliaj studento, nekomprenebla]

635
00:49:14,390 --> 00:49:18,330
[Bowden] Oni estimis. Okay. Volas klarigi?

636
00:49:18,330 --> 00:49:20,690
>> [Studenta] Ĉar ni scias, ke ni estis la enmeto

637
00:49:20,690 --> 00:49:24,060
novaj nodoj je la fino de la arbo,

638
00:49:24,060 --> 00:49:28,070
Mi looped tra la arbo iterativamente

639
00:49:28,070 --> 00:49:31,360
ĝis mi alvenis al nodo kiu notis al nula.

640
00:49:31,360 --> 00:49:34,220
Kaj poste mi decidis meti ĝin ĉu sur la dekstra flanko aŭ la maldekstra flanko

641
00:49:34,220 --> 00:49:37,420
uzante tiun rajton variablo; rakontis al mi kie meti ĝin.

642
00:49:37,420 --> 00:49:41,850
Kaj poste, esence, mi nur faris tiun lastan -

643
00:49:41,850 --> 00:49:47,520
ke temp nodo punkto al la nova vertico ke ĝi kreas,

644
00:49:47,520 --> 00:49:50,770
ĉu sur la maldekstra flanko aŭ ĉe la dekstra flanko, depende de tio, kion la valoro dekstra estis.

645
00:49:50,770 --> 00:49:56,530
Fine, mi starigis la novan nodon valoro al la valoro de lia provoj.

646
00:49:56,530 --> 00:49:59,550
[Bowden] Konsentite, tiel mi vidas unu afero ĉi tie.

647
00:49:59,550 --> 00:50:02,050
Ĉi tio estas kiel 95% de la vojo.

648
00:50:02,050 --> 00:50:07,550
La demando kiun mi vidas, nu, ne iu alia vidis afero?

649
00:50:07,550 --> 00:50:18,400
Kio estas la cirkonstanco sub kiuj ili rompas el la ciklo?

650
00:50:18,400 --> 00:50:22,100
[Studenta] Se temp estas nula? >> Jes. Do kiel vi rompi la buklo estas se temp estas nula.

651
00:50:22,100 --> 00:50:30,220
Sed kion mi faru ĉi tie?

652
00:50:30,220 --> 00:50:35,410
Mi dereference temp, kiu estas neeviteble nula.

653
00:50:35,410 --> 00:50:39,840
Do la alia afero vi bezonas fari, estas ne nur konservi trako ĝis temp estas nula,

654
00:50:39,840 --> 00:50:45,590
vi volas konservi trako de la patro en ĉiu momento.

655
00:50:45,590 --> 00:50:52,190
Ni ankaŭ volas nodo * patro, mi supozas ke ni povas subteni ke en nula en komenco.

656
00:50:52,190 --> 00:50:55,480
Tiu tuj havos stranga konduto por la radiko de la arbo,

657
00:50:55,480 --> 00:50:59,210
sed ni ricevos por tio.

658
00:50:59,210 --> 00:51:03,950
Se valoro estas pli granda ol kion ajn, tiam temp = temp pravas.

659
00:51:03,950 --> 00:51:07,910
Sed antaŭ ol ni faras tion, patro = temp.

660
00:51:07,910 --> 00:51:14,500
Aŭ gepatrojn ĉiam tuj egala temp? Ĉu tio estas la kazo?

661
00:51:14,500 --> 00:51:19,560
Se temp ne nula, tiam mi iros por movi malsupren, negrave kio,

662
00:51:19,560 --> 00:51:24,030
al nodo por kiu temp estas la patro.

663
00:51:24,030 --> 00:51:27,500
Do patro tuj estos temp, kaj tiam mi movi temp sube.

664
00:51:27,500 --> 00:51:32,410
Nun temp estas nula, sed patro poentojn al la patro de la aĵo kiu estas nula.

665
00:51:32,410 --> 00:51:39,110
Do ĉi tie, mi ne volas meti dekstra egalas 1.

666
00:51:39,110 --> 00:51:41,300
Do mi kopiis al la dekstra, do se dekstra = 1,

667
00:51:41,300 --> 00:51:45,130
kaj mi supozas ke vi ankaŭ volas fari -

668
00:51:45,130 --> 00:51:48,530
se vi movas al la maldekstra, vi volas agordi dekstra egala al 0.

669
00:51:48,530 --> 00:51:55,950
Alie se vi iam kopii al dekstre.

670
00:51:55,950 --> 00:51:58,590
So right = 0. Se dekstra = 1,

671
00:51:58,590 --> 00:52:04,260
nun ni deziras fari la patro dekstra puntero newnode,

672
00:52:04,260 --> 00:52:08,520
alie ni volas fari la patro maldekstra puntero newnode.

673
00:52:08,520 --> 00:52:16,850
Demandojn sur tio?

674
00:52:16,850 --> 00:52:24,880
Okay. Do ĉi tiu estas la vojo ni - nu, efektive, anstataŭ fari tion,

675
00:52:24,880 --> 00:52:29,630
ni duono atendis vin uzi build_node.

676
00:52:29,630 --> 00:52:40,450
Kaj tiam se newnode egalas nula, revenu falsaj.

677
00:52:40,450 --> 00:52:44,170
Tio estas tio. Nun, ĉi tiu estas kion ni atendas vin por fari.

678
00:52:44,170 --> 00:52:47,690
>> Ĉi tio estas kion la bastonon solvoj fari.

679
00:52:47,690 --> 00:52:52,360
Mi malkonsentas kun tiu, la "rajto" vojo de tuj pri tio

680
00:52:52,360 --> 00:52:57,820
sed ĉi tiu estas perfekte fajna kaj ĝi funkcios.

681
00:52:57,820 --> 00:53:02,840
Unu afero, ke estas iom stranga nun estas

682
00:53:02,840 --> 00:53:08,310
se la arbo dividu kiel nula, oni pasas en nula arbo.

683
00:53:08,310 --> 00:53:12,650
Mi supozas ke dependas de kiel vi difinas la konduton de pasi en nula arbo.

684
00:53:12,650 --> 00:53:15,490
Mi pensus ke se vi pasas en nula arbo,

685
00:53:15,490 --> 00:53:17,520
tiam la enmeto de la valoro en nula arbo

686
00:53:17,520 --> 00:53:23,030
devus simple resendas arbo kie la sola valoro estas, ke simpla nodo.

687
00:53:23,030 --> 00:53:25,830
Ĉu homoj konsentas kun tiu? Vi povus, se vi volas,

688
00:53:25,830 --> 00:53:28,050
se vi pasas en nula arbo

689
00:53:28,050 --> 00:53:31,320
kaj vi volas enmeti valoron en ĝin, revenu falsaj.

690
00:53:31,320 --> 00:53:33,830
Ĝi dependas de vi por difini tion.

691
00:53:33,830 --> 00:53:38,320
Por fari la unuan aferon mi diris kaj tiam -

692
00:53:38,320 --> 00:53:40,720
bone, vi havos problemojn fari tion, ĉar

693
00:53:40,720 --> 00:53:44,090
estus pli facile se ni havis suman sagon al la afero,

694
00:53:44,090 --> 00:53:48,570
sed ni ne, do se arbo estas nula, tie estas nenio ni povas fari pri tio.

695
00:53:48,570 --> 00:53:50,960
Ni povas nur redoni malvera.

696
00:53:50,960 --> 00:53:52,840
Do mi tuj ŝanĝos insert.

697
00:53:52,840 --> 00:53:56,540
Ni teknike povus simple ŝanĝi ĉi tie ĉi,

698
00:53:56,540 --> 00:53:58,400
kiel ĝi estas ripetanta super aĵoj,

699
00:53:58,400 --> 00:54:04,530
sed mi tuj ŝanĝos insert preni nodo ** arbo.

700
00:54:04,530 --> 00:54:07,510
Duobla punteros.

701
00:54:07,510 --> 00:54:09,710
Kion tio signifas?

702
00:54:09,710 --> 00:54:12,330
Anstataŭ trakti punteros al nodoj,

703
00:54:12,330 --> 00:54:16,690
la afero mi tuj iros manipulanta estas ĉi puntero.

704
00:54:16,690 --> 00:54:18,790
Mi tuj iros manipulanta ĉi puntero.

705
00:54:18,790 --> 00:54:21,770
Mi tuj iros manipulanta punteros rekte.

706
00:54:21,770 --> 00:54:25,760
Tiu makes sense ekde, pensi malsupren -

707
00:54:25,760 --> 00:54:33,340
nu, nun ĉi punktoj al nula.

708
00:54:33,340 --> 00:54:38,130
Kion mi volas fari estas manipuli ĉi puntero atentigi ke ne nula.

709
00:54:38,130 --> 00:54:40,970
Mi volas atentigi al mia nova nodo.

710
00:54:40,970 --> 00:54:44,870
Se mi ĝuste konservi trako de punteros al mia punteros,

711
00:54:44,870 --> 00:54:47,840
tiam mi ne bezonas konservi trako de patro puntero.

712
00:54:47,840 --> 00:54:52,640
Mi povas nur kontroli kiu faras por vidi se la puntero notas al nula,

713
00:54:52,640 --> 00:54:54,580
kaj se la puntero notas al nula,

714
00:54:54,580 --> 00:54:57,370
ŝanĝi ĝin al punkto al la nodo mi volas.

715
00:54:57,370 --> 00:55:00,070
Kaj mi povas ŝanĝi ĝin ĉar mi havas sagon al la puntero.

716
00:55:00,070 --> 00:55:02,040
Ni vidas ĉi nun.

717
00:55:02,040 --> 00:55:05,470
Vi povas vere fari ĝin rekursie bela facile.

718
00:55:05,470 --> 00:55:08,080
Ĉu ni volas fari tion?

719
00:55:08,080 --> 00:55:10,980
Jes, ni faros.

720
00:55:10,980 --> 00:55:16,790
>> Ni vidas rekursie.

721
00:55:16,790 --> 00:55:24,070
Unue, kio nia bazo kazo tuj estos?

722
00:55:24,070 --> 00:55:29,140
Preskaŭ ĉiam nia bazo kazo, sed efektive, tiu estas speco de malfacila.

723
00:55:29,140 --> 00:55:34,370
Unuaj aferoj unue, se (arbo == NULL)

724
00:55:34,370 --> 00:55:37,550
Mi supozas ni ĵus tuj revenos falsaj.

725
00:55:37,550 --> 00:55:40,460
Tiu estas malsama de via arbo esti nula.

726
00:55:40,460 --> 00:55:44,510
Ĉi tiu estas la puntero al via radika puntero esti nula

727
00:55:44,510 --> 00:55:48,360
kio signifas, ke via radika puntero ne ekzistas.

728
00:55:48,360 --> 00:55:52,390
Do ĉi tie, se mi faras

729
00:55:52,390 --> 00:55:55,760
nodo * - ni simple reuzas tion.

730
00:55:55,760 --> 00:55:58,960
Nodo * radiko = NULL,

731
00:55:58,960 --> 00:56:00,730
kaj tiam mi iros nomi insert farante ion kiel,

732
00:56:00,730 --> 00:56:04,540
enŝovu 4 en & radiko.

733
00:56:04,540 --> 00:56:06,560
Do & radiko, se radiko estas nodo *

734
00:56:06,560 --> 00:56:11,170
tiam & radiko tuj estos nodo **.

735
00:56:11,170 --> 00:56:15,120
Ĉi tio estas valida. En ĉi tiu kazo, arbo, tien,

736
00:56:15,120 --> 00:56:20,120
arbo estas ne nulaj - aŭ insert.

737
00:56:20,120 --> 00:56:24,630
Jen. Arbo estas ne nulaj; * arbo estas nula, kiu estas fajna

738
00:56:24,630 --> 00:56:26,680
ĉar se * arbo estas nula, tiam mi povas manipuli ĝin

739
00:56:26,680 --> 00:56:29,210
nun notas, kion mi volas atentigi al.

740
00:56:29,210 --> 00:56:34,750
Sed se arbo estas nula, kiu signifu mi nur venis ĉi tien kaj diris nula.

741
00:56:34,750 --> 00:56:42,710
Tio ne havas sencon. Mi ne povas fari ion kun tiu.

742
00:56:42,710 --> 00:56:45,540
Se arbo estas nula, revenu falsaj.

743
00:56:45,540 --> 00:56:48,220
Do mi esence jam diris kion niaj reala bazo kazo estas.

744
00:56:48,220 --> 00:56:50,580
Kaj kio estas tiu tuj estos?

745
00:56:50,580 --> 00:56:55,030
[Studento, nekomprenebla]

746
00:56:55,030 --> 00:57:00,000
[Bowden] Jes. Do, se (* arbo == NULL).

747
00:57:00,000 --> 00:57:04,520
Tiu rilatas al la kazo ĉi tien

748
00:57:04,520 --> 00:57:09,640
kie se mia ruĝa puntero estas la puntero Mi centris en,

749
00:57:09,640 --> 00:57:12,960
tiel kiel mi centris en ĉi pointer, nun mi centris en ĉi puntero.

750
00:57:12,960 --> 00:57:15,150
Nun mi centris en ĉi puntero.

751
00:57:15,150 --> 00:57:18,160
Do, se miaj ruĝaj pointer, kiu estas mia nodo **,

752
00:57:18,160 --> 00:57:22,880
estas iam - se *, mia ruĝa pointer, estas iam nula,

753
00:57:22,880 --> 00:57:28,470
tio signifas, ke mi estas la kazo kie mi enfokusigante puntero ke punktoj -

754
00:57:28,470 --> 00:57:32,530
ĉi tiu estas puntero kiu apartenas al folio.

755
00:57:32,530 --> 00:57:41,090
Mi volas ŝanĝi ĉi puntero atentigi al mia nova nodo.

756
00:57:41,090 --> 00:57:45,230
Revenu ĉi tien.

757
00:57:45,230 --> 00:57:56,490
Mia newnode estos nur esti nodo * n = build_node (valoro)

758
00:57:56,490 --> 00:58:07,300
tiam n, se n = NULL, revenu falsaj.

759
00:58:07,300 --> 00:58:12,600
Alie ni volas ŝanĝi kion la puntero nuntempe montrante

760
00:58:12,600 --> 00:58:17,830
nun notas al nia nove konstruita nodo.

761
00:58:17,830 --> 00:58:20,280
Ni povas vere fari tion tie ĉi.

762
00:58:20,280 --> 00:58:30,660
Anstataŭ diri n, ni diru * arbo = se * arbo.

763
00:58:30,660 --> 00:58:35,450
Cxiu komprenas tion? Ke per kontraktanta kun indikoj al punteros,

764
00:58:35,450 --> 00:58:40,750
ni povas ŝanĝi nula punteros atentigi al tio ni volas ilin atentigi al.

765
00:58:40,750 --> 00:58:42,820
Tio estas nia bazo kazo.

766
00:58:42,820 --> 00:58:45,740
>> Nun nia rekursieca, aŭ nia rekursio,

767
00:58:45,740 --> 00:58:51,430
tuj estos tre simila al ĉiuj aliaj recursions ni estis farante.

768
00:58:51,430 --> 00:58:55,830
Ni tuj volas enmeti valoron,

769
00:58:55,830 --> 00:58:59,040
kaj nun mi tuj uzos triargumenta denove, sed kio estas nia kondiĉo tuj estos?

770
00:58:59,040 --> 00:59:05,180
Kio estas tio ni serĉas por decidi ĉu ni volas iri maldekstra aŭ dekstra?

771
00:59:05,180 --> 00:59:07,760
Ni faru tion en apartaj paŝoj.

772
00:59:07,760 --> 00:59:18,850
If (valoro <) kio?

773
00:59:18,850 --> 00:59:23,200
[Studenta] La arbo valoron?

774
00:59:23,200 --> 00:59:27,490
[Bowden] Do memoru, ke mi estas aktuale -

775
00:59:27,490 --> 00:59:31,260
[Studentoj, nekomprenebla]

776
00:59:31,260 --> 00:59:34,140
[Bowden] Yeah, do ĉi tie, diru ke tiu verda sago

777
00:59:34,140 --> 00:59:39,050
estas ekzemplo de tio, kion arbo aktuale estas, estas puntero al ĉi puntero.

778
00:59:39,050 --> 00:59:46,610
Do tio signifas Mi estas puntero al puntero al 3.

779
00:59:46,610 --> 00:59:48,800
La dereference dufoje sonis bona.

780
00:59:48,800 --> 00:59:51,010
Kion mi - kiel mi faru tion?

781
00:59:51,010 --> 00:59:53,210
[Studenta] Dereference fojon, kaj tiam fari sago kiun vojon?

782
00:59:53,210 --> 00:59:58,420
[Bowden] So (* arbo) estas la dereference fojon, -> valoro

783
00:59:58,420 --> 01:00:05,960
tuj donu al mi la valoron de la nodo ke mi nerekte montrante.

784
01:00:05,960 --> 01:00:11,980
Do mi povas ankaŭ skribi ĝin ** tree.value se vi preferas tion.

785
01:00:11,980 --> 01:00:18,490
Ĉu funkcias.

786
01:00:18,490 --> 01:00:26,190
Se tio estas la kazo, tiam mi volas nomi enmeti per valoro.

787
01:00:26,190 --> 01:00:32,590
Kaj kio estas mia ĝisdatigita nodo ** tuj estos?

788
01:00:32,590 --> 01:00:39,440
Mi volas iri al la maldekstra, do ** tree.left tuj estos mia maldekstra.

789
01:00:39,440 --> 01:00:41,900
Kaj mi volas ke la referenco al tiu afero

790
01:00:41,900 --> 01:00:44,930
tiel ke se la maldekstra finas esti la nula pointer,

791
01:00:44,930 --> 01:00:48,360
Mi povas modifi ĝin rekte al mia nova nodo.

792
01:00:48,360 --> 01:00:51,460
>> Kaj la alia kazo povas esti tre similaj.

793
01:00:51,460 --> 01:00:55,600
Ni efektive faras ke mia triargumenta nun.

794
01:00:55,600 --> 01:01:04,480
Enmetu valoron se valoro <(** arbo). Valoro.

795
01:01:04,480 --> 01:01:11,040
Tiam ni volas ĝisdatigi nian ** al la maldekstra,

796
01:01:11,040 --> 01:01:17,030
alie ni volas ĝisdatigi nian ** dekstre.

797
01:01:17,030 --> 01:01:22,540
[Studenta] Ĉu tio akiri la sagon al la puntero?

798
01:01:22,540 --> 01:01:30,940
[Bowden] Memoru ke - ** tree.right estas nodo stelo.

799
01:01:30,940 --> 01:01:35,040
[Studento, nekomprenebla] >> Jes.

800
01:01:35,040 --> 01:01:41,140
** Tree.right estas kiel ĉi tiu puntero aŭ iu.

801
01:01:41,140 --> 01:01:45,140
Do per prenante puntero al tiu, kiu donas al mi kion mi volas

802
01:01:45,140 --> 01:01:50,090
de la puntero al tiu ulo.

803
01:01:50,090 --> 01:01:54,260
[Studenta] Could ni transiru denove kial oni uzas la du punteros?

804
01:01:54,260 --> 01:01:58,220
[Bowden] Yeah. Do - ne, vi povas, kaj ke solvo antaux

805
01:01:58,220 --> 01:02:04,540
Estis maniero fari ĝin sen fari du punteros.

806
01:02:04,540 --> 01:02:08,740
Vi bezonas por povi kompreni uzante du punteros,

807
01:02:08,740 --> 01:02:11,660
kaj ĉi tiu estas pli pura solvo.

808
01:02:11,660 --> 01:02:16,090
Ankaŭ, rimarki ke, kio okazas se mia arbo -

809
01:02:16,090 --> 01:02:24,480
kio okazas se mia radikon estis nula? Kio okazas se mi faras ĉi kazo ĉi tie?

810
01:02:24,480 --> 01:02:30,540
Do nodo * radiko = NULL, enŝovu 4 en & radiko.

811
01:02:30,540 --> 01:02:35,110
Kio estas radiko tuj estos post tio?

812
01:02:35,110 --> 01:02:37,470
[Studento, nekomprenebla] >> Jes.

813
01:02:37,470 --> 01:02:41,710
Radiko valoro tuj estos 4.

814
01:02:41,710 --> 01:02:45,510
Radiko maldekstra tuj estos nula, radiko dekstra tuj estos nula.

815
01:02:45,510 --> 01:02:49,490
En la kazo kie ni ne pasis radiko de adreson,

816
01:02:49,490 --> 01:02:52,490
ni ne povis modifi radikon.

817
01:02:52,490 --> 01:02:56,020
En la kazo kie la arbo - kie radiko estis nula,

818
01:02:56,020 --> 01:02:58,410
ni simple devis reveni falsaj. Nenio ni povus fari.

819
01:02:58,410 --> 01:03:01,520
Ni ne povas insertar nodo en malplenan arbo.

820
01:03:01,520 --> 01:03:06,810
Sed nun ni povas; ni simple malplena arbo en unu-nodo arbo.

821
01:03:06,810 --> 01:03:13,400
Kiu estas kutime la atendita formo kiu ĝi estas supozeble funkcias.

822
01:03:13,400 --> 01:03:21,610
>> Plue, tiu estas signife pli mallonga ol

823
01:03:21,610 --> 01:03:26,240
Ankaŭ konservanta trako de la patro, kaj tiel vi persisti malsupren la tuta vojo.

824
01:03:26,240 --> 01:03:30,140
Nun mi havas mian patro, kaj mi simple havas mian patro dekstra puntero al la kiom.

825
01:03:30,140 --> 01:03:35,640
Anstataŭe, se ni tion faris ripete, ĝi estus la sama ideo kun dum ciklo.

826
01:03:35,640 --> 01:03:38,100
Sed anstataŭ devi trakti kun mia patro pointer,

827
01:03:38,100 --> 01:03:40,600
anstataŭ mia nuna puntero estus la afero

828
01:03:40,600 --> 01:03:43,790
ke mi rekte modifi atentigi al mia nova nodo.

829
01:03:43,790 --> 01:03:46,090
Mi ne devas trakti ĉu ĝi estas montrante al la maldekstra.

830
01:03:46,090 --> 01:03:48,810
Mi ne devas trakti ĉu ĝi estas montranta dekstren.

831
01:03:48,810 --> 01:04:00,860
Estas nur ajn ĉi puntero estas, mi iros, por restarigi gxin rekte al mia nova nodo.

832
01:04:00,860 --> 01:04:05,740
Cxiu komprenas kiel ĝi funkcias?

833
01:04:05,740 --> 01:04:09,460
Se ne kial ni volas fari ĝin tiel,

834
01:04:09,460 --> 01:04:14,920
sed almenaŭ tiu ĉi verkoj kiel solvo?

835
01:04:14,920 --> 01:04:17,110
[Studenta] Kie ni revenos vera?

836
01:04:17,110 --> 01:04:21,550
[Bowden] Tio probable ĉi tie.

837
01:04:21,550 --> 01:04:26,690
Se ni ĝuste enmeti ĝin, revenas vera.

838
01:04:26,690 --> 01:04:32,010
Else, suben jen ni tuj volas reveni ajn insert revenas.

839
01:04:32,010 --> 01:04:35,950
>> Kaj kio estas speciala pri tiu rekursia funkcio?

840
01:04:35,950 --> 01:04:43,010
Estas vosto rekursie, do tiel longe kiel ni kompilos kun iuj optimumigo,

841
01:04:43,010 --> 01:04:48,060
ĝin rekonos, ke kaj vi neniam ricevas pilo superflui de ĉi tio,

842
01:04:48,060 --> 01:04:53,230
eĉ se nia arbo havas altecon de 10.000 aŭ 10 milionoj.

843
01:04:53,230 --> 01:04:55,630
[Studento, nekomprenebla]

844
01:04:55,630 --> 01:05:00,310
[Bowden] Mi opinias, ke ghi en Dash - aŭ kio optimumigo nivelo

845
01:05:00,310 --> 01:05:03,820
estas necesa por voston rekursio esti rekonita.

846
01:05:03,820 --> 01:05:09,350
Mi kredas ke rekonas - GCC kaj Clang

847
01:05:09,350 --> 01:05:12,610
ankaŭ havas malsamajn signifojn por ilia optimumigo niveloj.

848
01:05:12,610 --> 01:05:17,870
Mi volas diri ke estas DashO 2, por certigi ke ĝi rekonos vosto rekursio.

849
01:05:17,870 --> 01:05:27,880
Sed ni - vi povus konstrui kiel Fibonocci ekzemplo aŭ iu.

850
01:05:27,880 --> 01:05:30,030
Ne facile testi kun ĉi tio, ĉar ĝi estas malfacile konstrui

851
01:05:30,030 --> 01:05:32,600
duuma arbo kiu tiom granda.

852
01:05:32,600 --> 01:05:37,140
Sed jes, mi kredas ke estas DashO 2, kiu

853
01:05:37,140 --> 01:05:40,580
se vi kompili kun DashO 2, ĝi serĉos vosto rekursio

854
01:05:40,580 --> 01:05:54,030
kaj optimizar ke eksteren.

855
01:05:54,030 --> 01:05:58,190
Ni reiru al - enigi estas laŭvorte la lasta afero kiun ĝi bezonas.

856
01:05:58,190 --> 01:06:04,900
Ni reiru al la insert tien

857
01:06:04,900 --> 01:06:07,840
kie ni tuj faros la saman ideon.

858
01:06:07,840 --> 01:06:14,340
Ĝi devos ankoraŭ havas la difekton de ne povi tute manipuli

859
01:06:14,340 --> 01:06:17,940
kiam la radiko mem estas nula, aŭ la pasinteco eniro estas nula,

860
01:06:17,940 --> 01:06:20,060
sed anstataŭ kontraktanta kun patro pointer,

861
01:06:20,060 --> 01:06:27,430
ni apliku la saman logikon de gardi punteros al punteros.

862
01:06:27,430 --> 01:06:35,580
Se tie ni plenumas nian nodo ** nuna,

863
01:06:35,580 --> 01:06:37,860
kaj ni ne bezonas konservi trako de rajto plu,

864
01:06:37,860 --> 01:06:47,190
sed nodo ** nuna = & arbo.

865
01:06:47,190 --> 01:06:54,800
Kaj nun nia dum buklo tuj estos dum * nuna ne egala nula.

866
01:06:54,800 --> 01:07:00,270
Ne necesas konservi trako de gepatroj plu.

867
01:07:00,270 --> 01:07:04,180
Ne necesas konservi trako de maldekstra kaj dekstra.

868
01:07:04,180 --> 01:07:10,190
Kaj mi nomas ĝin temp, ĉar ni jam uzas temp.

869
01:07:10,190 --> 01:07:17,200
Okay. Do, se (valoro> * temp),

870
01:07:17,200 --> 01:07:24,010
tiam & (* temp) -> dekstre

871
01:07:24,010 --> 01:07:29,250
alie temp = & (* temp) -> maldekstra.

872
01:07:29,250 --> 01:07:32,730
Kaj nun, je ĉi tiu punkto, post ĉi tiu dum ciklo,

873
01:07:32,730 --> 01:07:36,380
Mi nur faras ĉi tion ĉar eble pli facilas pensi iterativamente ol rekursie,

874
01:07:36,380 --> 01:07:39,010
sed post ĉi dum ciklo,

875
01:07:39,010 --> 01:07:43,820
* Temp estas la puntero ni volas ŝanĝi.

876
01:07:43,820 --> 01:07:48,960
>> Antaŭ ol ni havis patro, kaj ni volis ŝanĝi ĉu patro maldekstra aŭ dekstra patro,

877
01:07:48,960 --> 01:07:51,310
sed se ni volas ŝanĝi patro pravas,

878
01:07:51,310 --> 01:07:54,550
tiam * temp estas patro estas prava, kaj ni povas ŝanĝi ĝin rekte.

879
01:07:54,550 --> 01:08:05,860
Do cxi tie, ni povas fari * temp = newnode, kaj tio estas ĝi.

880
01:08:05,860 --> 01:08:09,540
Do rimarki, ĉiuj ni faris en ĉi estis forprenu linioj de kodo.

881
01:08:09,540 --> 01:08:14,770
Por konservi trako de la patro en cxio, kio estas plia peno.

882
01:08:14,770 --> 01:08:18,689
Jen, se ni nur konservi trako de la sagon al la puntero,

883
01:08:18,689 --> 01:08:22,990
kaj eĉ se ni volis forigi ĉiujn ĉi tiujn frizita krampoj nun,

884
01:08:22,990 --> 01:08:27,170
fari ĝin rigardi pli mallonga.

885
01:08:27,170 --> 01:08:32,529
Tiu nun estas la ĝusta sama solvo,

886
01:08:32,529 --> 01:08:38,210
sed malpli linioj de kodo.

887
01:08:38,210 --> 01:08:41,229
Kiam vi komencos rekonante tion kiel validan solvo,

888
01:08:41,229 --> 01:08:43,529
ĝi estas ankaŭ pli facile rezoni pri pli ol kiel, bone,

889
01:08:43,529 --> 01:08:45,779
kial mi havas tiun flagon ĉe int dekstra?

890
01:08:45,779 --> 01:08:49,290
Kion tio signifas? Ho, ĝi estas kia

891
01:08:49,290 --> 01:08:51,370
ĉiufoje mi iros dekstren, mi bezonas por meti ĝin,

892
01:08:51,370 --> 01:08:53,819
alie, se mi iros lasis Mi bezonas meti ĝin al nulo.

893
01:08:53,819 --> 01:09:04,060
Ĉi tie, mi ne havas rezoni pri tio, temas nur pli facile pripensi.

894
01:09:04,060 --> 01:09:06,710
Demandoj?

895
01:09:06,710 --> 01:09:16,290
[Studento, nekomprenebla] >> Jes.

896
01:09:16,290 --> 01:09:23,359
Konsentite, tial en la lasta iom -

897
01:09:23,359 --> 01:09:28,080
Mi supozas oni rapida kaj facila funkcio ni povas fari estas,

898
01:09:28,080 --> 01:09:34,910
let's - kune, mi supozas, provu kaj skribu enhavas funkcio

899
01:09:34,910 --> 01:09:38,899
kiu ne zorgas ĉu ĝi estas duargumenta serĉo arbo.

900
01:09:38,899 --> 01:09:43,770
Tiu enhavas funkcion devus reveni vera

901
01:09:43,770 --> 01:09:58,330
se ie ajn en ĉi tiu ĝenerala duuma arbo estas la valoro, ni serĉas.

902
01:09:58,330 --> 01:10:02,520
Do ni unue faru ĝin rekursie kaj poste ni faros ĝin ripete.

903
01:10:02,520 --> 01:10:07,300
Ni povas vere nur tion kune, ĉar ĉi tiu tuj estos vere mallonga.

904
01:10:07,300 --> 01:10:11,510
>> Kio estas mia bazo kazo tuj estos?

905
01:10:11,510 --> 01:10:13,890
[Studento, nekomprenebla]

906
01:10:13,890 --> 01:10:18,230
[Bowden] Do, se (arbo == NULL), tiam kio?

907
01:10:18,230 --> 01:10:22,740
[Studenta] Reveno falsaj.

908
01:10:22,740 --> 01:10:26,160
[Bowden] Else, nu, mi ne bezonas la alian.

909
01:10:26,160 --> 01:10:30,250
Se estis mia alia bazo kazo.

910
01:10:30,250 --> 01:10:32,450
[Studenta] Tree valoro? >> Jes.

911
01:10:32,450 --> 01:10:36,430
Do, se (arbo-> valoro == valoro.

912
01:10:36,430 --> 01:10:39,920
Rimarku ni reen al nodo *, ne nodo ** j?

913
01:10:39,920 --> 01:10:42,990
Enhavas neniam devas uzi nodo **,

914
01:10:42,990 --> 01:10:45,480
ĉar ni ne modifas punteros.

915
01:10:45,480 --> 01:10:50,540
Ni nur trairante ilin.

916
01:10:50,540 --> 01:10:53,830
Se tio okazas, tiam ni volas reveni vera.

917
01:10:53,830 --> 01:10:58,270
Alie ni volas trairi la infanoj.

918
01:10:58,270 --> 01:11:02,620
Do ni ne povas rezoni pri tio, ĉu ĉio al la maldekstra estas malpli

919
01:11:02,620 --> 01:11:05,390
kaj ĉiu al dekstre estas granda.

920
01:11:05,390 --> 01:11:09,590
Do kio estas nia kondiĉo tuj estos tie - aŭ, kion ni tuj fari?

921
01:11:09,590 --> 01:11:11,840
[Studento, nekomprenebla] >> Jes.

922
01:11:11,840 --> 01:11:17,400
Reiri enhavas (valoro, arbo-> maldekstre)

923
01:11:17,400 --> 01:11:26,860
aŭ enhavas (valoro, arbo-> dekstre). Kaj tio estas ĝi.

924
01:11:26,860 --> 01:11:29,080
Kaj rimarki ekzistas iu mallonga cirkvito pritakso,

925
01:11:29,080 --> 01:11:32,520
kie se ni hazarde trovis la valoron en la maldekstra arbo,

926
01:11:32,520 --> 01:11:36,820
ni neniam devas rigardi la dekstra arbo.

927
01:11:36,820 --> 01:11:40,430
Tio estas la tuta funkcio.

928
01:11:40,430 --> 01:11:43,690
Nun ni faru ĝin ripete,

929
01:11:43,690 --> 01:11:48,060
kiu iras al esti malpli agrabla.

930
01:11:48,060 --> 01:11:54,750
Ni prenos la kutima komenco de nodo * nuna = arbo.

931
01:11:54,750 --> 01:12:03,250
Dum (nuna! = NULL).

932
01:12:03,250 --> 01:12:08,600
Rapide tuj vidas problemon.

933
01:12:08,600 --> 01:12:12,250
Se nuna - ĉi tie, se ni iam rompos el tio ĉi

934
01:12:12,250 --> 01:12:16,020
tiam ni ne plu havas aferojn por rigardi, do reveni falsaj.

935
01:12:16,020 --> 01:12:24,810
If (nuna-> valoro == valoro), revenu vera.

936
01:12:24,810 --> 01:12:32,910
Do nun ni estas en loko -

937
01:12:32,910 --> 01:12:36,250
ni ne scias, ĉu ni volas iri maldekstren aŭ dekstren.

938
01:12:36,250 --> 01:12:44,590
Do arbitre, ni nur iri lasis.

939
01:12:44,590 --> 01:12:47,910
Mi evidente kolizios afero kie mi tute forlasis cxion -

940
01:12:47,910 --> 01:12:50,760
Mi nur iam kontroli la maldekstra flanko de arbo.

941
01:12:50,760 --> 01:12:56,050
Mi neniam kontroli ion kiu estas dekstra filo de io.

942
01:12:56,050 --> 01:13:00,910
Kiel mi ripari tion?

943
01:13:00,910 --> 01:13:05,260
[Studenta] Oni devas konservi trako de la maldekstra kaj dekstra en pilo.

944
01:13:05,260 --> 01:13:13,710
[Bowden] Yeah. Do ni faru ĝin

945
01:13:13,710 --> 01:13:32,360
struct listo, nodo * n, kaj tiam nodo ** poste?

946
01:13:32,360 --> 01:13:40,240
Mi kredas, ke funkcias bone.

947
01:13:40,240 --> 01:13:45,940
Ni volas iri super la maldekstra, aŭ let's - ĝis ĉi tie.

948
01:13:45,940 --> 01:13:54,350
Struct listo listo =, ĝi devos komenci

949
01:13:54,350 --> 01:13:58,170
tra ĉi struct listo.

950
01:13:58,170 --> 01:14:04,040
* Listo = NULL. Por ke tuj estos nia ligillisto

951
01:14:04,040 --> 01:14:08,430
de subárboles ke ni saltis super.

952
01:14:08,430 --> 01:14:13,800
Ni iras al Traverse forlasis nun,

953
01:14:13,800 --> 01:14:17,870
sed ĉar ni neeviteble bezonas reveni al la dekstra,

954
01:14:17,870 --> 01:14:26,140
Ni tuj observas la dekstra flanko interne de nia struct listo.

955
01:14:26,140 --> 01:14:32,620
Tiam ni devos new_list aŭ struct,

956
01:14:32,620 --> 01:14:41,080
struct listo *, new_list = malloc (sizeof (listo)).

957
01:14:41,080 --> 01:14:44,920
Mi tuj ignori eraro-kontroladon tion, sed vi devus kontroli por vidi se la nula.

958
01:14:44,920 --> 01:14:50,540
New_list la nodo ĝi tuj indikas -

959
01:14:50,540 --> 01:14:56,890
ho, jen kial mi volis ĝin ĉi tie. Ĝi okazas al punkto al dua struct listo.

960
01:14:56,890 --> 01:15:02,380
Tio estas, kiom ligitaj lertaj laboro.

961
01:15:02,380 --> 01:15:04,810
Ĉi tiu estas la sama kiel int ligitaj listo

962
01:15:04,810 --> 01:15:06,960
krom ni nur anstataŭante int kun nodo *.

963
01:15:06,960 --> 01:15:11,040
Estas precize la sama.

964
01:15:11,040 --> 01:15:15,100
Do new_list, la valoro de nia new_list nodo,

965
01:15:15,100 --> 01:15:19,120
tuj estos nuna-> dekstren.

966
01:15:19,120 --> 01:15:24,280
La valoro de nia new_list-> sekva tuj estos nia originala listo,

967
01:15:24,280 --> 01:15:30,760
kaj poste ni iras al ĝisdatigi nian liston al punkto al new_list.

968
01:15:30,760 --> 01:15:33,650
>> Nun ni bezonas ian vojon de tirante aferojn,

969
01:15:33,650 --> 01:15:37,020
kiel ni trairis la tutan maldekstran subárbol.

970
01:15:37,020 --> 01:15:40,480
Nun ni bezonas tiri stuff el ĝi,

971
01:15:40,480 --> 01:15:43,850
kiel nuna estas nula; ni ne volas ĝuste redoni malvera.

972
01:15:43,850 --> 01:15:50,370
Ni volas nun tiri ekstere ĉe nia nova listo.

973
01:15:50,370 --> 01:15:53,690
Al oportuna maniero por tion fari - nu, efektive, ekzistas plurajn manierojn por fari tion.

974
01:15:53,690 --> 01:15:56,680
Ĉiu havas sugeston?

975
01:15:56,680 --> 01:15:58,790
Kie mi faru tiun aŭ kiel mi faru tion?

976
01:15:58,790 --> 01:16:08,010
Ni havas nur post kelkaj minutoj, sed neniu sugestojn?

977
01:16:08,010 --> 01:16:14,750
Anstataŭ - unu formo, anstataŭ nia kondiĉo esti dum,

978
01:16:14,750 --> 01:16:17,090
kion ni nuntempe rigardas ne nula,

979
01:16:17,090 --> 01:16:22,340
anstataŭ ni tuj daŭre iras ĝis nia listo mem estas nula.

980
01:16:22,340 --> 01:16:25,680
Do, se nia listo finas esti nula,

981
01:16:25,680 --> 01:16:30,680
tiam ni elĉerpas de aĵoj por serĉi, serĉo finiĝis.

982
01:16:30,680 --> 01:16:39,860
Sed tio signifas, ke la unua afero en nia listo estas nur tuj estos la unua nodo.

983
01:16:39,860 --> 01:16:49,730
La unua afero estos - ni ne plu bezonas vidi tion.

984
01:16:49,730 --> 01:16:58,710
Do listo-> n estos nia arbo.

985
01:16:58,710 --> 01:17:02,860
Listo-> sekva tuj estos nula.

986
01:17:02,860 --> 01:17:07,580
Kaj nun dum listo ne egala nula.

987
01:17:07,580 --> 01:17:11,610
Nuna tuj tiri ion de nia listo.

988
01:17:11,610 --> 01:17:13,500
Do nuna tuj egala listo-> n.

989
01:17:13,500 --> 01:17:20,850
Kaj poste listo tuj egala listo-> n, aŭ listo-> proksima.

990
01:17:20,850 --> 01:17:23,480
Do se nuna valoro egalas valoron.

991
01:17:23,480 --> 01:17:28,790
Nun ni povas aldoni ambaŭ niaj dekstra puntero kaj nia maldekstra puntero

992
01:17:28,790 --> 01:17:32,900
tiel longe kiel ili ne estas nula.

993
01:17:32,900 --> 01:17:36,390
Cxi tie, mi supozas ke ni devus fari ke en la unua loko.

994
01:17:36,390 --> 01:17:44,080
If (nuna-> dekstren! = NULL)

995
01:17:44,080 --> 01:17:56,380
tiam tuj enigi ke nodo en nian liston.

996
01:17:56,380 --> 01:17:59,290
If (nuna-> maldekstra), ĉi tiu estas iom da ekstra laboro, sed ĝi estas fajna.

997
01:17:59,290 --> 01:18:02,690
If (nuna-> maldekstra! = NULL),

998
01:18:02,690 --> 01:18:14,310
kaj ni tuj enigi la maldekstra en niajn ligitaj listo,

999
01:18:14,310 --> 01:18:19,700
kaj tio estu ĝi.

1000
01:18:19,700 --> 01:18:22,670
Ni persisti - kondiĉe ke ni havas ion en nia listo,

1001
01:18:22,670 --> 01:18:26,640
ni havos alian nodon por rigardi.

1002
01:18:26,640 --> 01:18:28,920
Do ni rigardas ke nodo,

1003
01:18:28,920 --> 01:18:31,390
ni antaŭi nia listo por la proksima.

1004
01:18:31,390 --> 01:18:34,060
Se tio nodo estas la valoro, ni serĉas, ni povas reveni vera.

1005
01:18:34,060 --> 01:18:37,640
Else enmeti ambaŭ nia maldekstra kaj dekstra subárboles,

1006
01:18:37,640 --> 01:18:40,510
tiel longe kiel ili ne estas nulaj, en nian liston

1007
01:18:40,510 --> 01:18:43,120
por ke ni neeviteble transiros ilin.

1008
01:18:43,120 --> 01:18:45,160
Do, se ili ne estis nula,

1009
01:18:45,160 --> 01:18:47,950
se niaj radiko puntero indikis du aferojn,

1010
01:18:47,950 --> 01:18:51,670
tiam unue ni tiris ion tiel nia listo finas esti nula.

1011
01:18:51,670 --> 01:18:56,890
Kaj tiam ni metas du aferoj denove en, do nun nia listo estas de amplekso 2.

1012
01:18:56,890 --> 01:19:00,030
Tiam ni iras por buklo back up kaj ni nur povos tion,

1013
01:19:00,030 --> 01:19:04,250
diru, la maldekstra puntero de nia radiko nodo.

1014
01:19:04,250 --> 01:19:07,730
Kaj tio estos ĝuste teni okazas; ni finos looping super ĉio.

1015
01:19:07,730 --> 01:19:11,280
>> Rimarku, ke tio signife pli komplika

1016
01:19:11,280 --> 01:19:14,160
en la rekursia solvo.

1017
01:19:14,160 --> 01:19:17,260
Kaj mi diris plurajn fojojn

1018
01:19:17,260 --> 01:19:25,120
ke la rekursia solvo kutime havas multon komunan kun la ripeta solvo.

1019
01:19:25,120 --> 01:19:30,820
Jen ĉi tiu estas ekzakte kion la rekursia solvo faras.

1020
01:19:30,820 --> 01:19:36,740
La sola ŝanĝo estas ke anstataŭ implice uzante la pilo, la programo pilo,

1021
01:19:36,740 --> 01:19:40,840
kiel via vojo de konservanta trako de kio nodoj vi ankoraŭ bezonas por viziti,

1022
01:19:40,840 --> 01:19:45,430
nun vi devas eksplicite uzas ligillisto.

1023
01:19:45,430 --> 01:19:49,070
En ambaŭ kazoj vi konservanta trako de kio nodo ankoraŭ bezonas esti vizitis.

1024
01:19:49,070 --> 01:19:51,790
En la rekursiaj kazo estas nur pli facile ĉar pilo

1025
01:19:51,790 --> 01:19:57,100
estas implementado por vi kiel la programo pilo.

1026
01:19:57,100 --> 01:19:59,550
Rimarku ke ĉi ligitaj listo, ĝi estas pilo.

1027
01:19:59,550 --> 01:20:01,580
Kion ajn ni nur metis en la stako

1028
01:20:01,580 --> 01:20:09,960
Estas tuj kion ni tuj detiri la pilo viziti proksima.

1029
01:20:09,960 --> 01:20:14,380
Ni estas el tempo, sed demandojn?

1030
01:20:14,380 --> 01:20:23,530
[Studento, nekomprenebla]

1031
01:20:23,530 --> 01:20:27,790
[Bowden] Yeah. Do, se ni havas niajn ligillisto,

1032
01:20:27,790 --> 01:20:30,150
nuna tuj atentigi al ĉi ulo,

1033
01:20:30,150 --> 01:20:34,690
kaj nun ni nur antaŭis nian ligillisto centri en ĉi tiu viro.

1034
01:20:34,690 --> 01:20:44,200
Ni lauxiris tra la ligitaj listo en tiu linio.

1035
01:20:44,200 --> 01:20:51,200
Kaj tiam mi supozas ke ni devus liberigi nian ligillisto kaj stuff

1036
01:20:51,200 --> 01:20:53,880
fojon antaŭ reveni vera aŭ malvera, ni bezonas

1037
01:20:53,880 --> 01:20:57,360
persisti super niaj ligitaj listo kaj ĉiam cxi tie, mi supozas,

1038
01:20:57,360 --> 01:21:03,900
se ni nuna rajto estas ne egala al, aldoni, do nun ni volas liberigi

1039
01:21:03,900 --> 01:21:09,600
nuna ĉar, nu, ni ne tute forgesi pri la listo? Yeah.

1040
01:21:09,600 --> 01:21:12,880
Do jen kion ni volas fari ĉi tie.

1041
01:21:12,880 --> 01:21:16,730
Kie estas la puntero?

1042
01:21:16,730 --> 01:21:23,320
Nuna estis tiam - ni volas al struct listo * 10 egalas listo proksima.

1043
01:21:23,320 --> 01:21:29,240
Libera listo, listo = temp.

1044
01:21:29,240 --> 01:21:32,820
Kaj en la kazo kie ni revenos vera, ni bezonas ankaŭ persisti

1045
01:21:32,820 --> 01:21:37,050
super la resto de nia ligillisto liberigante aĵoj.

1046
01:21:37,050 --> 01:21:39,700
La belan afero pri la rekursiaj solvo estas liberigi aĵoj

1047
01:21:39,700 --> 01:21:44,930
nur signifas krevi factorings ekstere la stako kiu okazos por vi.

1048
01:21:44,930 --> 01:21:50,720
Do ni iris de iu kiu estas kiel 3 linioj de malmola-al-pensas-pri kodo

1049
01:21:50,720 --> 01:21:57,520
al iu kiu estas signife multaj pli malmola-al-pensas-sur linioj de kodo.

1050
01:21:57,520 --> 01:22:00,620
Plu demandoj?

1051
01:22:00,620 --> 01:22:08,760
Bone. Ni estas bona. Ĝis!

1052
01:22:08,760 --> 01:22:11,760
[CS50.TV]