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

2
00:00:02,770 --> 00:00:05,090
[Rob Bowden] [Harvardeko Unibertsitateko]

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

4
00:00:07,930 --> 00:00:10,110
Guztiak eskubidea. Beraz, esan dut nire posta bezala,

5
00:00:10,110 --> 00:00:14,060
hau da bitar-zuhaitz-maila handiko atal bat izango da.

6
00:00:14,060 --> 00:00:16,820
Baina ez dira asko galderak.

7
00:00:16,820 --> 00:00:18,920
Beraz, galdera bakoitzean eta saiatu marraztu dugu

8
00:00:18,920 --> 00:00:25,430
eta gauzak egiteko modu onena xehetasun mingarriak sartu.

9
00:00:25,430 --> 00:00:31,200
Beraz, hasiera-hasieratik, lagin zuhaitz bitar eta stuff marrazkien bidez.

10
00:00:31,200 --> 00:00:35,970
Beraz, hemen, "Gogoratu binary zuhaitz bat nodo lotuta zerrenda antzekoak ditu,

11
00:00:35,970 --> 00:00:38,150
Erakuslea ordez izan ezik, bi dira: 'seme-alaba' ezkerreko bat

12
00:00:38,150 --> 00:00:41,950
eta eskuinera 'seme-alaba' bat. "

13
00:00:41,950 --> 00:00:45,630
Bitarra zuhaitz bat Beraz lotutako zerrenda bat besterik ez bezalakoa da,

14
00:00:45,630 --> 00:00:47,910
struct izan ezik, bi erakusle izan da.

15
00:00:47,910 --> 00:00:51,390
Ez trinary zuhaitzak, hiru erakusle izan behar diren,

16
00:00:51,390 --> 00:00:56,540
daude N-Ary zuhaitzak, besterik ez generic erakuslea

17
00:00:56,540 --> 00:01:00,320
Orduan duzu behar bezain handia izango da malloc

18
00:01:00,320 --> 00:01:04,840
erakusleak nahikoa posible seme-alaba guztiak.

19
00:01:04,840 --> 00:01:08,200
Beraz, binary zuhaitz gertatzen da bi zenbaki konstante bat izan da.

20
00:01:08,200 --> 00:01:11,260
Nahi izanez gero, zuhaitz unario lotutako zerrenda bat eman dezakezu,

21
00:01:11,260 --> 00:01:15,360
baina ez dut uste inork deitzen dela.

22
00:01:15,360 --> 00:01:18,060
"Marraztu zuhaitz bitar nodoaren diagrama kutxak-eta-geziak

23
00:01:18,060 --> 00:01:24,110
Nate gogokoena, 7, non erakuslea bakoitzean umearen null duten. "

24
00:01:24,110 --> 00:01:27,780
Beraz, iPad moduan.

25
00:01:27,780 --> 00:01:30,280
>> Nahiko erraza izango da.

26
00:01:30,280 --> 00:01:36,150
Nodo bat besterik ez gara, karratu bat marraztu dut.

27
00:01:36,150 --> 00:01:38,730
Eta balio marraztu dut hemen.

28
00:01:38,730 --> 00:01:41,090
Beraz, balioa egingo hemen,

29
00:01:41,090 --> 00:01:44,770
eta, ondoren, behera hemen erakuslea ezker ezkerreko eta eskuineko erakuslea eskubidea izango dugu.

30
00:01:44,770 --> 00:01:50,430
Eta asko da konbentzio, eta ezkerretik eskuinera, erakusle izenak deitu.

31
00:01:50,430 --> 00:01:52,460
Bi gauza horiek null izango dira.

32
00:01:52,460 --> 00:01:57,870
Izango dela besterik ez da hutsik egon, eta hori izan nahiko luke null.

33
00:01:57,870 --> 00:02:03,630
Ongi da. Beraz, hemen atzera.

34
00:02:03,630 --> 00:02:05,700
"Zerrenda bat lotuta, partidu besterik ez dugu erakuslea bat gorde

35
00:02:05,700 --> 00:02:09,639
lehen nodo zerrenda osoa lotuta zerrenda, edo zerrenda osoa gogoratzeko.

36
00:02:09,639 --> 00:02:11,650
Era berean, zuhaitzak, besterik ez dugu erakuslea bat gorde

37
00:02:11,650 --> 00:02:13,420
zuhaitz osoa gogoratzeko nodo bakar bat.

38
00:02:13,420 --> 00:02:15,980
Nodo hau calle da 'root' zuhaitza.

39
00:02:15,980 --> 00:02:18,320
Diagrama gainean Eraiki baino lehen, edo berri bat marraztu

40
00:02:18,320 --> 00:02:21,690
zuhaitz bitar bat irudikatze kutxak-eta-geziak duzula

41
00:02:21,690 --> 00:02:25,730
balioa 7 eta, ondoren, ezker 3,

42
00:02:25,730 --> 00:02:32,760
orduan eskubidea 9, eta, ondoren, 6 3 eskubidea. "

43
00:02:32,760 --> 00:02:34,810
Ikus dezagun hori guztia gogoratzen dut nire burua.

44
00:02:34,810 --> 00:02:37,670
Beraz, hau da gure root hemen izango da.

45
00:02:37,670 --> 00:02:41,600
Erakuslea nonbait izango dugu, root deituko dugun zerbait,

46
00:02:41,600 --> 00:02:45,140
eta lasaia hau seinalatuz.

47
00:02:45,140 --> 00:02:48,490
Orain nodo berria egiteko,

48
00:02:48,490 --> 00:02:52,870
zer dugu 3 ezkerretik?

49
00:02:52,870 --> 00:02:57,140
3 nodo berri bat, beraz, eta hasiera batean adierazi du null.

50
00:02:57,140 --> 00:02:59,190
Besterik ez dut jarri N.

51
00:02:59,190 --> 00:03:02,250
Orain 7 ezkerreko joan egin nahi dugu.

52
00:03:02,250 --> 00:03:06,840
Beraz, erakuslea hau aldatu dugu orain guy hau seinalatu.

53
00:03:06,840 --> 00:03:12,420
Eta gauza bera egin dugu. 9 hemen nahi dugu

54
00:03:12,420 --> 00:03:14,620
hasiera batean besterik ez dio null.

55
00:03:14,620 --> 00:03:19,600
Hau erakuslea, eta 9 puntu aldatzeko ari gara,

56
00:03:19,600 --> 00:03:23,310
eta, gaur egun, 6 3 eskubidea jarri nahi dugu.

57
00:03:23,310 --> 00:03:32,170
Beraz, - egin, 6.

58
00:03:32,170 --> 00:03:34,310
Eta lasaia ez dagoela seinalatu egingo.

59
00:03:34,310 --> 00:03:38,320
Ongi da. Beraz, galdetzen digu egin.

60
00:03:38,320 --> 00:03:42,770
>> Orain dezagun terminologia batzuk baino gehiago joan.

61
00:03:42,770 --> 00:03:46,690
Zuhaitzaren erro nola zuhaitzean nodo top-gehienak buruz hitz egin dugu dagoeneko.

62
00:03:46,690 --> 00:03:54,720
Bat duten 7. Zuhaitzaren beheko nodoak deitzen dira hostoak.

63
00:03:54,720 --> 00:04:01,240
Duen edozein besterik ez ditu bere seme-alabak gisa null nodo hosto bat da.

64
00:04:01,240 --> 00:04:03,680
Beraz, posible da, gure binary zuhaitz bakarra nodo bat baldin bada,

65
00:04:03,680 --> 00:04:10,130
zuhaitz baten hosto bat da, eta hori da.

66
00:04:10,130 --> 00:04:12,060
"'Zuhaitza' altuera Hops kopurua egin duzu

67
00:04:12,060 --> 00:04:16,620
goitik hosto bat lortzeko ".

68
00:04:16,620 --> 00:04:18,640
Lortuko dugu sartu, bigarren batean, diferentzia

69
00:04:18,640 --> 00:04:21,940
bitarra orekatua eta desorekatua zuhaitzen artean,

70
00:04:21,940 --> 00:04:29,470
baina orain, zuhaitz honen altuera, oro har

71
00:04:29,470 --> 00:04:34,520
Esan 3 nuke, zenbatu dituzu Hops kopurua nahiz

72
00:04:34,520 --> 00:04:39,710
9 lortu ahal izateko egin behar duzu, eta gero benetan soilik 2-ko altueran.

73
00:04:39,710 --> 00:04:43,340
Oraintxe desorekatua binary zuhaitz bat da,

74
00:04:43,340 --> 00:04:49,840
baina orekatua dugu hitz garrantzitsuak izan egingo du.

75
00:04:49,840 --> 00:04:52,040
Beraz, gaur egun zuhaitz baten nodo buruz hitz egin ahal izango dugu terminoetan

76
00:04:52,040 --> 00:04:54,700
erlatiboa zuhaitzean nodo beste.

77
00:04:54,700 --> 00:04:59,730
Beraz, gaur egun, gurasoak, seme-alabak, anai-arrebak, arbasoek eta ondorengoek dugu.

78
00:04:59,730 --> 00:05:05,650
Pretty sen dira, zer esan nahi dute.

79
00:05:05,650 --> 00:05:09,610
Galdetzen badugu gurasoek.

80
00:05:09,610 --> 00:05:12,830
Beraz, zer da 3 gurasoa da?

81
00:05:12,830 --> 00:05:16,090
[Ikasleak] 7. >> Bai. Gurasoa besterik ez da eta zer puntu izango da.

82
00:05:16,090 --> 00:05:20,510
Orduan, zer dira 7 seme-alabak?

83
00:05:20,510 --> 00:05:23,860
[Ikasleak] 3 eta 9. >> Bai.

84
00:05:23,860 --> 00:05:26,460
"Seme-alabak" literalki esan nahi seme-alabak,

85
00:05:26,460 --> 00:05:31,010
6, beraz, ez litzateke aplikatuko, grandchild bat bezalakoa delako.

86
00:05:31,010 --> 00:05:35,540
Baina orduan joaten gara ondorengoak izanez gero, eta, beraz, zer 7 ondorengoak dira?

87
00:05:35,540 --> 00:05:37,500
[Ikasleak] 3, 6 eta 9. >> Bai.

88
00:05:37,500 --> 00:05:42,330
Erroko nodoa ondorengoak dena izango da, zuhaitza,

89
00:05:42,330 --> 00:05:47,950
agian izan ezik erroko nodoa bera, ez baduzu nahi duten ondorengoa kontuan hartu behar dira.

90
00:05:47,950 --> 00:05:50,750
Eta, azkenik, arbasoak, eta, beraz, kontrako norabidean.

91
00:05:50,750 --> 00:05:55,740
Beraz, zer dira 6 arbasoen?

92
00:05:55,740 --> 00:05:58,920
[Ikasleak] 3 eta 7. >> Bai. 9 ez dago barne.

93
00:05:58,920 --> 00:06:02,520
Besterik ez da zuzena leinu erro atzera

94
00:06:02,520 --> 00:06:13,230
zure arbasoek izango.

95
00:06:13,230 --> 00:06:16,300
>> "Bitarrak zuhaitz bat da, 'agindu' esaten dugu, bada, zuhaitza nodo bakoitzean,

96
00:06:16,300 --> 00:06:19,530
bere ezker ondorengoak balio txikiagoan dituzte

97
00:06:19,530 --> 00:06:22,890
eta eskubidea dira guztiak handiagoa dute balio.

98
00:06:22,890 --> 00:06:27,060
Esate baterako, zuhaitz gainetik dago ordenatuta, baina ez da posible bakarra antolaketa agindu ".

99
00:06:27,060 --> 00:06:30,180
Dugun aurretik,

100
00:06:30,180 --> 00:06:36,420
agindu bitar zuhaitz da, baita ere, bilaketa bitarra zuhaitz bat bezala ezagutzen da.

101
00:06:36,420 --> 00:06:38,660
Hemen deituz bat agindu bitar zuhaitz gertatuko dugu,

102
00:06:38,660 --> 00:06:41,850
baina inoiz ez dut entzun binary zuhaitz bat agindu aurretik deitu zion,

103
00:06:41,850 --> 00:06:46,650
eta galdetegi bat askoz ere litekeena da bilaketa zuhaitz bitarraren jarri gara.

104
00:06:46,650 --> 00:06:49,250
Bat eta bera dira,

105
00:06:49,250 --> 00:06:54,580
eta garrantzitsua da ezagutzen duzun zuhaitz bitarra eta bitarra bilaketa zuhaitz arteko bereizketa.

106
00:06:54,580 --> 00:06:58,830
Binary zuhaitz bat zuhaitz bat besterik ez da, bi gauza puntuak.

107
00:06:58,830 --> 00:07:02,120
Nodo bakoitzak bi gauza adierazi.

108
00:07:02,120 --> 00:07:06,310
Adierazi du balioak buruzko arrazoibidea ez da.

109
00:07:06,310 --> 00:07:11,370
Beraz, nahi baino gehiago hemen, bilaketa zuhaitz bitar bat da geroztik,

110
00:07:11,370 --> 00:07:14,030
joan badugu 7 utzi badakigu,

111
00:07:14,030 --> 00:07:16,670
ondoren ahal izango dugu ziurrenik iritsiko balio guztiak

112
00:07:16,670 --> 00:07:19,310
7 utzi egingo dute 7 baino txikiagoa izan.

113
00:07:19,310 --> 00:07:24,070
Hasiera baino gutxiago 7 balore guztiak dira, 3 eta 6.

114
00:07:24,070 --> 00:07:26,040
Horiek guztiak 7 ezkerreko.

115
00:07:26,040 --> 00:07:29,020
7 eskubidea dugu joaten bada, dena 7 baino handiagoa izan behar du,

116
00:07:29,020 --> 00:07:33,220
beraz 9 7 eskubidea da eta, beraz, onak gara.

117
00:07:33,220 --> 00:07:36,150
Zuhaitz bitar bat ez da kasua,

118
00:07:36,150 --> 00:07:40,020
ohiko zuhaitz bitar bat besterik ez dugu goian, 7 ezkerraldeko 3,

119
00:07:40,020 --> 00:07:47,630
7 ezkerreko 9; ez balio inolako ordena.

120
00:07:47,630 --> 00:07:56,140
Orain, ez dugu benetan egiten da lapurtera eta alferrikako delako,

121
00:07:56,140 --> 00:07:59,400
baina "saiatu hainbat agindu zuhaitzak marraztu dezakezu pentsatzen

122
00:07:59,400 --> 00:08:01,900
zenbakiak 7, 3, 9, eta 6.

123
00:08:01,900 --> 00:08:06,800
Zenbat desberdin moldaketak daude? Zein da bakoitzaren altuera? "

124
00:08:06,800 --> 00:08:10,480
>> Pare bat egin dugu, baina ideia nagusia da,

125
00:08:10,480 --> 00:08:16,530
zuhaitz bitar bat balio hauek duten ordezkaritza bakarra ez da.

126
00:08:16,530 --> 00:08:22,760
Guztiak behar dugu, zuhaitz batzuk bitarrak dituen 7, 3, 6, eta 9.

127
00:08:22,760 --> 00:08:25,960
Beste ahalik eta baliozko bat root 3 izango litzateke,

128
00:08:25,960 --> 00:08:30,260
ezkerretara joan eta 6 da, ezkerrera joan eta 7 da,

129
00:08:30,260 --> 00:08:32,730
ezkerrera joan eta 9 da.

130
00:08:32,730 --> 00:08:36,169
Hori primeran baliozko bitar bilaketa zuhaitza da.

131
00:08:36,169 --> 00:08:39,570
Ez da oso lagungarria, lotuta zerrenda bezala delako

132
00:08:39,570 --> 00:08:43,750
eta erakusleak horiek guztiak ez dira besterik gabe, null.

133
00:08:43,750 --> 00:08:48,900
Baina baliozko zuhaitz bat da. Bai?

134
00:08:48,900 --> 00:08:51,310
[Student] Ez balioak eskubidea on handiagoa izan behar du?

135
00:08:51,310 --> 00:08:56,700
Edo da hau? >> Horiek beste modu batera joateko esan nahi dut.

136
00:08:56,700 --> 00:09:00,960
Dago ere bai, dezagun piztu dela.

137
00:09:00,960 --> 00:09:07,770
9, 7, 6, 3. Good harrapaketa.

138
00:09:07,770 --> 00:09:11,730
Du, hala ere, zer bitar zuhaitz bilaketa suposatzen da egin errespetatu.

139
00:09:11,730 --> 00:09:15,650
Beraz, dena ezkerreko edozein nodo baino gutxiago izan behar ditu.

140
00:09:15,650 --> 00:09:23,180
Besterik ez izan dugu mugitu, esan, hau 6 eta hemen jarri.

141
00:09:23,180 --> 00:09:26,880
Ez, ezin dugu onartu. Zergatik egiten dut?

142
00:09:26,880 --> 00:09:35,350
Egin dezagun - Hemen 6, 7, 6 eta 3 puntu.

143
00:09:35,350 --> 00:09:39,290
Hau da, oraindik baliozko bitar bilaketa zuhaitz bat.

144
00:09:39,290 --> 00:09:49,260
Zer da oker I - Ikus dezagun etorri naiz antolaketa batekin.

145
00:09:49,260 --> 00:09:52,280
Bai, ados. Beraz, zer da okerreko Zuhaitz hau?

146
00:09:52,280 --> 00:10:08,920
Nik dagoeneko eman duzu zerbait gaizki iradokizun bat asmatzen dut.

147
00:10:08,920 --> 00:10:14,430
Zergatik egiten dut?

148
00:10:14,430 --> 00:10:18,510
Ongi da. Badirudi arrazoizkoa.

149
00:10:18,510 --> 00:10:22,590
Nodo bakoitzean, 7 bezala eta, ondoren, ezkerreko 7 begiratuz gero, 3.

150
00:10:22,590 --> 00:10:24,960
Beraz, 3 ditugu, 3 eskubidea gauza bat da 6.

151
00:10:24,960 --> 00:10:27,750
Eta 6 begiratzen baduzu, 6 eskubidea gauza bat eta 9.

152
00:10:27,750 --> 00:10:30,910
Beraz, zergatik ez da baliozko bitar bilaketa zuhaitza?

153
00:10:30,910 --> 00:10:36,330
[Ikasleak] 9 oraindik 7 ezkerreko. >> Bai.

154
00:10:36,330 --> 00:10:43,710
Egia ziurrenik dezakezu ezkerreko 7 joan iristeko balio guztiak 7 baino gutxiago izan behar da.

155
00:10:43,710 --> 00:10:49,120
Joaten gara 7 geratzen bada, 3 eta 6 eskuratu ahal izango dugu, oraindik ere,

156
00:10:49,120 --> 00:10:52,520
eta 9 oraindik ere eskuratu ahal izango dugu, baina ondoren desagertu baino 7 gutxiago,

157
00:10:52,520 --> 00:10:55,070
, 7 baino handiagoa da kopuru hori lortzeko gai izan behar dugu.

158
00:10:55,070 --> 00:10:59,830
Beraz, hau ez da baliozko bitar bilaketa zuhaitza.

159
00:10:59,830 --> 00:11:02,330
>> Nire anaia benetan elkarrizketa galdera bat izan

160
00:11:02,330 --> 00:11:07,760
izan zen, funtsean, hau da, kodea zerbait baliozkotzeko sortu

161
00:11:07,760 --> 00:11:10,500
zuhaitz bat edo bilaketa zuhaitz bitar bat da,

162
00:11:10,500 --> 00:11:13,580
eta, beraz, egin zuen lehen gauza izan zen ikusteko, egiaztatu

163
00:11:13,580 --> 00:11:17,020
ezkerreko eta eskuineko zuzena bada, eta, ondoren, batetik bestera joateko hor behera.

164
00:11:17,020 --> 00:11:19,700
Baina ezin duzun hori egiteko; pista jarraitu behar duzu

165
00:11:19,700 --> 00:11:22,550
Izan ere, orain dela utzi 7 dut joan,

166
00:11:22,550 --> 00:11:26,340
Azpizuhaitza hau guztia 7 baino txikiagoa izan behar du.

167
00:11:26,340 --> 00:11:28,430
Algoritmoa zuzena behar segimendua egiteko

168
00:11:28,430 --> 00:11:35,970
mugetatik kanpo balioak ziurrenik erori sartu

169
00:11:35,970 --> 00:11:38,360
Ez dugu horien guztien bidez.

170
00:11:38,360 --> 00:11:41,630
Polit bat errepikatze aldean, hau da,

171
00:11:41,630 --> 00:11:44,810
dugu, nahiz eta ez duten ahaztuak, edo ez ditugu horiek,

172
00:11:44,810 --> 00:11:47,030
zenbat benetan dira definituz.

173
00:11:47,030 --> 00:11:53,180
Beraz, horietako 14 daude.

174
00:11:53,180 --> 00:11:56,020
Nola egin nahi duzun ideia matematikoki bezala,

175
00:11:56,020 --> 00:11:59,770
bakar bat hauta dezakezu erroko nodoa izango da,

176
00:11:59,770 --> 00:12:03,160
eta, ondoren, pick I 7 erroko nodoa izango da,

177
00:12:03,160 --> 00:12:08,150
egongo dira, adibidez, zenbaki batzuk izan nire ezker nodo joan

178
00:12:08,150 --> 00:12:10,440
eta nire eskuineko nodo izan daiteke zenbaki batzuk daude,

179
00:12:10,440 --> 00:12:15,090
baina I guztira zenbakiak, ondoren, ezkerrera joan zenbatekoa bada n

180
00:12:15,090 --> 00:12:18,820
gehi zenbatekoa eskuinera joan ahal izango da N - 1.

181
00:12:18,820 --> 00:12:26,130
Beraz, gainerako zenbakiak, bai ezkerrera edo eskuinera joateko gai izan behar dute.

182
00:12:26,130 --> 00:12:31,580
Zaila dirudi, jarri dut 3 bada lehen, ondoren, dena behar du ezker joan,

183
00:12:31,580 --> 00:12:35,080
baina jarri badut 7, orduan gauza batzuk ezkerreko joan daiteke, eta gauza batzuk eskuinera joan daiteke.

184
00:12:35,080 --> 00:12:39,570
Eta '3 'lehen dena eskubidea esan nahi dut.

185
00:12:39,570 --> 00:12:42,350
Benetan da, besterik ez duzu pentsatu,

186
00:12:42,350 --> 00:12:47,980
zenbat gauza zuhaitzaren hurrengo maila joan.

187
00:12:47,980 --> 00:12:50,420
Eta orduan 14 izango da, edo horiek guztiak marraztu ahal izango duzu,

188
00:12:50,420 --> 00:12:54,650
eta, ondoren, 14 jaso ahal izango duzu.

189
00:12:54,650 --> 00:13:01,120
>> Atzera eginez hemen,

190
00:13:01,120 --> 00:13:03,510
"Eskatutako zuhaitz bitarrak dira cool ahal izango dugu, horien bitartez delako bilatu

191
00:13:03,510 --> 00:13:06,910
ordenatuko array bat baino gehiago bilatzeko modu bat, oso antzekoa da.

192
00:13:06,910 --> 00:13:10,120
Horretarako, hasteko, errotik dugu eta gure modu lan behera zuhaitz

193
00:13:10,120 --> 00:13:13,440
hostoak bidean, egiaztatuko Nodo bakoitzaren balioak balioak ari gara bilatzen aurka.

194
00:13:13,440 --> 00:13:15,810
Uneko nodoaren balioa balioa baino txikiagoa bada bilatzen ari gara,

195
00:13:15,810 --> 00:13:18,050
nodo eskubidea seme-alaba ondoan joan behar dute.

196
00:13:18,050 --> 00:13:20,030
Bestela, joan nodo ezker seme-alaba.

197
00:13:20,030 --> 00:13:22,800
Uneren batean, bai dituzu balioa aurkitu bilatzen ari zaren, edo null batean exekuta dituzu,

198
00:13:22,800 --> 00:13:28,520
balioa adierazten ez zuhaitza ".

199
00:13:28,520 --> 00:13:32,450
Aurretik izan genuen zuhaitz marraztu behar dut; duen bigarren bat hartuko dugu.

200
00:13:32,450 --> 00:13:38,280
Baina bilatuko 6, 10, eta 1 ala ez zuhaitza nahi dugu.

201
00:13:38,280 --> 00:13:49,180
Beraz, zer izan zen, 7, 9, 3, 6. Ongi da.

202
00:13:49,180 --> 00:13:52,730
Sortu begiratu nahi duzun, zenbakiak bilatuko 6 nahi dugu.

203
00:13:52,730 --> 00:13:55,440
Nola ez du algoritmoa lan?

204
00:13:55,440 --> 00:14:03,040
Beno, izan ere, gure zuhaitz root batzuk erakuslea.

205
00:14:03,040 --> 00:14:12,460
Eta erro genuke joan eta esan, balio hau bilatzen ari gara balioa berdina da?

206
00:14:12,460 --> 00:14:15,000
Beraz, 6 ari gara begira, beraz, ez da berdina.

207
00:14:15,000 --> 00:14:20,140
Beraz jarraitzea dugu, eta gaur egun esan genezake, ados, eta, beraz, 6 7 baino txikiagoa da.

208
00:14:20,140 --> 00:14:23,940
Esan nahi du ezker joan nahi dugu, edo eskuinera joan nahi dugu?

209
00:14:23,940 --> 00:14:27,340
[Student] Ezker. >> Bai.

210
00:14:27,340 --> 00:14:33,340
Nabarmen errazagoa da, egin behar duzun guztia zuhaitzaren nodo bat posible marraztu da

211
00:14:33,340 --> 00:14:37,760
eta, ondoren, don't duzu zure burua uste ordez saiatzen

212
00:14:37,760 --> 00:14:40,020
ados, bada gutxiago, ez joan ezkerrera edo eskuinera joan,

213
00:14:40,020 --> 00:14:43,030
argazki hau begira, oso argia da ezkerretik joan behar dut

214
00:14:43,030 --> 00:14:47,700
nodo hau da naiz I bila balioa baino handiagoa bada.

215
00:14:47,700 --> 00:14:52,600
Beraz, ezker, gaur egun, 3 naiz.

216
00:14:52,600 --> 00:14:57,770
Nahi dut - 3 balioa bilatzen dut, hau da, 6 baino txikiagoa da.

217
00:14:57,770 --> 00:15:03,420
Beraz, joateko eskubidea dugu, eta orain amaituko dut 6,

218
00:15:03,420 --> 00:15:07,380
balioa bila nabil, itzuliko naiz egia, beraz.

219
00:15:07,380 --> 00:15:15,760
Begiratu dut hurrengo balioa 10 da.

220
00:15:15,760 --> 00:15:23,230
Ongi da. Moztu - root jarraitu egingo 10 Beraz, gaur egun, da joan.

221
00:15:23,230 --> 00:15:27,670
Orain, 10 da, 7 baino handiagoa izan behar du, beraz, eskuinera begiratu nahi dut.

222
00:15:27,670 --> 00:15:31,660
Baino gehiago etorri hemen noa, 10 9 baino handiagoa izan behar du,

223
00:15:31,660 --> 00:15:34,520
beraz, eskuinera begiratu nahi dut.

224
00:15:34,520 --> 00:15:42,100
Hemen baino gehiago naiz, baina orain hemen nago null dut.

225
00:15:42,100 --> 00:15:44,170
Zer hit I null bada egin behar dut?

226
00:15:44,170 --> 00:15:47,440
[Student] itzuli gezurra? >> Bai. Ez dut aurkitu 10.

227
00:15:47,440 --> 00:15:49,800
1 da kasu ia berdin-berdina izango da,

228
00:15:49,800 --> 00:15:51,950
izan ezik da iraulita dira joan ordez bila

229
00:15:51,950 --> 00:15:56,540
eskuinaldean behera, ezker hegalean behera begiratu dut.

230
00:15:56,540 --> 00:16:00,430
>> Orain benetan kodea gara uste dut.

231
00:16:00,430 --> 00:16:04,070
Hona hemen non - ireki CS50-tresnak eta zure bidea nabigatzeko han,

232
00:16:04,070 --> 00:16:07,010
baina era berean, besterik gabe egin espazioan.

233
00:16:07,010 --> 00:16:09,170
Izango da seguru asko, ideal egiten espazioa,

234
00:16:09,170 --> 00:16:13,760
espazioa delako lan dezakegu.

235
00:16:13,760 --> 00:16:19,170
"Lehenik eta behin, int balio duten zuhaitz bitar nodo mota definizio berria behar dugu.

236
00:16:19,170 --> 00:16:21,400
Boilerplate typedef azpitik erabiliz,

237
00:16:21,400 --> 00:16:24,510
zuhaitz bitar bat nodo bat definizio mota berri bat sortzeko.

238
00:16:24,510 --> 00:16:27,930
Trabatuta gelditzen bazara. . . "Blah, blah, blah. Larreina.

239
00:16:27,930 --> 00:16:30,380
Hargatik jarri boilerplate hemen,

240
00:16:30,380 --> 00:16:41,630
typedef struct nodoa, eta nodo. Bai, ados.

241
00:16:41,630 --> 00:16:44,270
Beraz, zer dira eremu gure nodo nahi dugu?

242
00:16:44,270 --> 00:16:46,520
[Student] Int, eta, ondoren, bi erakusleak?

243
00:16:46,520 --> 00:16:49,700
>> Int balioa, bi erakusleak? Nola erakusleak idazten dut?

244
00:16:49,700 --> 00:16:58,440
[Student] egitura. >> Mapan handiago sartu beharko nuke Bai, eta, beraz, egiturari nodo * utzi,

245
00:16:58,440 --> 00:17:01,320
eta egiturari nodo * eskuinera.

246
00:17:01,320 --> 00:17:03,460
Eta azken eztabaida gogoratzeko,

247
00:17:03,460 --> 00:17:15,290
horrek ez du zentzurik, ez du zentzurik

248
00:17:15,290 --> 00:17:18,270
hau da, ez du zentzurik.

249
00:17:18,270 --> 00:17:25,000
Recursive struct hau definitzeko, dena ez behar duzu.

250
00:17:25,000 --> 00:17:27,970
Ados, beraz, zein den gure zuhaitz itxura.

251
00:17:27,970 --> 00:17:37,670
Genuen trinary zuhaitz bat bada, orduan nodo bat izan liteke b1, b2, struct nodo * b3 bezala "Zaharregia, txikiegia agian

252
00:17:37,670 --> 00:17:43,470
, non b adar bat da, benetan, gehiago dut entzun, utzi, erdi-erdian, eskuineko, baina edozein dela ere.

253
00:17:43,470 --> 00:17:55,610
Bitarra zaintzeko besterik ez ditugu, eta, beraz, eskuinera, ezkerrera.

254
00:17:55,610 --> 00:17:59,110
"Orain deklaratu global nodo * aldagaiak zuhaitzaren erroan."

255
00:17:59,110 --> 00:18:01,510
Beraz, ez ari gara horretarako.

256
00:18:01,510 --> 00:18:08,950
Gauzak apur bat zailagoa da eta gehiago orokortua egiteko,

257
00:18:08,950 --> 00:18:11,570
ez nodo aldagai global bat izango dugu.

258
00:18:11,570 --> 00:18:16,710
Horren ordez, nagusia gure gauzak nodo guztiak aldarrikatu ahal izango dugu,

259
00:18:16,710 --> 00:18:20,500
eta horrek esan nahi du azpian, exekutatzen hasten gara

260
00:18:20,500 --> 00:18:23,130
Gure Contiene funtzioa eta gure txertatze-funtzioa,

261
00:18:23,130 --> 00:18:27,410
gure daukan ordez funtzioa besterik ez global nodo aldagai hau erabiliz,

262
00:18:27,410 --> 00:18:34,280
argumentu gisa zuhaitza izan dugu prozesatu da nahi dugun.

263
00:18:34,280 --> 00:18:36,650
Global aldagaia izatea zen ustezko gauzak errazteko.

264
00:18:36,650 --> 00:18:42,310
Gauza gogorragoa egin dugu.

265
00:18:42,310 --> 00:18:51,210
Orain, hartu minutu bat edo, beraz, gauza sort besterik ez egin,

266
00:18:51,210 --> 00:18:57,690
non barruan nagusia Zuhaitz hau sortu nahi baduzu, eta hori da egin nahi duzun guztia.

267
00:18:57,690 --> 00:19:04,530
Saiatu eta Zuhaitz hau eraikitzeko zure eginkizun nagusia.

268
00:19:42,760 --> 00:19:47,610
>> Ongi da. Beraz, ez duzu ere eraiki zuhaitz osoa oraindik.

269
00:19:47,610 --> 00:19:49,840
Baina inor tira sortu nuen zerbait

270
00:19:49,840 --> 00:20:03,130
erakusteko nola zuhaitz bat, eraikitzen hasteko daiteke?

271
00:20:03,130 --> 00:20:08,080
[Student] Norbaitek banging, atera nahian.

272
00:20:08,080 --> 00:20:13,100
[Bowden] Edonork beren zuhaitz eraikuntza eroso?

273
00:20:13,100 --> 00:20:15,520
[Student] Sure. Ez da egin. >> Fina da. Besterik ez dugu amaitzeko

274
00:20:15,520 --> 00:20:26,860
oh, gorde daiteke duzu? Hooray.

275
00:20:26,860 --> 00:20:32,020
Beraz, hemen dugu - oh, apur bat dut moztu.

276
00:20:32,020 --> 00:20:34,770
Am handitutako I?

277
00:20:34,770 --> 00:20:37,730
Handiagotzeko, joan. >> Galdera bat daukat. >> Bai?

278
00:20:37,730 --> 00:20:44,410
[Student] eta egitura definitzeko, ezer hasieratu bezalako gauzak dira?

279
00:20:44,410 --> 00:20:47,160
[Bowden] n. >> Ados. Beraz, hasieratu nahi duzun

280
00:20:47,160 --> 00:20:50,450
[Bowden] N º denean, zehaztu edo noiz aldarrikatu eta egitura bat,

281
00:20:50,450 --> 00:20:55,600
lehenespenez ez da hasieratu; just like it aldarrikatu int bat bada.

282
00:20:55,600 --> 00:20:59,020
Zehazki, gauza bera da. Bere eremu banakako bakoitzean bezalakoa da

283
00:20:59,020 --> 00:21:04,460
zabor-balio bat izan daiteke. >> Eta definitzeko aukera ematen du - edo aldarrikatzen eta egitura

284
00:21:04,460 --> 00:21:07,740
ez dela modu bat hasieratu horiek?

285
00:21:07,740 --> 00:21:13,200
[Bowden] Bai. Beraz, laster-Hasieratzea sintaxia

286
00:21:13,200 --> 00:21:18,660
itxura -

287
00:21:18,660 --> 00:21:22,200
Ez da bi modu hau egin ahal izango dugu. Konpilatu behar dugula uste dut

288
00:21:22,200 --> 00:21:25,840
Ziur Clang egiteko ere ez du.

289
00:21:25,840 --> 00:21:28,510
Argumentu ordena dator, eta egitura,

290
00:21:28,510 --> 00:21:32,170
kizkur giltza horien barruan argumentuak ordena jarri duzun bezala.

291
00:21:32,170 --> 00:21:35,690
Beraz, bada abiarazi 9 nahi duzun eta utz null eta, ondoren, eskubidea izango null

292
00:21:35,690 --> 00:21:41,570
9 izango litzateke, null, null.

293
00:21:41,570 --> 00:21:47,890
Alternatiba da, eta editoreak ez sintaxia hau gustatzen,

294
00:21:47,890 --> 00:21:50,300
eta bloke berri bat nahi dut pentsatzen,

295
00:21:50,300 --> 00:22:01,800
baina alternatiba da zerbait

296
00:22:01,800 --> 00:22:04,190
Hemen, lerro berri bat jarri dut.

297
00:22:04,190 --> 00:22:09,140
Esplizituki esan dezakezu, sintaxia zehatza ahaztu dut.

298
00:22:09,140 --> 00:22:13,110
Beraz, esplizituki dezakezu aurre izenaren arabera, eta esan,

299
00:22:13,110 --> 00:22:21,570
C, edo. = 9, ezkerreko = NULL balioa.

300
00:22:21,570 --> 00:22:24,540
Premia horiek koma izan dut asmatzen.

301
00:22:24,540 --> 00:22:29,110
Eskubidea = NULL, beraz, modu honetan ez duzu

302
00:22:29,110 --> 00:22:33,780
benetan behar struct-ordena ezagutzeko.

303
00:22:33,780 --> 00:22:36,650
eta hau irakurtzen ari zaren, askoz ere esplizitua da

304
00:22:36,650 --> 00:22:41,920
zer balio ari hasieratu.

305
00:22:41,920 --> 00:22:44,080
>> Gertatzen da hori gauza bat izango -

306
00:22:44,080 --> 00:22:49,100
beraz, zati handiena, C + + C. superset bat da

307
00:22:49,100 --> 00:22:54,160
C-kodea hartu dezakezu, mugitu C + +, eta konpilatu beharko luke.

308
00:22:54,160 --> 00:22:59,570
C + + onartzen ez gauza bat da, beraz, pertsona joera ez da egin behar.

309
00:22:59,570 --> 00:23:01,850
Ez dakit hori arrazoi bakarra jendea joera ez da egin behar izanez gero,

310
00:23:01,850 --> 00:23:10,540
baina kasu non erabili behar dut C + + eta, beraz, ezin dut hau erabili behar.

311
00:23:10,540 --> 00:23:14,000
Zerbait beste adibide bat ez da C + + da

312
00:23:14,000 --> 00:23:16,940
nola malloc "void *," itzultzen du teknikoki,

313
00:23:16,940 --> 00:23:20,200
baina,, char * x = malloc edozein dela ere esan ahal izango duzu,

314
00:23:20,200 --> 00:23:22,840
eta automatikoki, char * bat bota.

315
00:23:22,840 --> 00:23:25,450
Automatikoa cast Hori ez da gertatuko C + +.

316
00:23:25,450 --> 00:23:28,150
Hori ez litzateke konpilatu, eta esplizituki esan beharko zenuke

317
00:23:28,150 --> 00:23:34,510
char *, malloc, edozein izanda ere, char * urtu.

318
00:23:34,510 --> 00:23:37,270
Ez daude C eta C + + ados gauza asko,

319
00:23:37,270 --> 00:23:40,620
baina bi dira.

320
00:23:40,620 --> 00:23:43,120
Beraz, sintaxi honekin dugu.

321
00:23:43,120 --> 00:23:46,150
Baina nahiz eta ez genuen sintaxia duten,

322
00:23:46,150 --> 00:23:49,470
zer da honekin oker egon daiteke?

323
00:23:49,470 --> 00:23:52,170
[Student] ez dut behar dereference da? >> Bai.

324
00:23:52,170 --> 00:23:55,110
Gogoratu gezi dereference inplizitu bat du,

325
00:23:55,110 --> 00:23:58,230
eta, beraz, besterik gabe, ari gara eta egitura batekin aurre egiteko,

326
00:23:58,230 --> 00:24:04,300
erabili nahi dugu. struct-eremu bat barrutik.

327
00:24:04,300 --> 00:24:07,200
Eta denbora arrow bakarra erabiltzen dugu gertatzen da, hain zuzen ere, egin nahi dugun

328
00:24:07,200 --> 00:24:13,450
ondo, arrow baliokidea -

329
00:24:13,450 --> 00:24:17,020
hori zer ekarri litzateke erabili dut arrow bada.

330
00:24:17,020 --> 00:24:24,600
Da gezi-bide guztiak, dereference hau, gaur egun, naiz eta egitura bat dut, eta eremuan lor daiteke.

331
00:24:24,600 --> 00:24:28,040
Edo Eremu zuzenean edo dereference eta eremuan

332
00:24:28,040 --> 00:24:30,380
Balio hau izan behar uste dut.

333
00:24:30,380 --> 00:24:33,910
Baina hemen eta egitura bat besterik ez, ez da egitura erakuslea aurre naiz,

334
00:24:33,910 --> 00:24:38,780
eta beraz, ezin dut erabili gezi-.

335
00:24:38,780 --> 00:24:47,510
Baina gauza sort honetan nodo guztiak egin ahal izango dugu.

336
00:24:47,510 --> 00:24:55,790
Oh my God.

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

338
00:25:09,540 --> 00:25:16,470
Ondoren ezarri ahal izango ditugu, gure zuhaitz adarrak, 7 izan dezakegu

339
00:25:16,470 --> 00:25:21,650
dute, haren ezkerreko behar 3 seinalatu.

340
00:25:21,650 --> 00:25:25,130
Beraz, zer egiten dugu hori?

341
00:25:25,130 --> 00:25:29,320
[Ikasleak, ulertezinak] >> Bai. Node3 helbidea,

342
00:25:29,320 --> 00:25:34,170
eta ez bada ez duzu helbidea, Orduan, besterik gabe, ez konpilatu.

343
00:25:34,170 --> 00:25:38,190
Baina gogoratu horiek hurrengo nodoak erakusleak.

344
00:25:38,190 --> 00:25:44,930
Eskubidea 9 seinalatu behar du,

345
00:25:44,930 --> 00:25:53,330
eta 3 6 eskubidea seinalatu behar.

346
00:25:53,330 --> 00:25:58,480
Nik uste dut, hau da multzo. Iruzkinak edo galdera?

347
00:25:58,480 --> 00:26:02,060
[Ikaslea, ulertezina] sustraia 7 izango da.

348
00:26:02,060 --> 00:26:08,210
Bakarrik esan dezakegu nodo * ptr =

349
00:26:08,210 --> 00:26:14,160
edo root = & node7.

350
00:26:14,160 --> 00:26:20,730
>> Gure helburuetarako, txertatze dira aurre dugu,

351
00:26:20,730 --> 00:26:25,490
beraz, zuhaitz honen bitar txertatzeko funtzio bat idatzi nahi dugu

352
00:26:25,490 --> 00:26:34,230
eta txertatze da ezinbestean malloc deitu Zuhaitz hau nodo berri bat sortu nahi du.

353
00:26:34,230 --> 00:26:36,590
Beraz, gauzak messy Izan ere, nodo batzuk

354
00:26:36,590 --> 00:26:38,590
Une honetan pilaketan

355
00:26:38,590 --> 00:26:43,680
eta beste nodo amaitzeko zeure gainean sartu dugu.

356
00:26:43,680 --> 00:26:47,640
Hau guztiz baliozkoa da, baina arrazoia

357
00:26:47,640 --> 00:26:49,600
hau egin ahal pilaketan gara

358
00:26:49,600 --> 00:26:51,840
adibide bat contrived, besteak beste, ezagutzen dugu delako

359
00:26:51,840 --> 00:26:56,360
zuhaitza da ustezko 7, 3, 6, 9 eraiki ahal izateko.

360
00:26:56,360 --> 00:27:02,970
Genuen hau ez bada, orduan ez genuke malloc lehenik eta behin.

361
00:27:02,970 --> 00:27:06,160
Pixka bat geroago ikusiko dugun bezala dugu, malloc'ing behar dugu.

362
00:27:06,160 --> 00:27:08,570
Oraintxe Erabat arrazoizkoa da pila jarri,

363
00:27:08,570 --> 00:27:14,750
baina ez dezagun hau aldatu malloc ezartzea.

364
00:27:14,750 --> 00:27:17,160
Beraz, horietako bakoitzak gaur egun antzeko zerbait izango

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

366
00:27:24,240 --> 00:27:28,040
Eta orain, gure kontrol egin behar dugu.

367
00:27:28,040 --> 00:27:34,010
(== NULL node9) - ez dut nahi -

368
00:27:34,010 --> 00:27:40,950
itzuli 1, eta, ondoren, node9> egin ahal izango dugu orain erakuslea delako,

369
00:27:40,950 --> 00:27:45,300
balioa = 6, node9-> utzi = NULL,

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

371
00:27:48,930 --> 00:27:51,410
eta horretarako nodo horietako bakoitzean izan dugu.

372
00:27:51,410 --> 00:27:57,490
Beraz, horren ordez, dezagun jarri barruan aparteko funtzioa.

373
00:27:57,490 --> 00:28:00,620
Dezagun nodo * build_node

374
00:28:00,620 --> 00:28:09,050
Huffman kodeketa APIak eskaintzen dugu zertxobait antzekoa da.

375
00:28:09,050 --> 00:28:12,730
Ematen dugu initializer funtzioak zuhaitz baten

376
00:28:12,730 --> 00:28:20,520
deconstructor "funtzio" horiek zuhaitzak eta basoak berean.

377
00:28:20,520 --> 00:28:22,570
>> Beraz hemen initializer-funtzio bat izan dugu

378
00:28:22,570 --> 00:28:25,170
besterik ez eraikitzeko Gurekin nodo bat.

379
00:28:25,170 --> 00:28:29,320
Eta pretty askoz ere itxura zehazki hau atsegin dute.

380
00:28:29,320 --> 00:28:32,230
Eta are dut alferrak izan da, eta ez, aldagaiaren izena aldatu,

381
00:28:32,230 --> 00:28:34,380
nahiz eta node9 ez du zentzurik jada.

382
00:28:34,380 --> 00:28:38,610
Oh, node9 balio uste dut behar ez izan 6.

383
00:28:38,610 --> 00:28:42,800
Orain node9 itzuli ahal izango dugu.

384
00:28:42,800 --> 00:28:49,550
Eta hemen itzuli null behar dugu.

385
00:28:49,550 --> 00:28:52,690
Guztiek build-a-nodo funtzio hori ados?

386
00:28:52,690 --> 00:28:59,780
Beraz, gaur egun besterik ez diegu balio bat eman eta erakusleak null nodo edozein eraikitzeko.

387
00:28:59,780 --> 00:29:09,750
Orain deitzen dugu, nodo * node9 = build_node (9) egin ahal izango dugu.

388
00:29:09,750 --> 00:29:25,810
Eta utzi egin. . .

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

390
00:29:33,980 --> 00:29:39,330
Eta orain ezarri nahi dugu, bera erakusle

391
00:29:39,330 --> 00:29:42,470
Orain dela izan ezik guztia erakusleak dagokionez dagoeneko

392
00:29:42,470 --> 00:29:48,480
beraz, ez da gehiago behar helbidea.

393
00:29:48,480 --> 00:29:56,300
Ongi da. Beraz, zer egin nahi dut azken gauza?

394
00:29:56,300 --> 00:30:03,850
Errorea gertatu da egiaztapena naiz ez dut egiten.

395
00:30:03,850 --> 00:30:06,800
Zer da nodo bueltan eraiki du?

396
00:30:06,800 --> 00:30:11,660
[Ikaslea, ulertezina] >> Bai. Malloc bada huts egin du, eta itzuli null duzu.

397
00:30:11,660 --> 00:30:16,460
Beraz, lazily hemen jarri ordez, bakoitzaren baldintza bat egiten dut.

398
00:30:16,460 --> 00:30:22,320
(Node9 == NULL, edo are errazagoa,

399
00:30:22,320 --> 00:30:28,020
hau da, besterik ez bada ez node9 baliokidea.

400
00:30:28,020 --> 00:30:38,310
Beraz, ez bada node9, edo ez node6, edo ez node3, edo ez node7, itzuliko 1.

401
00:30:38,310 --> 00:30:42,850
Agian inprimatu malloc huts egin du, edo zerbait behar dugu.

402
00:30:42,850 --> 00:30:46,680
[Student] faltsua baita null berdina al da?

403
00:30:46,680 --> 00:30:51,290
[Bowden] Edozein zero balioa faltsua da.

404
00:30:51,290 --> 00:30:53,920
Beraz, null balioa zero da.

405
00:30:53,920 --> 00:30:56,780
Zero balioa zero da. False balioa zero da.

406
00:30:56,780 --> 00:31:02,130
Edozein - pretty askoz bakarra 2 null balioak zero dira eta zero,

407
00:31:02,130 --> 00:31:07,900
faltsua besterik ez da hash zero bezala definitzen da.

408
00:31:07,900 --> 00:31:13,030
Hori ere aplikatzen global aldagai aldarrikatu ezean.

409
00:31:13,030 --> 00:31:17,890
Genuen nodo * root Hemen bada,

410
00:31:17,890 --> 00:31:24,150
ondoren, aldagai global buruz gauza polita da beti hasierako balioa dutela.

411
00:31:24,150 --> 00:31:27,500
Hori ez da egia nola, funtzio barruan, hemen,

412
00:31:27,500 --> 00:31:34,870
badugu, adibidez, nodoak * edo nodoaren x.

413
00:31:34,870 --> 00:31:37,380
Ez daki zer x.value, x.whatever ditugu,

414
00:31:37,380 --> 00:31:40,700
edo inprimatu izan dugu eta arbitrarioak izan dira.

415
00:31:40,700 --> 00:31:44,980
Hori ez da egia aldagai global.

416
00:31:44,980 --> 00:31:47,450
Beraz, erroko nodoa edo nodoaren x.

417
00:31:47,450 --> 00:31:53,410
Berez, hori guztia global, ez bada esplizituki balio batzuk hasieratu

418
00:31:53,410 --> 00:31:57,390
bere balioa zero balioa du.

419
00:31:57,390 --> 00:32:01,150
Hortaz, hona hemen, nodoen * root, ez dugu esplizituki hasieratu da ezer,

420
00:32:01,150 --> 00:32:06,350
beraz, bere balio lehenetsia null izango da, erakusleak balioa zero da.

421
00:32:06,350 --> 00:32:11,870
X-en balio lehenetsia da x.value dela zero esan nahi du,

422
00:32:11,870 --> 00:32:14,260
da x.left null, eta x.right null da.

423
00:32:14,260 --> 00:32:21,070
Beraz, geroztik, eta egitura bat da, struct, eremu guztietan zero balio izango da.

424
00:32:21,070 --> 00:32:24,410
Guk ez dugu hemen erabili behar da, nahiz eta.

425
00:32:24,410 --> 00:32:27,320
[Student] structs desberdinak dira beste aldagai batzuk baino, eta beste aldagai

426
00:32:27,320 --> 00:32:31,400
zabor balio; zeroen dira?

427
00:32:31,400 --> 00:32:36,220
[Bowden] Beste balioak ere. Beraz, x, x zero izango da.

428
00:32:36,220 --> 00:32:40,070
Esparrua mundu gero, hasierako balioa du. >> Ados.

429
00:32:40,070 --> 00:32:48,950
[Bowden] Edo hasierako balioa edo zero eman zenuen.

430
00:32:48,950 --> 00:32:53,260
Nik uste dut hori guztia arduratzen da.

431
00:32:53,260 --> 00:32:58,390
>> Ongi da. Beraz, hurrengo galdera galdetzen,

432
00:32:58,390 --> 00:33:01,260
"Orain deitzen badu funtzio bat idatzi nahi dugu

433
00:33:01,260 --> 00:33:04,930
int balio boolearra prototipo bat dauka. "

434
00:33:04,930 --> 00:33:08,340
Ez gara boolearra int balio badu.

435
00:33:08,340 --> 00:33:15,110
Gure prototipoa da itxura

436
00:33:15,110 --> 00:33:22,380
boolearra badu (int balio.

437
00:33:22,380 --> 00:33:24,490
Eta gero ere ari gara pasatzen zuhaitz

438
00:33:24,490 --> 00:33:28,870
dela egiaztatzeko behar ditu balio duten ala ez ikusteko.

439
00:33:28,870 --> 00:33:38,290
Beraz, nodo * zuhaitz). Ongi da.

440
00:33:38,290 --> 00:33:44,440
Eta, ondoren, antzeko zerbait deitu ahal izango dugu,

441
00:33:44,440 --> 00:33:46,090
agian printf edo zerbait nahi dugu.

442
00:33:46,090 --> 00:33:51,040
Dauka 6, gure root.

443
00:33:51,040 --> 00:33:54,300
Hori bat, edo egia itzuli behar,

444
00:33:54,300 --> 00:33:59,390
badu, berriz, 5 root false itzuli behar du.

445
00:33:59,390 --> 00:34:02,690
Beraz, hartu bigarren hau ezartzeko.

446
00:34:02,690 --> 00:34:06,780
Egin dezakezu bai iteratively edo errekurtsiboki.

447
00:34:06,780 --> 00:34:09,739
Ezarri dugu gauzak modu buruzko gauza polita dela

448
00:34:09,739 --> 00:34:12,300
bera erabaki gure recursive konponbidea askoz errazagoa

449
00:34:12,300 --> 00:34:14,719
modu global-aldakorra baino egin.

450
00:34:14,719 --> 00:34:19,750
Besterik ez dugu int balio duelako, eta gero behera errekurtsibitatean subtrees inola ere ez dugu.

451
00:34:19,750 --> 00:34:24,130
Bereizi helper funtzioa Gurekin subtrees recurses izan nahi dugu.

452
00:34:24,130 --> 00:34:29,610
Baina Nik geroztik aldatu zuhaitz argumentu gisa hartu du,

453
00:34:29,610 --> 00:34:32,760
duten beti behar izan da, lehenik eta behin,

454
00:34:32,760 --> 00:34:35,710
gaur egun recurse dezakegu erraz.

455
00:34:35,710 --> 00:34:38,960
Beraz, joan-etorriko edo recursive, bai joan baino gehiago dugu,

456
00:34:38,960 --> 00:34:46,139
baina recursive amaierak ikusten dugu nahiko erraza sortu.

457
00:34:59,140 --> 00:35:02,480
Ongi da. Does Edozeinek zerbait lan egin ahal izango dugu?

458
00:35:02,480 --> 00:35:12,000
>> [Student] dut bat etorriko konponbidea. >> All right, joan-etorriko.

459
00:35:12,000 --> 00:35:16,030
Ongi da, hau itxura ona.

460
00:35:16,030 --> 00:35:18,920
Beraz, nahi gurekin oinez bidez?

461
00:35:18,920 --> 00:35:25,780
[Student] Sure. Beraz, temp aldagai bat ezarri dut zuhaitza lehen nodo lortzeko.

462
00:35:25,780 --> 00:35:28,330
Eta gero temp ez, berriz, berdintasuna null bidez besterik ez dut looped

463
00:35:28,330 --> 00:35:31,700
beraz, berriz oraindik zuhaitza, I guess.

464
00:35:31,700 --> 00:35:35,710
Eta balioa balioa berdina bada temp hori seinalatuz,

465
00:35:35,710 --> 00:35:37,640
ondoren balio hori itzultzen.

466
00:35:37,640 --> 00:35:40,210
Bestela, eskuin aldean edo ezker aldean bada egiaztatzen.

467
00:35:40,210 --> 00:35:43,400
Al duzu inoiz bada, egoera bat non zuhaitz gehiago ez da,

468
00:35:43,400 --> 00:35:47,330
ondoren itzultzen du - begizta da irteera eta false itzultzen du.

469
00:35:47,330 --> 00:35:52,190
[Bowden] Larreina. Beraz, badirudi ona.

470
00:35:52,190 --> 00:35:58,470
Edonork ezer iruzkinak edozein?

471
00:35:58,470 --> 00:36:02,400
Ez dut zuzentasuna iruzkin guztiak.

472
00:36:02,400 --> 00:36:11,020
Gauza bat egin ahal izango dugu, hau da lasaia.

473
00:36:11,020 --> 00:36:21,660
Oh, little longish bat joan da.

474
00:36:21,660 --> 00:36:33,460
Dela konpondu dut. Ongi da.

475
00:36:33,460 --> 00:36:37,150
>> Pertsona orok lanak nola hirutarra adibidez gogoratu behar da.

476
00:36:37,150 --> 00:36:38,610
Han behin betiko iraganean galdetegiak

477
00:36:38,610 --> 00:36:41,170
ematen dizu, hirutarra adibidez operadore funtzio bat,

478
00:36:41,170 --> 00:36:45,750
eta esan, hau da, itzuli, egin erabiltzen ez duen zerbait, hirutarra adibidez.

479
00:36:45,750 --> 00:36:49,140
, Beraz, hau kasu oso ohikoa da pentsatzea, hirutarra adibidez erabili nahi nuke,

480
00:36:49,140 --> 00:36:54,610
non, baldintza batzuk ezarri aldagai bat, zerbait

481
00:36:54,610 --> 00:36:58,580
bestela, beste zerbait ezarri aldagaia bera.

482
00:36:58,580 --> 00:37:03,390
Zerbait maiz gauza sort honetan sartu daiteke eraldatu

483
00:37:03,390 --> 00:37:14,420
non ezarri aldagaia - edo, eta bai, egia da hau? Ondoren, hau, bestela.

484
00:37:14,420 --> 00:37:18,550
[Student] lehenengoa da egia, ezta?

485
00:37:18,550 --> 00:37:25,570
[Bowden] Bai. Irakurri dut beti, hau da, aldi baterako balio temp balioa baino handiagoa berdin,

486
00:37:25,570 --> 00:37:30,680
gero, bestela hau. Galdera bat eskatuz.

487
00:37:30,680 --> 00:37:35,200
Da handiagoa? Ondoren, lehenengo gauza egin. Bestela, bigarren gauza egin.

488
00:37:35,200 --> 00:37:41,670
Ia beti I - colon, I just - nire buruan, irakurri bestela.

489
00:37:41,670 --> 00:37:47,180
>> Does Edozeinek recursive konponbide bat?

490
00:37:47,180 --> 00:37:49,670
Ongi da. Hau dugu dagoeneko handia izan da,

491
00:37:49,670 --> 00:37:53,990
baina hobeto ere egin dugu.

492
00:37:53,990 --> 00:37:58,720
Pretty askoz berean ideia zehatza.

493
00:37:58,720 --> 00:38:03,060
Besterik ez da, bai, ez azaldu nahi al duzu?

494
00:38:03,060 --> 00:38:08,340
[Student] Sure. Beraz, ziurtatu zuhaitza ez dago null lehen egiten ari gara,

495
00:38:08,340 --> 00:38:13,380
Zuhaitzaren null gero false itzuli dugu aurkitu ez delako delako joan.

496
00:38:13,380 --> 00:38:19,200
Eta badago oraindik ere zuhaitz bat, sartu dugu lehen egiaztatu dugu balioa uneko nodoaren bada.

497
00:38:19,200 --> 00:38:23,740
Itzuli egia bada, eta ez bada recurse ezkerrera edo eskuinera.

498
00:38:23,740 --> 00:38:25,970
Soinu egokia eta horrela, ez? >> Mm-hmm. (Hitzarmena)

499
00:38:25,970 --> 00:38:33,880
Beraz, hau da, ia - egituraz etorriko konponbidea oso antzekoa da.

500
00:38:33,880 --> 00:38:38,200
Besterik ez da ordez errekurtsibitatean, berriz, begizta bat izan genuen.

501
00:38:38,200 --> 00:38:40,840
Eta oinarri kasuan hemen non zuhaitz ez berdinak null

502
00:38:40,840 --> 00:38:44,850
baldintza pean hautsi dugu, berriz, loop zen.

503
00:38:44,850 --> 00:38:50,200
Oso antzekoak dira. Baina urrats bat gehiago hartu dugu.

504
00:38:50,200 --> 00:38:54,190
Orain, gauza bera egiten dugu.

505
00:38:54,190 --> 00:38:57,680
Iragarki bi lerro hauek gauza bera itzultzen ari gara,

506
00:38:57,680 --> 00:39:00,220
izan ezik argumentu bat desberdina da.

507
00:39:00,220 --> 00:39:07,950
Beraz, hirutarra adibidez batean goaz.

508
00:39:07,950 --> 00:39:13,790
Aukera zerbait hit dut, eta sinbolo bat egin du. Ongi da.

509
00:39:13,790 --> 00:39:21,720
Beraz itzuli dugu hori.

510
00:39:21,720 --> 00:39:28,030
Hau da, lerro bat baino gehiago izan lortzean, bai, da handitutako.

511
00:39:28,030 --> 00:39:31,060
Normalean, gauza bat estilistiko gisa, ez dut uste jende askok

512
00:39:31,060 --> 00:39:38,640
arrow ondoren espazio bat jarri, baina Oraindik koherentea izanez gero, isuna da asmatzen dut.

513
00:39:38,640 --> 00:39:44,320
Balioa zuhaitz-balioa baino txikiagoa bada, zuhaitz-ezkerrean recurse nahi dugu,

514
00:39:44,320 --> 00:39:53,890
bestela, zuhaitz eskubidea recurse nahi dugu.

515
00:39:53,890 --> 00:39:58,610
Beraz, urrats bat izan zen itxura hau txikiagoa eginez.

516
00:39:58,610 --> 00:40:02,660
Urratsera itxura hau txikiagoa eginez bi -

517
00:40:02,660 --> 00:40:09,150
hau bereizteko ahal izango dugu lerro bat baino gehiago.

518
00:40:09,150 --> 00:40:16,500
Ongi da. Txikiagoa itxura egiteko bi urratsa da hemen,

519
00:40:16,500 --> 00:40:25,860
beraz, itzulitako balioa zuhaitz balio berdinak, edo edozein dela ere badu.

520
00:40:25,860 --> 00:40:28,340
>> Garrantzitsuena bat da.

521
00:40:28,340 --> 00:40:30,860
Ez nago ziur esan zuen esplizituki klase bada,

522
00:40:30,860 --> 00:40:34,740
baina zirkuitu-laburrik eragin ebaluazioa.

523
00:40:34,740 --> 00:40:41,060
Hemen ideia balioa == zuhaitz balio.

524
00:40:41,060 --> 00:40:49,960
Hori egia bada, orduan hau da egia, eta nahi dugu 'edo' edozein da hemen.

525
00:40:49,960 --> 00:40:52,520
Beraz, are gehiago, edozein dela ere hemen da pentsatu gabe,

526
00:40:52,520 --> 00:40:55,070
zer da adierazpen osoa itzuli egingo da?

527
00:40:55,070 --> 00:40:59,430
[Student] True? >> Bai, ezer egia delako,

528
00:40:59,430 --> 00:41:04,990
gauza or'd or'd - edo egia da derrigorrez egia da.

529
00:41:04,990 --> 00:41:08,150
Beraz, ahalik eta azkarren bueltan balioa = zuhaitz balioa ikusten dugun bezala,

530
00:41:08,150 --> 00:41:10,140
ari gara egia itzuli.

531
00:41:10,140 --> 00:41:15,710
Ere ez recurse joan lerroa gehiago dauka.

532
00:41:15,710 --> 00:41:20,980
Urrats bat gehiago hartu ahal izango dugu.

533
00:41:20,980 --> 00:41:29,490
Zuhaitz Return null ez berdinak, eta hori guztia.

534
00:41:29,490 --> 00:41:32,650
Funtzio bat-line egin.

535
00:41:32,650 --> 00:41:36,790
Zirkuitu-laburrik eragin ebaluazio hori ere adibide bat.

536
00:41:36,790 --> 00:41:40,680
Baina orain ideia bera da

537
00:41:40,680 --> 00:41:47,320
ordez, beraz, ez da berdina null ez bada zuhaitz - edo, eta bai,

538
00:41:47,320 --> 00:41:49,580
, zuhaitz berdinak null ez bada, kasuan txarra da,

539
00:41:49,580 --> 00:41:54,790
zuhaitz berdinen null bada eta, ondoren, lehen baldintza da faltsua izango da.

540
00:41:54,790 --> 00:42:00,550
Beraz, faltsuak ezer anded zer izango da?

541
00:42:00,550 --> 00:42:04,640
[Student] False. >> Bai. Zirkuitu-laburrik eragin ebaluazio beste erdia,

542
00:42:04,640 --> 00:42:10,710
non zuhaitz ez berdinak null ez bada, orduan ez du ari gara, nahiz eta joan egingo

543
00:42:10,710 --> 00:42:14,930
edo, zuhaitz berdinak null ez badu, orduan ez du ari gara balioa == zuhaitz balio du.

544
00:42:14,930 --> 00:42:17,010
Besterik ez gara berehala itzultzeko faltsua.

545
00:42:17,010 --> 00:42:20,970
Zein da, bada geroztik ez da zirkuitu-laburrik eragin ebaluatzeko,

546
00:42:20,970 --> 00:42:25,860
gero, zuhaitz berdinak null ez bada, bigarren baldintza hori seg errua,

547
00:42:25,860 --> 00:42:32,510
zuhaitz-> balioa null dereferencing delako.

548
00:42:32,510 --> 00:42:40,490
Beraz, hori. Hau egin ahal izango filmea behin baino gehiago.

549
00:42:40,490 --> 00:42:44,840
Hau oso ohikoa da gauza bat da, gainera, ez da honekin lerro bat egiteko,

550
00:42:44,840 --> 00:42:49,000
baina baldintza gauza komun bat da, agian ez da hemen,

551
00:42:49,000 --> 00:42:59,380
baina (zuhaitz! = NULL, eta zuhaitz-> balioa == balioa), ez bada edozein izanda ere.

552
00:42:59,380 --> 00:43:01,560
Hau oso ohikoa den egoera bat da, non ez izatearen ordez

553
00:43:01,560 --> 00:43:06,770
apurtu bi IFS, non bezala, zuhaitz null da?

554
00:43:06,770 --> 00:43:11,780
Ados, ez da nulua, eta, beraz, gaur egun zuhaitz balio balio berdina da? Do hau.

555
00:43:11,780 --> 00:43:17,300
Horren ordez, egoera honetan, hau ez da inoiz errua seg

556
00:43:17,300 --> 00:43:21,220
apurtu delako honetan gertatzen null izan nahi izanez gero.

557
00:43:21,220 --> 00:43:24,000
Beno, uste dut zure zuhaitz erakuslea guztiz baliogabea bada, oraindik daiteke errua seg

558
00:43:24,000 --> 00:43:26,620
baina ezin du errua seg zuhaitz null bada.

559
00:43:26,620 --> 00:43:32,900
Ziren null bada, hausteko litzateke zara inoiz erakuslea dereferenced aurretik lehenik eta behin.

560
00:43:32,900 --> 00:43:35,000
[Student] alferrak ebaluazioa izenekoa da?

561
00:43:35,000 --> 00:43:40,770
>> [Bowden] Lazy ebaluazio beste gauza bat da.

562
00:43:40,770 --> 00:43:49,880
Lazy ebaluazioa da, gehiago balio bat eskatu bezala,

563
00:43:49,880 --> 00:43:54,270
balioa, mota horretako kalkulatzeko eskatu duzu, baina ez duzu behar berehala.

564
00:43:54,270 --> 00:43:59,040
Beraz, benetan behar duzun arte, ez da ebaluatu.

565
00:43:59,040 --> 00:44:03,920
Hau ez da zehazki gauza bera, baina Huffman pset

566
00:44:03,920 --> 00:44:06,520
dugun "lazily" idatzi dio.

567
00:44:06,520 --> 00:44:08,670
Arrazoia egiten dugu ari gara benetan delako idazteko Bufferreratzen

568
00:44:08,670 --> 00:44:11,820
ez dugu nahi banakako bit idazteko aldi berean,

569
00:44:11,820 --> 00:44:15,450
edo aldi berean banakako bytes, ordez nahi dugu bytes zatia bat lortzeko.

570
00:44:15,450 --> 00:44:19,270
Ondoren dugu, byte zatia behin, gero idatzi dugu.

571
00:44:19,270 --> 00:44:22,640
Nahiz eta galdetzen idatzi eta fwrite eta gauza sort fread gauza bera egin zuen.

572
00:44:22,640 --> 00:44:26,260
Zure irakurtzen eta idazten du bufferreko dute.

573
00:44:26,260 --> 00:44:31,610
Nahiz eta galdetu berehala idatzi, ziurrenik ez.

574
00:44:31,610 --> 00:44:34,540
Eta ezin duzu ziurtatu gauza idatzi egingo da

575
00:44:34,540 --> 00:44:37,540
deitu hfclose arte edo dena delakoa da,

576
00:44:37,540 --> 00:44:39,620
eta gero dio, ados, nire file dut itxi,

577
00:44:39,620 --> 00:44:43,450
horrek esan nahi du hobe dut idazten dena ez dut idatzi gabe.

578
00:44:43,450 --> 00:44:45,770
Ez du behar dena idazteko

579
00:44:45,770 --> 00:44:49,010
ari zaren fitxategia arte itxi, eta, ondoren, behar da.

580
00:44:49,010 --> 00:44:56,220
Beraz, besterik gabe, zer alferrak - gertatu arte itxaroten da.

581
00:44:56,220 --> 00:44:59,990
- Hartu 51 eta xehetasun gehiago sartu dituzu joan

582
00:44:59,990 --> 00:45:05,470
51 OCaml eta dena, dena delako errekurtsio da.

583
00:45:05,470 --> 00:45:08,890
Ez dago irtenbideak ez dira etorriko, batez ere.

584
00:45:08,890 --> 00:45:11,550
Dena errekurtsio, eta ebaluazio alferrak

585
00:45:11,550 --> 00:45:14,790
garrantzitsua da, egoera asko gertatzen

586
00:45:14,790 --> 00:45:19,920
non, ez baduzu lazily ebaluatzeko, zela esan nahi

587
00:45:19,920 --> 00:45:24,760
Adibidez errekak, infinituki luzea da.

588
00:45:24,760 --> 00:45:30,990
Teorian, natural gisa 1-2-3-4-5-6-7 korronte zenbakiak dezakezu uste,

589
00:45:30,990 --> 00:45:33,090
Beraz lazily ebaluatu gauzak fina dira.

590
00:45:33,090 --> 00:45:37,210
Diot hamargarren kopurua nahi dut, eta, ondoren, ebaluatzeko sortu dut hamargarren kopurua.

591
00:45:37,210 --> 00:45:40,300
Nahi dut hundredth kopurua bada, orduan ebaluatzeko sortu dut kopurua hundredth.

592
00:45:40,300 --> 00:45:46,290
, Ebaluazio-alferrak gabe, eta gero zenbaki guztiak ebaluatzeko berehala saiatuko da.

593
00:45:46,290 --> 00:45:50,000
Infinituki askotan zenbakiak ari zara, ebaluatzen, eta hori ez da posible.

594
00:45:50,000 --> 00:45:52,080
Beraz, egoera asko daude non alferrak ebaluazioa

595
00:45:52,080 --> 00:45:57,840
besterik ez da gauzak lan egiteko ezinbestekoa da.

596
00:45:57,840 --> 00:46:05,260
>> Orain txertatze idatzi nahi dugu, non txertatze izango da

597
00:46:05,260 --> 00:46:08,430
era berean, haren definizioa aldatzen ari da.

598
00:46:08,430 --> 00:46:10,470
Beraz, oraintxe txertatze-boolearra (int balioa).

599
00:46:10,470 --> 00:46:23,850
Aldatu boolearra txertatze (int balioa, nodoak * zuhaitz) goaz.

600
00:46:23,850 --> 00:46:29,120
Benetan ari gara berriro aldatu pixka bat, ikus zergatik dugu.

601
00:46:29,120 --> 00:46:32,210
Eta let mugitu build_node, demontre,

602
00:46:32,210 --> 00:46:36,730
goian sartu ez dugu, beraz, funtzio-prototipo bat idazteko.

603
00:46:36,730 --> 00:46:42,450
Zein aholku bat zarela erabiltzen ari build_node txertatze.

604
00:46:42,450 --> 00:46:49,590
Ongi da. Hartu minutu bat dela.

605
00:46:49,590 --> 00:46:52,130
Berrikusketaren gorde dut uste dut, nahi duzun hori zabaltzen bada,

606
00:46:52,130 --> 00:47:00,240
edo, gutxienez, gaur egun egin nuen.

607
00:47:00,240 --> 00:47:04,190
Apur bat break txertatze logika pentsatu nahi dut,

608
00:47:04,190 --> 00:47:08,750
ezin baduzu pentsatu.

609
00:47:08,750 --> 00:47:12,860
Funtsean, bakarrik izango duzu inoiz izango hostoak tartekatuz.

610
00:47:12,860 --> 00:47:18,640
Like txertatzeko I 1 bada, ondoren, ezinbestean dut sartzearen 1 -

611
00:47:18,640 --> 00:47:21,820
Beltza aldatu dut - I'll dira 1 txertatu hemen.

612
00:47:21,820 --> 00:47:28,070
Edo txertatu I 4 bada, behar bezala 4 hemen baino gehiago nahi dut.

613
00:47:28,070 --> 00:47:32,180
Ez dio axola zer egin nahi duzu, beraz, hosto bat txertatu duzu.

614
00:47:32,180 --> 00:47:36,130
Guztiak egin behar duzun da, batetik bestera joateko behera zuhaitz nodo iritsi arte

615
00:47:36,130 --> 00:47:40,890
nodoaren guraso, berriak nodo guraso izan behar du,

616
00:47:40,890 --> 00:47:44,560
eta, ondoren, bere ezkerrera edo eskuinera erakuslea aldatu, edo ez arabera

617
00:47:44,560 --> 00:47:47,060
baino handiagoa edo uneko nodo baino txikiagoa da.

618
00:47:47,060 --> 00:47:51,180
Aldatu erakuslea, zure nodo batetara.

619
00:47:51,180 --> 00:48:05,490
Beraz, batetik bestera joateko zuhaitz, hosto-puntua nodo berria.

620
00:48:05,490 --> 00:48:09,810
Era berean, zergatik duten egoera mota debekatzen aurretik pentsatzen,

621
00:48:09,810 --> 00:48:17,990
zuhaitz bitarrak non eraiki dut, non zuzena izan zen

622
00:48:17,990 --> 00:48:19,920
nodo bakar bat baldin bada bakarrik begiratu,

623
00:48:19,920 --> 00:48:24,830
baina 9 7 ezkerreko iterated behera modu guztiak.

624
00:48:24,830 --> 00:48:29,770
Egoera honetan ezinezkoa da, beraz, geroztik

625
00:48:29,770 --> 00:48:32,530
pentsatu 9 edo zerbait txertatzea; oso nodo lehen,

626
00:48:32,530 --> 00:48:35,350
7 ikusteko eta besterik ez dut eskuinera joango naiz.

627
00:48:35,350 --> 00:48:38,490
Beraz, zer egin dut axola ez banago, hosto bat joan txertatu,

628
00:48:38,490 --> 00:48:40,790
eta hosto bat algoritmoa egokia erabiliz,

629
00:48:40,790 --> 00:48:43,130
ezinezkoa 9 me sartu 7 ezkerreko

630
00:48:43,130 --> 00:48:48,250
bezain laster hit I 7 eskuinera joan naiz dudalako joan.

631
00:48:59,740 --> 00:49:02,070
Does Edozeinek hasteko zerbait?

632
00:49:02,070 --> 00:49:05,480
[Student] egiten dut. >> Sure.

633
00:49:05,480 --> 00:49:09,200
[Ikaslea, ulertezina]

634
00:49:09,200 --> 00:49:14,390
[Beste ikaslea, ulertezina]

635
00:49:14,390 --> 00:49:18,330
[Bowden] da estimatzen. Ongi da. Azaldu nahi duzu?

636
00:49:18,330 --> 00:49:20,690
>> [Student] geroztik dugun txertatu badakigu

637
00:49:20,690 --> 00:49:24,060
zuhaitzaren amaieran nodo berriak,

638
00:49:24,060 --> 00:49:28,070
Looped Zuhaitz bidez iteratively

639
00:49:28,070 --> 00:49:31,360
nodo bat dela adierazi null dut lortu arte.

640
00:49:31,360 --> 00:49:34,220
Eta gero, erabaki nuen, bai eskuineko aldean edo ezkerraldean ipini

641
00:49:34,220 --> 00:49:37,420
aldagai hau erabiliz; esan zidan non jarri.

642
00:49:37,420 --> 00:49:41,850
Eta gero, funtsean, egin dut azken

643
00:49:41,850 --> 00:49:47,520
hori temp nodo duten nodo berriak sortzea zen,

644
00:49:47,520 --> 00:49:50,770
edo ezkerreko aldean edo eskuineko aldean, zer balioa arabera.

645
00:49:50,770 --> 00:49:56,530
Azkenik, nodoa bere egiaztatze balioa balioa ezarri dut.

646
00:49:56,530 --> 00:49:59,550
[Bowden] Ongi da, eta, beraz, gai bat ikusten dut hemen.

647
00:49:59,550 --> 00:50:02,050
Bidean% 95 bezalakoa da.

648
00:50:02,050 --> 00:50:07,550
Bat gai ikusten dut, bai, inork ez ikusteko arazo bat?

649
00:50:07,550 --> 00:50:18,400
Zer da inguruabar pean apurtzen dute Begizta?

650
00:50:18,400 --> 00:50:22,100
[Student] temp null bada? >> Bai. Beraz, nola apurtu Begizta temp null bada.

651
00:50:22,100 --> 00:50:30,220
Baina, zer egin behar dut hemen?

652
00:50:30,220 --> 00:50:35,410
I dereference temp, den ezinbestean null.

653
00:50:35,410 --> 00:50:39,840
Beraz, beste gauza egin behar duzun ez da bakarrik gorde pista temp null arte,

654
00:50:39,840 --> 00:50:45,590
segimendua egiteko, gurasoaren uneoro nahi duzun.

655
00:50:45,590 --> 00:50:52,190
Ere nahi dugu nodo * guraso, null at mantendu ahal izango dugu lehen uste dut.

656
00:50:52,190 --> 00:50:55,480
Portaera bitxi hori zuhaitzaren erro

657
00:50:55,480 --> 00:50:59,210
baina hori lortu dugu.

658
00:50:59,210 --> 00:51:03,950
Balioa edozein dela ere baino handiagoa bada, orduan aldi baterako = temp eskubidea.

659
00:51:03,950 --> 00:51:07,910
Baina egin aurretik, parent = temp.

660
00:51:07,910 --> 00:51:14,500
Edo gurasoak dira beti berdinak temp? Kasua dela?

661
00:51:14,500 --> 00:51:19,560
Temp null ez bada, ondoren, behera, eta ez du axola zer noa,

662
00:51:19,560 --> 00:51:24,030
nodo temp guraso da.

663
00:51:24,030 --> 00:51:27,500
Beraz, gurasoen temp izango du, eta, ondoren, temp mugitzen I behera.

664
00:51:27,500 --> 00:51:32,410
Orain temp null da, baina guraso gauza dela null guraso puntu.

665
00:51:32,410 --> 00:51:39,110
Beraz, behera hemen, ez dut nahi ezartzeko eskubidea funtzioak 1 itzultzen du.

666
00:51:39,110 --> 00:51:41,300
Beraz, eskubidea joan nintzen, eta, beraz, eskuineko = 1 bada,

667
00:51:41,300 --> 00:51:45,130
eta uste dut egin nahi duzun

668
00:51:45,130 --> 00:51:48,530
ezkerrera mugituko zara, gero, eskuinera eta 0 berdinak ezarri nahi duzu.

669
00:51:48,530 --> 00:51:55,950
Edo, bestela, inoiz eskubidea mugitzeko.

670
00:51:55,950 --> 00:51:58,590
Beraz, eskuineko = 0. = Eskuineko 1 bada,

671
00:51:58,590 --> 00:52:04,260
guraso eskuineko erakuslea newnode egin nahi dugu,

672
00:52:04,260 --> 00:52:08,520
guraso ezkerreko erakuslea newnode beste egin nahi dugu.

673
00:52:08,520 --> 00:52:16,850
Horri buruzko galderak?

674
00:52:16,850 --> 00:52:24,880
Ongi da. Modua dugu, beraz, hau da, ondo, egia esan, lan hau egiteko ordez,

675
00:52:24,880 --> 00:52:29,630
erdi espero dugu build_node erabili behar duzu.

676
00:52:29,630 --> 00:52:40,450
Eta gero newnode berdinen null bada, faltsua itzuliko.

677
00:52:40,450 --> 00:52:44,170
Hori da hori. Orain, hau da, zer egin ahal izango duzu espero dugu.

678
00:52:44,170 --> 00:52:47,690
>> Hau da, langileek irtenbideak egin.

679
00:52:47,690 --> 00:52:52,360
Ados ez dut horri buruz going "eskubidea" modu gisa

680
00:52:52,360 --> 00:52:57,820
baina hori guztiz fina eta lan egingo du.

681
00:52:57,820 --> 00:53:02,840
Gauza bat gaur egun, apur bat arraro eskubidea da

682
00:53:02,840 --> 00:53:08,310
zuhaitza hasten bada null, null zuhaitz gainditu dugu.

683
00:53:08,310 --> 00:53:12,650
Araberakoa nola null zuhaitz batean pasatzen portaera definitzeko uste dut.

684
00:53:12,650 --> 00:53:15,490
Uste bada pasatzen zuhaitz bat null nuke,

685
00:53:15,490 --> 00:53:17,520
ondoren zuhaitz bat null balioa txertatu

686
00:53:17,520 --> 00:53:23,030
return zuhaitz bat non soilik balioa nodo bakarra dela.

687
00:53:23,030 --> 00:53:25,830
Do duten pertsonen ados? Dezakezu, nahi izanez gero,

688
00:53:25,830 --> 00:53:28,050
, zuhaitz bat null pasatzen bada

689
00:53:28,050 --> 00:53:31,320
eta nahi duzun balio bat sartu da, itzultzeko faltsua.

690
00:53:31,320 --> 00:53:33,830
Da sortu nahi duzun definitzeko.

691
00:53:33,830 --> 00:53:38,320
Lehenik eta behin, eta esan nion, orduan egin

692
00:53:38,320 --> 00:53:40,720
ondo, arazoak egiten ari zaren joan, zeren

693
00:53:40,720 --> 00:53:44,090
errazagoa izango litzateke gauza erakuslea global bat izan genuen,

694
00:53:44,090 --> 00:53:48,570
baina ez dugu, eta, beraz, zuhaitz null bada, ez dago ezer horri buruz egin ahal izango dugu.

695
00:53:48,570 --> 00:53:50,960
Besterik ez dugu itzultzeko faltsua.

696
00:53:50,960 --> 00:53:52,840
Beraz txertatze aldatu dut.

697
00:53:52,840 --> 00:53:56,540
Izan teknikoki dugu aldatzeko eskubide hori hemen,

698
00:53:56,540 --> 00:53:58,400
gauzak nola baino gehiago errepikatzean,

699
00:53:58,400 --> 00:54:04,530
baina txertatze aldatu ** zuhaitz nodo bat hartu dut.

700
00:54:04,530 --> 00:54:07,510
Bikoitza erakusleak.

701
00:54:07,510 --> 00:54:09,710
Zer esan nahi du horrek?

702
00:54:09,710 --> 00:54:12,330
Nodo erakusleak aurre ordez,

703
00:54:12,330 --> 00:54:16,690
gauza dira manipulatzeko noa erakuslea da.

704
00:54:16,690 --> 00:54:18,790
Erakuslea hau manipulatzeko noa.

705
00:54:18,790 --> 00:54:21,770
Dira manipulatzeko erakusleak zuzenean noa.

706
00:54:21,770 --> 00:54:25,760
Honek zentzua du, behera pentsatu geroztik

707
00:54:25,760 --> 00:54:33,340
ondo, oraintxe bertan puntu hau null.

708
00:54:33,340 --> 00:54:38,130
Zer egin nahi dut manipulatzeko erakuslea hau ez null seinalatu.

709
00:54:38,130 --> 00:54:40,970
My new nodo seinalatu nahi dut.

710
00:54:40,970 --> 00:54:44,870
Dut pista erakusleak nire erakusleak,

711
00:54:44,870 --> 00:54:47,840
orduan ez behar dut segimendua egiteko, guraso erakuslea.

712
00:54:47,840 --> 00:54:52,640
Bakarrik gorde ahal izango dut pista erakuslea da null bada seinalatuz,

713
00:54:52,640 --> 00:54:54,580
eta erakuslea apuntatzen bada null

714
00:54:54,580 --> 00:54:57,370
aldatu nahi dut nodo seinalatu.

715
00:54:57,370 --> 00:55:00,070
Eta hori aldatu ahal izango dut Erakuslea erakuslea baita.

716
00:55:00,070 --> 00:55:02,040
Eskubide hori gaur egun.

717
00:55:02,040 --> 00:55:05,470
Benetan egin dezakezu errekurtsiboki nahiko erraz.

718
00:55:05,470 --> 00:55:08,080
Ez hori egin nahi dugu?

719
00:55:08,080 --> 00:55:10,980
Bai, egiten dugu.

720
00:55:10,980 --> 00:55:16,790
>> Ikus dezagun Errekurtsiboki.

721
00:55:16,790 --> 00:55:24,070
Lehenik eta behin, gure base kasuan izango da?

722
00:55:24,070 --> 00:55:29,140
Ia beti gure oinarria kasuan, baina, benetan, hau delikatua mota da.

723
00:55:29,140 --> 00:55:34,370
Lehen gauzak lehen, bada (zuhaitz == NULL)

724
00:55:34,370 --> 00:55:37,550
Besterik ari gara false itzuli uste dut.

725
00:55:37,550 --> 00:55:40,460
Hau da zure zuhaitz null izatetik ezberdina.

726
00:55:40,460 --> 00:55:44,510
Hau zure root erakuslea null izateaz erakuslea da

727
00:55:44,510 --> 00:55:48,360
Horrek esan nahi du zure root erakuslea hori ez da existitzen.

728
00:55:48,360 --> 00:55:52,390
Beraz, behera hemen, ez badut

729
00:55:52,390 --> 00:55:55,760
nodo * - dezagun berrerabiltzea hau.

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

731
00:55:58,960 --> 00:56:00,730
eta, ondoren, txertatze deitu antzeko zerbait egiten dut,

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

733
00:56:04,540 --> 00:56:06,560
Beraz, eta root root nodo *

734
00:56:06,560 --> 00:56:11,170
ondoren eta root nodo ** bat izango da.

735
00:56:11,170 --> 00:56:15,120
Baliozkoa da. Kasu honetan, zuhaitz, hemen,

736
00:56:15,120 --> 00:56:20,120
zuhaitz ez da null - edo txertatze-.

737
00:56:20,120 --> 00:56:24,630
Hemen. Zuhaitz ez da null; * zuhaitz null, hau da, isuna

738
00:56:24,630 --> 00:56:26,680
* zuhaitz null bada, orduan delako manipulatu ahal izango dut

739
00:56:26,680 --> 00:56:29,210
orain zer puntutaraino nahi dut seinalatu.

740
00:56:29,210 --> 00:56:34,750
Baina zuhaitz null bada, horrek esan nahi du, izan zen besterik ez dut hemen, eta hau esan null.

741
00:56:34,750 --> 00:56:42,710
Horrek ez du zentzurik. Ezin dut ezer egin duten.

742
00:56:42,710 --> 00:56:45,540
Zuhaitz null bada, faltsua itzuliko.

743
00:56:45,540 --> 00:56:48,220
Beraz, funtsean, esan zuen dagoeneko dut zer da gure benetako oinarria kasuan.

744
00:56:48,220 --> 00:56:50,580
Eta zer da hori?

745
00:56:50,580 --> 00:56:55,030
[Ikaslea, ulertezina]

746
00:56:55,030 --> 00:57:00,000
[Bowden] Bai. Beraz, (* zuhaitz == NULL).

747
00:57:00,000 --> 00:57:04,520
Kasuan erlazionatzen hemen

748
00:57:04,520 --> 00:57:09,640
non nire gorria erakuslea erakusleak bada dut arreta,

749
00:57:09,640 --> 00:57:12,960
erakuslea hau bezalako bideratuta dut, gaur egun dut erakuslea honen ardatz hartzen.

750
00:57:12,960 --> 00:57:15,150
Orain erakuslea honen ardatz hartzen dut.

751
00:57:15,150 --> 00:57:18,160
Beraz, nire erakuslea gorria, hau da, nire nodo **

752
00:57:18,160 --> 00:57:22,880
beti * izanez gero, nire gorria erakuslea da, inoiz null,

753
00:57:22,880 --> 00:57:28,470
horrek esan nahi du kasu, non erakuslea puntu bideratua dut I am

754
00:57:28,470 --> 00:57:32,530
erakuslea hosto bat da.

755
00:57:32,530 --> 00:57:41,090
Erakuslea hau aldatu nahi dut nire nodo batetara.

756
00:57:41,090 --> 00:57:45,230
Come back hemen.

757
00:57:45,230 --> 00:57:56,490
Nire newnode nodo * n = build_node (balioa)

758
00:57:56,490 --> 00:58:07,300
ondoren, n, n = NULL bada, faltsua itzuliko.

759
00:58:07,300 --> 00:58:12,600
Bestela, zer erakuslea da gaur egun zuzentzen duen aldatu nahi dugu

760
00:58:12,600 --> 00:58:17,830
Gaur egun, gure eraiki berri den nodo seinalatu.

761
00:58:17,830 --> 00:58:20,280
Benetan egin ahal izango dugu hemen.

762
00:58:20,280 --> 00:58:30,660
N esaten ordez, esan * zuhaitza = * zuhaitz bada.

763
00:58:30,660 --> 00:58:35,450
Pertsona orok ulertzen? Hori erakusleak erakusle aurre,

764
00:58:35,450 --> 00:58:40,750
null erakusleak aldatu ahal izango dugu, gauza horiek seinalatu nahi dugu.

765
00:58:40,750 --> 00:58:42,820
Hori gure base kasu.

766
00:58:42,820 --> 00:58:45,740
>> Orain gure errepikatze, edo gure errekurtsio

767
00:58:45,740 --> 00:58:51,430
egin dugu egiten beste recursions guztiak oso antzekoa izango da.

768
00:58:51,430 --> 00:58:55,830
Balioa txertatu nahi dugu,

769
00:58:55,830 --> 00:58:59,040
eta, gaur egun, hirutarra adibidez berriro erabiltzeko naiz joan, baina gure egoera zein izango da?

770
00:58:59,040 --> 00:59:05,180
Zer da ari gara bilatzen dugu ezkerrera edo eskuinera joan nahi duen ala ez erabakitzeko?

771
00:59:05,180 --> 00:59:07,760
Egin dezagun urrats desberdinetan.

772
00:59:07,760 --> 00:59:18,850
(Balioa <) bada, zer?

773
00:59:18,850 --> 00:59:23,200
[Student] zuhaitza balio?

774
00:59:23,200 --> 00:59:27,490
[Bowden] Beraz, gogoratzen naiz I gaur egun -

775
00:59:27,490 --> 00:59:31,260
[Ikasleak, ulertezina]

776
00:59:31,260 --> 00:59:34,140
[Bowden] Bai, eta, beraz, hementxe, demagun gezi berdeak hori

777
00:59:34,140 --> 00:59:39,050
zer zuhaitz Gaur egun, adibide bat da, erakuslea hau erakuslea da.

778
00:59:39,050 --> 00:59:46,610
Beraz, horrek esan nahi du 3 erakuslea erakuslea naiz.

779
00:59:46,610 --> 00:59:48,800
Dereference birritan sounded good.

780
00:59:48,800 --> 00:59:51,010
Zer I - nola ez egin behar dut?

781
00:59:51,010 --> 00:59:53,210
[Student] Dereference behin, eta, ondoren, egin arrow bide horretatik?

782
00:59:53,210 --> 00:59:58,420
[Bowden] Beraz, - (* zuhaitz) dereference behin,> balio

783
00:59:58,420 --> 01:00:05,960
me naiz I zeharka seinalatuz nodo balioa emateko.

784
01:00:05,960 --> 01:00:11,980
Beraz, ezin dut idatzi tree.value ** nahiago baduzu.

785
01:00:11,980 --> 01:00:18,490
Edo lan egiten du.

786
01:00:18,490 --> 01:00:26,190
Hori horrela bada, orduan balio txertatzeko deitu nahi dut.

787
01:00:26,190 --> 01:00:32,590
Eta zer da nire nodo eguneratzen da ** izango da?

788
01:00:32,590 --> 01:00:39,440
Ezkerrera joan nahi dut, eta, beraz, ** tree.left izango da nire ezker.

789
01:00:39,440 --> 01:00:41,900
Eta gauza erakuslea nahi dut

790
01:00:41,900 --> 01:00:44,930
beraz, ezker eta ondorioz sortu bada null erakuslea da,

791
01:00:44,930 --> 01:00:48,360
Aldatu ahal ditut nire nodo batetara.

792
01:00:48,360 --> 01:00:51,460
>> Eta beste kasua oso antzekoa izan daiteke.

793
01:00:51,460 --> 01:00:55,600
Dezagun benetan nire hirutarra adibidez oraintxe.

794
01:00:55,600 --> 01:01:04,480
Txertatu balioa balioa bada <(** zuhaitz). Balio.

795
01:01:04,480 --> 01:01:11,040
Ondoren, ezkerreko gure ** eguneratu nahi dugu,

796
01:01:11,040 --> 01:01:17,030
bestela, gure eskubidea ** eguneratu nahi dugu.

797
01:01:17,030 --> 01:01:22,540
[Student], hori lortzeko erakuslea erakusleak?

798
01:01:22,540 --> 01:01:30,940
[Bowden] Gogoratu - ** tree.right nodo izar bat da.

799
01:01:30,940 --> 01:01:35,040
[Ikaslea, ulertezina] >> Bai.

800
01:01:35,040 --> 01:01:41,140
** Tree.right erakuslea hau edo antzeko zerbait da.

801
01:01:41,140 --> 01:01:45,140
Erakuslea hartu ahal izateko, ematen dit nahi dudana

802
01:01:45,140 --> 01:01:50,090
guy hori erakuslea.

803
01:01:50,090 --> 01:01:54,260
[Student] Ezin izan baino gehiago gara berriro zergatik bi erakusleak erabiltzen ari gara?

804
01:01:54,260 --> 01:01:58,220
[Bowden] Bai. Beraz, - no, ahal izango duzu eta konponbidea hori baino lehen

805
01:01:58,220 --> 01:02:04,540
bi erakusleak egin gabe egiten modu bat izan zen.

806
01:02:04,540 --> 01:02:08,740
Bi erakusleak erabiltzen ulertzeko gai izan behar duzu,

807
01:02:08,740 --> 01:02:11,660
eta garbiagoa hau irtenbide bat da.

808
01:02:11,660 --> 01:02:16,090
Era berean, konturatu, zer gertatzen den nire zuhaitz bada

809
01:02:16,090 --> 01:02:24,480
zer gertatzen den nire root zen null bada? Zer gertatzen da kasu honetan bada egin behar dut hemen?

810
01:02:24,480 --> 01:02:30,540
Beraz, nodo * root = NULL, sartu & root sartu 4.

811
01:02:30,540 --> 01:02:35,110
Zer da root honen ondoren izango da?

812
01:02:35,110 --> 01:02:37,470
[Ikaslea, ulertezina] >> Bai.

813
01:02:37,470 --> 01:02:41,710
Root balioa 4 izango da.

814
01:02:41,710 --> 01:02:45,510
Root ezker null izango da, root eskubidea null izango da.

815
01:02:45,510 --> 01:02:49,490
Kasu honetan, non ez genuen gainditu root helbidea,

816
01:02:49,490 --> 01:02:52,490
ezin dugu aldatu root.

817
01:02:52,490 --> 01:02:56,020
Kasu honetan, non zuhaitz non root null,

818
01:02:56,020 --> 01:02:58,410
false itzuli izan dugu. Ez dago ezer egin ahal izan genuen.

819
01:02:58,410 --> 01:03:01,520
Nodo bat zuhaitz hutsa ezin dugu sartu.

820
01:03:01,520 --> 01:03:06,810
Baina orain ezin dugu hutsik egin besterik ez dugu zuhaitz bat, zuhaitz bat-nodo batean.

821
01:03:06,810 --> 01:03:13,400
Zein da normalean espero duela ustezko lan.

822
01:03:13,400 --> 01:03:21,610
>> Horrez gain, hau da, baino nabarmen laburragoa

823
01:03:21,610 --> 01:03:26,240
gurasoa ere jarraipena, eta, beraz, behera batetik bestera joateko modu guztiak.

824
01:03:26,240 --> 01:03:30,140
Orain nire guraso izan dut, eta aski izango da nire guraso eskubidea edozein erakuslea.

825
01:03:30,140 --> 01:03:35,640
Horren ordez, egin dugu, hori izanez gero iteratively, begizta bat, berriz, ideia bera izango da litzaidake.

826
01:03:35,640 --> 01:03:38,100
Baina ordez, nire guraso erakuslea aurre egiteko beharrik,

827
01:03:38,100 --> 01:03:40,600
ordez nire oraingo erakuslea gauza izango litzateke

828
01:03:40,600 --> 01:03:43,790
naiz I zuzenean nire nodo batetara aldatzea.

829
01:03:43,790 --> 01:03:46,090
Nik ez dut ezker ala ez seinalatuz aurre egiteko.

830
01:03:46,090 --> 01:03:48,810
Ez daukat eskubidea ala ez seinalatuz aurre egiteko.

831
01:03:48,810 --> 01:04:00,860
Besterik ez da edozein erakuslea hau da, nire nodo batetara ezarri nahi dut joan.

832
01:04:00,860 --> 01:04:05,740
Pertsona orok du ulertzen nola funtzionatzen duen?

833
01:04:05,740 --> 01:04:09,460
Ez bada, zergatik egin nahi dugu modu honetan,

834
01:04:09,460 --> 01:04:14,920
baina, gutxienez, hori irtenbide bat lan?

835
01:04:14,920 --> 01:04:17,110
[Student] Nora egin egia itzuliko gara?

836
01:04:17,110 --> 01:04:21,550
[Bowden] Hori da ziurrenik hemen.

837
01:04:21,550 --> 01:04:26,690
Behar bezala sartu dugu bada, itzultzeko egia.

838
01:04:26,690 --> 01:04:32,010
Bestela, behera hemen edozein izanda ere txertatze itzultzen itzuli nahi dugu.

839
01:04:32,010 --> 01:04:35,950
>> Eta zer da berezia hau recursive funtzioa?

840
01:04:35,950 --> 01:04:43,010
Buztana errekurtsiboa da, eta, beraz, luze optimizazioa batzuk konpilatu dugun bezala,

841
01:04:43,010 --> 01:04:48,060
hori ezagutu egingo du, eta ez du inoiz izango duzu gainezkatzea pila bat lortu honetako

842
01:04:48,060 --> 01:04:53,230
nahiz eta gure zuhaitza 10.000 edo 10 milioi altuera du.

843
01:04:53,230 --> 01:04:55,630
[Ikaslea, ulertezina]

844
01:04:55,630 --> 01:05:00,310
[Bowden] Dash at uste dut edo zer optimizazio maila

845
01:05:00,310 --> 01:05:03,820
da buztana errekurtsio onartu behar da.

846
01:05:03,820 --> 01:05:09,350
Ohartuko da uste dut - GCC eta Clang

847
01:05:09,350 --> 01:05:12,610
beren optimizazio maila esanahi desberdinak ere izan.

848
01:05:12,610 --> 01:05:17,870
DashO 2, buztana errekurtsio konturatu egingo da ziur esan nahi dut.

849
01:05:17,870 --> 01:05:27,880
Baina bat Fibonocci adibidez, edo antzeko zerbait eraikitzeko.

850
01:05:27,880 --> 01:05:30,030
Ez da erraza hau probatzeko, zaila delako eraikitzeko

851
01:05:30,030 --> 01:05:32,600
zuhaitz bitar bat da, oso handia.

852
01:05:32,600 --> 01:05:37,140
Baina bai, DashO 2, hau da, uste dut

853
01:05:37,140 --> 01:05:40,580
DashO 2 konpilatu bada, buztana errekurtsio itxura izango da

854
01:05:40,580 --> 01:05:54,030
eta optimizatzeko out.

855
01:05:54,030 --> 01:05:58,190
Dezagun itzuli diskoa literalki azken gauza behar.

856
01:05:58,190 --> 01:06:04,900
Atzera dezagun inserto hemen

857
01:06:04,900 --> 01:06:07,840
non ideia bera egin behar dugu.

858
01:06:07,840 --> 01:06:14,340
Oraindik ere izango da, ez da oso-osorik kudeatzeko gai izan flaw

859
01:06:14,340 --> 01:06:17,940
erro bera null, edo iragan sarrera null,

860
01:06:17,940 --> 01:06:20,060
baina erakuslea gurasoaren ordez aurre egiteko,

861
01:06:20,060 --> 01:06:27,430
dezagun erakusleak mantentzeko logika bera aplikatzen erakusleak.

862
01:06:27,430 --> 01:06:35,580
Hemen bada gure nodo ** orain mantendu dugu,

863
01:06:35,580 --> 01:06:37,860
eta ez dugu behar segimendua egiteko eskubidea gehiago

864
01:06:37,860 --> 01:06:47,190
baina nodo ** orain = & zuhaitza.

865
01:06:47,190 --> 01:06:54,800
Eta orain, gure, berriz, loop eta * orain ez, berriz, berdintasuna null izango.

866
01:06:54,800 --> 01:07:00,270
Ez behar gehiago gurasoek segimendua egiteko.

867
01:07:00,270 --> 01:07:04,180
Ez behar ezkerreko eta eskuineko pista mantentzeko.

868
01:07:04,180 --> 01:07:10,190
Eta deitu dut temp ari gara, dagoeneko erabiltzen delako temp.

869
01:07:10,190 --> 01:07:17,200
Ongi da. Beraz, bada (balioa> * aldi baterako),

870
01:07:17,200 --> 01:07:24,010
gero eta (* tenp) -> eskubidea

871
01:07:24,010 --> 01:07:29,250
bestela, aldi baterako = & (* tenp) -> utzi.

872
01:07:29,250 --> 01:07:32,730
Eta orain, puntu honetan, bitartean begizta honen ondoren,

873
01:07:32,730 --> 01:07:36,380
Baino ez dut hau agian errazagoa delako buruz iteratively errekurtsiboki baino uste,

874
01:07:36,380 --> 01:07:39,010
baina bitartean begizta honen ondoren,

875
01:07:39,010 --> 01:07:43,820
* Aldi baterako erakuslea aldatu nahi dugu.

876
01:07:43,820 --> 01:07:48,960
>> Guraso izan aurretik, eta bai guraso ezkerrera edo guraso eskubidea aldatu nahi dugu,

877
01:07:48,960 --> 01:07:51,310
nahi dugu, baina guraso eskubidea aldatu nahi izanez gero,

878
01:07:51,310 --> 01:07:54,550
ondoren * temp, guraso eskubidea da, eta aldatzeko aukera izango dugu zuzenean.

879
01:07:54,550 --> 01:08:05,860
Beraz, behera hemen, * temp = newnode egin ahal izango dugu, eta hori da.

880
01:08:05,860 --> 01:08:09,540
Oharra Beraz, egin dugu kode lerro atera zen.

881
01:08:09,540 --> 01:08:14,770
Segimendua guztiak gurasoa duten ahalegina osagarria da.

882
01:08:14,770 --> 01:08:18,689
Hemen, besterik ez dugu mantendu bada pista erakuslea erakusleak,

883
01:08:18,689 --> 01:08:22,990
eta, nahiz eta horiek kizkur giltza guztiak kentzeko, orain nahi dugu,

884
01:08:22,990 --> 01:08:27,170
egin laburragoa itxura.

885
01:08:27,170 --> 01:08:32,529
Zehatza irtenbide bera da,

886
01:08:32,529 --> 01:08:38,210
baina kode-lerro gutxiago.

887
01:08:38,210 --> 01:08:41,229
Behin hau aitortzeko baliozko irtenbide gisa hasten zarenean,

888
01:08:41,229 --> 01:08:43,529
arrazoia buruz ere atsegin baino errazagoa da, ados,

889
01:08:43,529 --> 01:08:45,779
zergatik Ez daukat eskubidea int?

890
01:08:45,779 --> 01:08:49,290
Zer esan nahi du horrek? Oh, signifying da

891
01:08:49,290 --> 01:08:51,370
eskuinera joaten naiz, aldi bakoitzean ezarri behar dut

892
01:08:51,370 --> 01:08:53,819
bestela, joan I uzten bada zero ezarri behar dut.

893
01:08:53,819 --> 01:09:04,060
Hemen, ez dut horri buruzko arrazoia, besterik gabe, errazagoa da pentsatu.

894
01:09:04,060 --> 01:09:06,710
Zalantzak dituzu?

895
01:09:06,710 --> 01:09:16,290
[Ikaslea, ulertezina] >> Bai.

896
01:09:16,290 --> 01:09:23,359
Ongi da, eta, beraz, azken bit

897
01:09:23,359 --> 01:09:28,080
Bat azkar eta erraz egin ahal izango dugu funtzioa dela uste dut,

898
01:09:28,080 --> 01:09:34,910
let's batera, I guess, saiatu eta idatzi bat dauka funtzioa

899
01:09:34,910 --> 01:09:38,899
horrek ez du axola ala ez bilatu zuhaitz bitar bat.

900
01:09:38,899 --> 01:09:43,770
Honek funtzio egia itzuli behar

901
01:09:43,770 --> 01:09:58,330
hau, oro har, zuhaitz bitarra bada edozein lekutan balioa da bilatzen ari gara.

902
01:09:58,330 --> 01:10:02,520
Hargatik lehen egiten da, errekurtsiboki eta ondoren egin dugu iteratively.

903
01:10:02,520 --> 01:10:07,300
Benetan ahal izango dugu egin elkarrekin, hau da, oso laburra izan delako.

904
01:10:07,300 --> 01:10:11,510
>> Zein da nire oinarria kasuan behar du?

905
01:10:11,510 --> 01:10:13,890
[Ikaslea, ulertezina]

906
01:10:13,890 --> 01:10:18,230
[Bowden] Beraz, (zuhaitza == NULL), eta ondoren zer?

907
01:10:18,230 --> 01:10:22,740
[Student] itzuli faltsua.

908
01:10:22,740 --> 01:10:26,160
[Bowden Bestela, ondo, ez dut behar beste.

909
01:10:26,160 --> 01:10:30,250
Izan zen, bada nire base beste kasu.

910
01:10:30,250 --> 01:10:32,450
[Student] Tree balio? >> Bai.

911
01:10:32,450 --> 01:10:36,430
Beraz, (zuhaitz-> balioa == balioa bada.

912
01:10:36,430 --> 01:10:39,920
Ohartu gara berriro nodo *, ez nodo ** s?

913
01:10:39,920 --> 01:10:42,990
Contiene ez da inoiz behar nodo ** bat erabili ahal izateko,

914
01:10:42,990 --> 01:10:45,480
ari gara, ez baita erakusleak aldatzea.

915
01:10:45,480 --> 01:10:50,540
Ari gara traversing.

916
01:10:50,540 --> 01:10:53,830
Hori gertatuz gero, orduan egia itzuli nahi dugu.

917
01:10:53,830 --> 01:10:58,270
Bestela, seme-alabak zeharkatzeko nahi dugu.

918
01:10:58,270 --> 01:11:02,620
Beraz, ezin dugu ezkerreko dena gutxiago ala ez Arrazoia

919
01:11:02,620 --> 01:11:05,390
eta eskubidea dena da handiagoa.

920
01:11:05,390 --> 01:11:09,590
Beraz, gure egoera zein da hemen izango, edo zer egin dugu?

921
01:11:09,590 --> 01:11:11,840
[Ikaslea, ulertezina] >> Bai.

922
01:11:11,840 --> 01:11:17,400
Return dauka (balioa, zuhaitz-> ezker)

923
01:11:17,400 --> 01:11:26,860
edo dauka (balioa, zuhaitz-> eskubidea). Eta hori da.

924
01:11:26,860 --> 01:11:29,080
Eta zirkuitu-laburrik eragin ebaluazio batzuk,

925
01:11:29,080 --> 01:11:32,520
non gertatuko dugu zuhaitz ezkerreko balioa aurkitu nahi izanez gero,

926
01:11:32,520 --> 01:11:36,820
eskuineko zuhaitza begiratu behar dugu, inoiz ez.

927
01:11:36,820 --> 01:11:40,430
Hori guztia funtzioa.

928
01:11:40,430 --> 01:11:43,690
Orain egin dezagun da iteratively

929
01:11:43,690 --> 01:11:48,060
gutxiago nice izango.

930
01:11:48,060 --> 01:11:54,750
Nodo * orain = zuhaitz Irteeran ohiko hartu dugu.

931
01:11:54,750 --> 01:12:03,250
(Orain! = NULL) bitartean.

932
01:12:03,250 --> 01:12:08,600
Quickly arazo bat ikusteko.

933
01:12:08,600 --> 01:12:12,250
Orain badu - hemendik, inoiz ez dugu hautsi bada, hau da,

934
01:12:12,250 --> 01:12:16,020
gero exekuta dugu gauzak begiratzen, eta, beraz, itzultzeko faltsua.

935
01:12:16,020 --> 01:12:24,810
(Orain> balioa == balioa), itzultzeko Egia bada.

936
01:12:24,810 --> 01:12:32,910
Beraz, gaur egun, leku bat dugu

937
01:12:32,910 --> 01:12:36,250
ez dakigu ezkerrera edo eskuinera joan nahi dugu.

938
01:12:36,250 --> 01:12:44,590
Beraz, arbitrarioki, dezagun bakarrik utzi.

939
01:12:44,590 --> 01:12:47,910
, Jakina, non erabat Nik abandonatu guztia arazo bat sartu exekutatu dut

940
01:12:47,910 --> 01:12:50,760
Bakarrik izango dut inoiz egiaztatu zuhaitz baten ezkerretik.

941
01:12:50,760 --> 01:12:56,050
Inoiz ez dut ezer haurren eskubide bat da ezer egiaztatu.

942
01:12:56,050 --> 01:13:00,910
Nola hau konpontzeko?

943
01:13:00,910 --> 01:13:05,260
[Student] ezkerreko eta eskuineko pista pila batean gorde behar duzu.

944
01:13:05,260 --> 01:13:13,710
[Bowden] Bai. Hargatik da

945
01:13:13,710 --> 01:13:32,360
struct zerrenda, nodoen * n, eta, ondoren, nodo ** hurrengo?

946
01:13:32,360 --> 01:13:40,240
Nik uste dut ongi funtzionatzen.

947
01:13:40,240 --> 01:13:45,940
Hemen baino gehiago joan ezkerretara, edo let's nahi dugu.

948
01:13:45,940 --> 01:13:54,350
Egiturari zerrenda =, hasiko da

949
01:13:54,350 --> 01:13:58,170
struct zerrenda honetan out.

950
01:13:58,170 --> 01:14:04,040
* List = NULL. Beraz, izango da gure lotutako zerrenda

951
01:14:04,040 --> 01:14:08,430
subtrees saltatu dugun baino gehiago.

952
01:14:08,430 --> 01:14:13,800
Orain utzi Traverse dugu,

953
01:14:13,800 --> 01:14:17,870
baina ezinbestean eskuinera itzuli behar dugu,

954
01:14:17,870 --> 01:14:26,140
Eskuinaldean mantendu gure struct zerrenda barruan goaz.

955
01:14:26,140 --> 01:14:32,620
Ondoren new_list edo struct izan dugu,

956
01:14:32,620 --> 01:14:41,080
struct zerrenda, new_list = malloc (sizeof (zerrenda)).

957
01:14:41,080 --> 01:14:44,920
Dela error-checking alde batetara utzi dut, baina, egiaztatu bada bere null ikusi behar duzu.

958
01:14:44,920 --> 01:14:50,540
New_list nodo seinalatzen

959
01:14:50,540 --> 01:14:56,890
oh, zergatik nahi nuen hemen. Bigarren struct zerrenda bat seinalatu.

960
01:14:56,890 --> 01:15:02,380
Hori da, nola lotuta zerrendak lana.

961
01:15:02,380 --> 01:15:04,810
Int zerrenda bat lotuta berdina da

962
01:15:04,810 --> 01:15:06,960
ari izan ezik dugu int ordez * nodoa.

963
01:15:06,960 --> 01:15:11,040
Zehazki gauza bera.

964
01:15:11,040 --> 01:15:15,100
Beraz new_list, gure new_list nodoaren balioa,

965
01:15:15,100 --> 01:15:19,120
orain-> eskubidea izango da.

966
01:15:19,120 --> 01:15:24,280
Gure balioa new_list-> hurrengo gure jatorrizko zerrenda izango da,

967
01:15:24,280 --> 01:15:30,760
eta, ondoren, gure zerrenda eguneratzeko seinalatu new_list dugu.

968
01:15:30,760 --> 01:15:33,650
>> Orain gauza dio modu nolabaiteko behar dugu,

969
01:15:33,650 --> 01:15:37,020
dugu osoan ezkerreko Azpizuhaitza zeharkatu bezala.

970
01:15:37,020 --> 01:15:40,480
Orain stuff tira atera behar dugu,

971
01:15:40,480 --> 01:15:43,850
orain bezalakoa da, null, ez dugu nahi return false.

972
01:15:43,850 --> 01:15:50,370
Tira kanpo nahi dugu, gure zerrendan.

973
01:15:50,370 --> 01:15:53,690
Hau egiteko modu eroso A - ondo, egia esan, ez dago hau egiteko modu bat baino gehiago.

974
01:15:53,690 --> 01:15:56,680
Edonork iradokizun bat?

975
01:15:56,680 --> 01:15:58,790
Non hau edo hori nola egin behar dut egin behar dut?

976
01:15:58,790 --> 01:16:08,010
Besterik ez dugu minutu pare bat, baina edozein iradokizun?

977
01:16:08,010 --> 01:16:14,750
Ordez modu bat ordez, gure egoera izanik,

978
01:16:14,750 --> 01:16:17,090
zer ari gara begira ez da null

979
01:16:17,090 --> 01:16:22,340
ordez joan gure zerrendan bera null arte jarraituko dugu.

980
01:16:22,340 --> 01:16:25,680
Beraz, gure zerrendan eta ondorioz sortu null izatea,

981
01:16:25,680 --> 01:16:30,680
ondoren exekutatu ditugu gauzak begiratu, bilatu.

982
01:16:30,680 --> 01:16:39,860
Baina horrek esan nahi du gure zerrendan lehen gauza besterik ez da lehen nodoaren izango.

983
01:16:39,860 --> 01:16:49,730
Oso lehenengo gauza izango da - Behar ez dugu ikusten.

984
01:16:49,730 --> 01:16:58,710
Beraz, zerrenda-> n gure zuhaitz izango da.

985
01:16:58,710 --> 01:17:02,860
list-> hurrengo null izango da.

986
01:17:02,860 --> 01:17:07,580
Eta orain zerrenda ez, berriz, berdintasuna null.

987
01:17:07,580 --> 01:17:11,610
Orain zerbait zabaltzen da gure zerrenda.

988
01:17:11,610 --> 01:17:13,500
Beraz, orain da berdina list-> n.

989
01:17:13,500 --> 01:17:20,850
Eta gero, zerrenda berdina list-> n, edo zerrenda-> hurrengo.

990
01:17:20,850 --> 01:17:23,480
Beraz, orain bada balioa berdin balio.

991
01:17:23,480 --> 01:17:28,790
Orain bai gure eskubidea eta gure ezkerretara erakuslea erakusleak gehitu ahal izango dugu.

992
01:17:28,790 --> 01:17:32,900
betiere Oraindik ez dute null.

993
01:17:32,900 --> 01:17:36,390
Hortik behera, uste dut egin behar dugu lehenik eta behin.

994
01:17:36,390 --> 01:17:44,080
(Orain> eskubidea! = NULL) bada

995
01:17:44,080 --> 01:17:56,380
gero nodo gure zerrenda horretan sartu gara.

996
01:17:56,380 --> 01:17:59,290
(Orain-> ezker) bada, hau da aparteko lana pixka bat da, baina fina da.

997
01:17:59,290 --> 01:18:02,690
(Orain-> ezker! = NULL) bada,

998
01:18:02,690 --> 01:18:14,310
eta ezker lotuta sartu gure zerrendan sartu dugu,

999
01:18:14,310 --> 01:18:19,700
eta hori izan beharko luke.

1000
01:18:19,700 --> 01:18:22,670
Batetik bestera joateko dugu, betiere, zerbait izan dugun bezala gure zerrendan,

1001
01:18:22,670 --> 01:18:26,640
nodoa beste begiratzen dugu.

1002
01:18:26,640 --> 01:18:28,920
Beraz, itxura nodo hartan,

1003
01:18:28,920 --> 01:18:31,390
gure zerrendan hurrengo bat aurrera egin dugu.

1004
01:18:31,390 --> 01:18:34,060
Nodo hori bilatzen ari gara balioa bada, itzultzeko egia esan daiteke.

1005
01:18:34,060 --> 01:18:37,640
Bestela, bai ezkerreko eta eskuineko subtrees sartu,

1006
01:18:37,640 --> 01:18:40,510
betiere Oraindik ez dute null, gure zerrendan sartu

1007
01:18:40,510 --> 01:18:43,120
beraz, haien gainean ezinbestean gara.

1008
01:18:43,120 --> 01:18:45,160
Beraz, bada ez ziren null,

1009
01:18:45,160 --> 01:18:47,950
gure root erakuslea bi gauza adierazi bada,

1010
01:18:47,950 --> 01:18:51,670
ondoren, lehen zerbait bota dugu gure zerrenda eta ondorioz, beraz null izatea.

1011
01:18:51,670 --> 01:18:56,890
Eta gero, bi gauza jarri dugu berriro, beraz, gaur egun, gure zerrendan tamaina 2.

1012
01:18:56,890 --> 01:19:00,030
Ondoren, loop ari gara itzuli arte, eta besterik ez gabiltza zabaltzen joan da,

1013
01:19:00,030 --> 01:19:04,250
demagun, gure root nodoaren erakuslea ezker.

1014
01:19:04,250 --> 01:19:07,730
Eta hori dugu, besterik gabe mantendu gertatzen ari den; amaituko dugu dena baino gehiago begizta batean.

1015
01:19:07,730 --> 01:19:11,280
>> Iragarki hori izan da, nabarmen zailagoa

1016
01:19:11,280 --> 01:19:14,160
recursive konponbidea.

1017
01:19:14,160 --> 01:19:17,260
Eta behin baino gehiagotan esan dut

1018
01:19:17,260 --> 01:19:25,120
recursive konponbidea izan ohi du komun askoz etorriko konponbidea.

1019
01:19:25,120 --> 01:19:30,820
Hemen hori da recursive konponbidea zehatz-mehatz zer egiten ari da.

1020
01:19:30,820 --> 01:19:36,740
Aldaketa bakarra inplizituki pila erabiliz ordez, programa pila,

1021
01:19:36,740 --> 01:19:40,840
jarraipena zer nodo bisitatu behar duzu zure modu gisa,

1022
01:19:40,840 --> 01:19:45,430
lotutako zerrenda bat esplizituki erabili behar duzu.

1023
01:19:45,430 --> 01:19:49,070
Bi kasuetan, pista ari zaren mantenduz zer nodo oraindik behar bisitatu beharreko.

1024
01:19:49,070 --> 01:19:51,790
Errekurtsiboaren kasuan errazagoa da pila bat delako

1025
01:19:51,790 --> 01:19:57,100
inplementatu programa pila.

1026
01:19:57,100 --> 01:19:59,550
Oharra lotuta zerrenda hau, pila bat da.

1027
01:19:59,550 --> 01:20:01,580
Whatever pilaketan besterik ez dugu jarri

1028
01:20:01,580 --> 01:20:09,960
da berehala zer off tira pila hurrengo bisitatzera goaz.

1029
01:20:09,960 --> 01:20:14,380
Gara, baina edozein galdera?

1030
01:20:14,380 --> 01:20:23,530
[Ikaslea, ulertezina]

1031
01:20:23,530 --> 01:20:27,790
[Bowden] Bai. Beraz, bada, gure lotutako zerrenda dugu,

1032
01:20:27,790 --> 01:20:30,150
korrontea guy hau seinalatu

1033
01:20:30,150 --> 01:20:34,690
eta orain ari gara gure lotutako zerrenda aurrera lasaia honetan zentratuko da.

1034
01:20:34,690 --> 01:20:44,200
Ildo horretan zerrenda lotuta traversing baino gehiago ari gara.

1035
01:20:44,200 --> 01:20:51,200
Eta gero, gure lotutako zerrenda eta stuff libre behar dugula uste dut

1036
01:20:51,200 --> 01:20:53,880
behin egia edo gezurra itzuli baino lehen, behar dugu

1037
01:20:53,880 --> 01:20:57,360
lotuta baino gehiago gure zerrendan batetik bestera joateko eta beti behera hemen, I guess,

1038
01:20:57,360 --> 01:21:03,900
dugu orain eskuinera bada, ez da berdina, gehitu du, eta, beraz, orain libre nahi dugu

1039
01:21:03,900 --> 01:21:09,600
orain delako, bai, ez zerrendari buruzko erabat dugu ahaztu? Bai.

1040
01:21:09,600 --> 01:21:12,880
Beraz, hemen zer egin nahi dugu.

1041
01:21:12,880 --> 01:21:16,730
Non dago erakuslea da?

1042
01:21:16,730 --> 01:21:23,320
Cur zen ondoren struct zerrenda bat * 10 berdinen zerrenda hurrengoa nahi dugu.

1043
01:21:23,320 --> 01:21:29,240
Free zerrenda, list = tenp.

1044
01:21:29,240 --> 01:21:32,820
Eta kasu honetan, non egia itzuliko gara, behar ez dugu batetik bestera joateko

1045
01:21:32,820 --> 01:21:37,050
gure zerrendan lotutako gauzak askatzeaz gainerako zehar.

1046
01:21:37,050 --> 01:21:39,700
Errekurtsiboaren irtenbide buruz gauza polita da gauza askatzeaz

1047
01:21:39,700 --> 01:21:44,930
besterik gabe esan nahi du pila izango duzu gertatuko off factorings leihoa.

1048
01:21:44,930 --> 01:21:50,720
Beraz, zerbait uste hard-to-buruzko-kodea 3 lerro bezala dugu joan

1049
01:21:50,720 --> 01:21:57,520
zerbait da, nabarmen askoz gehiago hard-to-uste-buruzko kode lerro.

1050
01:21:57,520 --> 01:22:00,620
Edozein galdera bat baino gehiago?

1051
01:22:00,620 --> 01:22:08,760
Guztiak eskubidea. Onak gara. Bye!

1052
01:22:08,760 --> 01:22:11,760
[CS50.TV]