1
00:00:00,000 --> 00:00:02,000
[Powered by Google Translate] [Binary Search]

2
00:00:02,000 --> 00:00:04,000
[Patrick Schmid - Harvard Unibertsitatea]

3
00:00:04,000 --> 00:00:07,000
[Hau CS50 da. - CS50.TV]

4
00:00:07,000 --> 00:00:09,000
>> Eman dut baduzu Disney pertsonaia izenak zerrenda ordena alfabetikoan

5
00:00:09,000 --> 00:00:11,000
zaizu eta Mickey Mouse aurkitu,

6
00:00:11,000 --> 00:00:13,000
nola hau egiten al duzu?

7
00:00:13,000 --> 00:00:15,000
One bistako hasieratik zerrenda eskaneatu izango litzateke

8
00:00:15,000 --> 00:00:18,000
eta egiaztatu izena da Mickey bada bakoitzean ikusteko.

9
00:00:18,000 --> 00:00:22,000
Baina irakurri nahi Aladdin, Alice, Ariel, eta abar,

10
00:00:22,000 --> 00:00:25,000
zerrendan aurrean hasita azkar duzu konturatzen ez zela ideia ona.

11
00:00:25,000 --> 00:00:29,000
Ados, agian atzeraka lan zerrendaren bukaeran hasi behar duzu.

12
00:00:29,000 --> 00:00:33,000
Orain Tarzan, Stitch, Snow White, eta abar irakurri duzu.

13
00:00:33,000 --> 00:00:36,000
Hala eta guztiz ere, ez dirudi buruz joan modurik onena bezala.

14
00:00:36,000 --> 00:00:38,000
>> Beno, beste modu bat izan duzula horretan buruz behera mugatu saiatzeko

15
00:00:38,000 --> 00:00:41,000
izenak zerrenda begiratzen duzula.

16
00:00:41,000 --> 00:00:43,000
Badakizu, ordena alfabetikoan dira geroztik,

17
00:00:43,000 --> 00:00:45,000
izenak begiratu besterik ez izan zerrendaren erdian

18
00:00:45,000 --> 00:00:49,000
eta egiaztatu Mickey Mouse izen hori aurretik edo ondoren bada.

19
00:00:49,000 --> 00:00:51,000
Bigarren zutabean abizena begira

20
00:00:51,000 --> 00:00:54,000
konturatzen Mickey M Jasmine for J ondoren dator nahi duzuna

21
00:00:54,000 --> 00:00:57,000
beraz, besterik ez dituzu, ez ikusi egin zerrenda lehen erdia.

22
00:00:57,000 --> 00:00:59,000
Ondoren, seguruenik litzaidake duzu azken zutabean goialdean bilatzeko

23
00:00:59,000 --> 00:01:02,000
ikusi eta Rapunzel hasten dela.

24
00:01:02,000 --> 00:01:06,000
Mickey Rapunzel aurretik dator; azken zutabean itxura dugu ahaztu bezala baita.

25
00:01:06,000 --> 00:01:08,000
Etengabeko bilaketa-estrategia, azkar ikusiko dituzu Mickey dela

26
00:01:08,000 --> 00:01:11,000
gainerako zerrenda izenak lehenengo seihilekoan

27
00:01:11,000 --> 00:01:14,000
eta, azkenik, Mickey Merlin eta Minnie artean ezkutatzen dira.

28
00:01:14,000 --> 00:01:17,000
>> Zer egin besterik ez duzu, funtsean, bitar bilaketa izan zen.

29
00:01:17,000 --> 00:01:22,000
Izen hori dakar, bere bilaketa-estrategia egiten da materia bitar bat.

30
00:01:22,000 --> 00:01:24,000
Zer esan nahi du horrek?

31
00:01:24,000 --> 00:01:27,000
Beno, horrela antolatu elementu zerrenda bat ematen da, binary bilaketa algoritmoa bitarrak erabaki bat hartu du

32
00:01:27,000 --> 00:01:33,000
ezkerrera edo eskuinera, baino handiagoa edo txikiagoa, baino aurretik edo ondoren alfabetikoki puntu bakoitzean.

33
00:01:33,000 --> 00:01:35,000
Orain bilaketa-algoritmo honekin batera doan izen bat dugula,

34
00:01:35,000 --> 00:01:38,000
dezagun beste adibide bat begiratu, baina oraingo honetan zenbakiak ordenatuko zerrenda bat.

35
00:01:38,000 --> 00:01:43,000
Esan kopurua 144 zenbakiak ordenatuko zerrenda hau bilatzen ari gara.

36
00:01:43,000 --> 00:01:46,000
Just nahi baino lehen, zenbaki erdian aurkituko dugu

37
00:01:46,000 --> 00:01:50,000
kasu honetan 13 eta 144 baino handiagoa edo 13 baino gutxiago bada.

38
00:01:50,000 --> 00:01:54,000
Da argi eta garbi 13 baino handiagoa izan denez, dena alde batetara utzi ahal izango dugu, hau da, 13 edo gutxiago

39
00:01:54,000 --> 00:01:57,000
eta gainerako erdia da.

40
00:01:57,000 --> 00:01:59,000
Orain dugu geroztik, nahiz eta utzi bat elementu kopurua,

41
00:01:59,000 --> 00:02:01,000
erditik hurbil da zenbaki bat aukeratu besterik ez dugu.

42
00:02:01,000 --> 00:02:03,000
Kasu honetan, 55 aukeratu dugu.

43
00:02:03,000 --> 00:02:06,000
Izan bezain erraz izan dugu aukeratu 89.

44
00:02:06,000 --> 00:02:11,000
Ongi da. Berriz ere, 144 55 baino handiagoa da, beraz, joateko eskubidea dugu.

45
00:02:11,000 --> 00:02:14,000
Zorionez, gurekin, hurrengo erdian kopurua 144 da, eta

46
00:02:14,000 --> 00:02:16,000
bat bilatzen ari gara.

47
00:02:16,000 --> 00:02:21,000
Beraz, ordena 144 bitarrak bilaketa bat erabiliz, gai da bakarrik 3 urrats aurkituko gara.

48
00:02:21,000 --> 00:02:24,000
Erabiltzen dugu izanez gero hemen lineal bilaketa, hartu litzateke 12 urrats.

49
00:02:24,000 --> 00:02:28,000
Izan ere, materia gisa, bilaketa-metodo hau aurrera elementu kopurua halves

50
00:02:28,000 --> 00:02:31,000
Urrats bakoitzean begiratu du, elementua aurkitu ahal izango da bilatzen

51
00:02:31,000 --> 00:02:35,000
zerrendako elementu kopurua log buruz.

52
00:02:35,000 --> 00:02:37,000
Orain ikusten ditudan 2 pieza dezagun, bada, itxura batean

53
00:02:37,000 --> 00:02:41,000
funtzioa errekurtsiboa bilaketa bitarra ezartzen pseudocode batzuk.

54
00:02:41,000 --> 00:02:44,000
Goialdean hasita, 4 argumenturik hartzen dituen funtzio bat aurkitu dugula ikusiko dugu:

55
00:02:44,000 --> 00:02:47,000
gakoa, array, min, eta max.

56
00:02:47,000 --> 00:02:51,000
Gakoa ari garela, beraz, aurreko Adibidez 144 zenbakia da.

57
00:02:51,000 --> 00:02:54,000
Array ari garen zenbakien zerrenda bilatzen da.

58
00:02:54,000 --> 00:02:57,000
Min eta gutxieneko eta gehieneko posizio max indizeak

59
00:02:57,000 --> 00:02:59,000
ari gara gaur egun begira.

60
00:02:59,000 --> 00:03:03,000
Beraz abiarazten dugunean, min zero izango da eta max array gehienezko indizea izango da.

61
00:03:03,000 --> 00:03:07,000
Mugatu gara bilaketa behera, min eta max eguneratu egingo dugu

62
00:03:07,000 --> 00:03:10,000
sorta ari garela oraindik sartu bilatzen

63
00:03:10,000 --> 00:03:12,000
>> Dezagun interesgarria parte saltatzeko lehen.

64
00:03:12,000 --> 00:03:14,000
Egiten dugun lehen gauza da aurkitu erdigunea,

65
00:03:14,000 --> 00:03:19,000
indizea array oraindik ari garela kontuan hartuta, min eta max arteko erdibidean da.

66
00:03:19,000 --> 00:03:22,000
Ondoren, begiratu array balioa dugu erdigunea kokapena hartan

67
00:03:22,000 --> 00:03:25,000
ikusi eta bila ari garela gako bat baino gutxiago bada.

68
00:03:25,000 --> 00:03:27,000
Posizio hartan kopurua txikiagoa bada,

69
00:03:27,000 --> 00:03:31,000
sakatu posizio horren ezkerreko zenbakiak guztiak baino handiagoa da esan nahi du.

70
00:03:31,000 --> 00:03:33,000
Beraz, bilaketa-funtzioa bitarraren deitu ahal izango dugu berriro,

71
00:03:33,000 --> 00:03:36,000
baina oraingo honetan min eta max parametroak eguneratzeko erdia besterik ez irakurri

72
00:03:36,000 --> 00:03:40,000
hau da, begiratu besterik ez dugu at balioa baino handiagoa edo berdina.

73
00:03:40,000 --> 00:03:44,000
Beste alde batetik, gakoa da array egungo erdigunea kopurua baino txikiagoa bada,

74
00:03:44,000 --> 00:03:47,000
ezkerrera joan eta guztiak dira handiagoa zenbakiak alde batetara utzi nahi dugu.

75
00:03:47,000 --> 00:03:52,000
Berriz ere, min eta max eguneraketa gama bitarra bilatu, baina denbora honetan deitzen dugun

76
00:03:52,000 --> 00:03:54,000
besterik ez beheko erdian.

77
00:03:54,000 --> 00:03:57,000
Array uneko erdigunea balioa ez da bada

78
00:03:57,000 --> 00:04:01,000
baino handiagoa, ezta gakoa baino txikiagoa da, orduan gakoa berdina izan behar du.

79
00:04:01,000 --> 00:04:05,000
Horrela, besterik gabe, ahal izango dugu itzultzeko uneko erdigunea indizea, eta egin gaude.

80
00:04:05,000 --> 00:04:09,000
Azkenik, hau hemen check kasuan kopurua

81
00:04:09,000 --> 00:04:11,000
ez da benetan zenbakiak bilatzen ari gara array.

82
00:04:11,000 --> 00:04:14,000
Gama gehienezko indizea bila ari garela bada

83
00:04:14,000 --> 00:04:17,000
gutxieneko inoiz baino txikiagoa da, horrek esan nahi du joan ditudan urrunegi.

84
00:04:17,000 --> 00:04:20,000
Kopurua ez zen aurrera sarrera array, -1 itzuliko gara

85
00:04:20,000 --> 00:04:24,000
ezer ez adierazi aurkitu zen.

86
00:04:24,000 --> 00:04:26,000
>> Konturatuko algoritmo hau lan egin dezakezu,

87
00:04:26,000 --> 00:04:28,000
zenbakien zerrenda ordenatuko diren.

88
00:04:28,000 --> 00:04:31,000
Beste era batera esanda, baino ezin dugu aurkitu 144 bitar bilaketa erabiliz

89
00:04:31,000 --> 00:04:34,000
zenbaki guztiak dira txikiena etatik handiena agindu zuen.

90
00:04:34,000 --> 00:04:38,000
Hori gutxi ez bada, ez genuke urrats bakoitzaren zenbakiak erdia kanpoan utzi ahal izango.

91
00:04:38,000 --> 00:04:40,000
Hori dela eta, 2 aukera ditugu.

92
00:04:40,000 --> 00:04:43,000
Edo Unsorted zerrenda bat hartu ahal izango dugu, eta ordenatzeko bilaketa bitarra erabiliz aurretik,

93
00:04:43,000 --> 00:04:48,000
edo ziurtatu zenbakien zerrendan gehitu ditugu zenbakiak bezala hori horrela antolatu ahal izango dugu.

94
00:04:48,000 --> 00:04:50,000
Horrela, bakarrik bilatu behar dugu ordenatzeko ordez,

95
00:04:50,000 --> 00:04:53,000
zergatik ez gorde uneoro antolatuta zerrendan?

96
00:04:53,000 --> 00:04:57,000
>> Joanekoa zenbakien zerrenda bat gorde ordenatuko aldi berean aukera ematen du

97
00:04:57,000 --> 00:04:59,000
gehitu edo bat mugitu zenbakiak zerrenda honetan

98
00:04:59,000 --> 00:05:02,000
zerbait izeneko bilaketa zuhaitz bitar bat erabiliz.

99
00:05:02,000 --> 00:05:05,000
A binary bilaketa-zuhaitz bat datuak egitura 3 propietate ditu.

100
00:05:05,000 --> 00:05:09,000
Lehenik eta behin, ezker nodo edozein Azpizuhaitza diren balioak baino gutxiago bakarrik ditu

101
00:05:09,000 --> 00:05:11,000
edo nodo balio berdinak.

102
00:05:11,000 --> 00:05:15,000
Bigarrenik, nodo bat Azpizuhaitza eskubidea baino ez diren balioak baino handiagoa

103
00:05:15,000 --> 00:05:17,000
edo nodo balio berdinak.

104
00:05:17,000 --> 00:05:20,000
Eta, azkenik, nodo guztiak subtrees bai ezkerreko eta eskuineko

105
00:05:20,000 --> 00:05:23,000
bilaketa zuhaitz bitarra.

106
00:05:23,000 --> 00:05:26,000
Dezagun adibide bat bilatzeko lehenago erabiltzen dugun zenbaki bereko.

107
00:05:26,000 --> 00:05:30,000
Dutenek ez dute inoiz ikusi ez informatika zuhaitza aurretik,

108
00:05:30,000 --> 00:05:34,000
utzi hasiko diozu informatika zuhaitza hazten beherantz by me.

109
00:05:34,000 --> 00:05:36,000
Bai, zuhaitzak dira ohituta ez bezala,

110
00:05:36,000 --> 00:05:38,000
informatika zuhaitza root goialdean da,

111
00:05:38,000 --> 00:05:41,000
eta hostoak, behealdean.

112
00:05:41,000 --> 00:05:45,000
Little box bakoitzak nodo bat deitzen da, eta nodoak dira ertzak by elkarren artean lotuta.

113
00:05:45,000 --> 00:05:48,000
Beraz, Zuhaitz hau root 13 balioa balio nodo bat da,

114
00:05:48,000 --> 00:05:52,000
2 balioak 5 eta 34 seme-alabak nodoak ditu.

115
00:05:52,000 --> 00:05:57,000
Azpizuhaitza A zuhaitz hori zuhaitz osoa azpiataletan begira eratu da.

116
00:05:57,000 --> 00:06:03,000
>> Adibidez, nodo 3 Azpizuhaitza ezkerreko nodo 0, 1, eta 2 sortutako zuhaitza da.

117
00:06:03,000 --> 00:06:06,000
Beraz, joaten gara itzuliz gero bilaketa zuhaitz bitar propietateak,

118
00:06:06,000 --> 00:06:09,000
zuhaitza nodo bakoitzean 3 propietate, hala nola egokitzen duen ikusiko dugu,

119
00:06:09,000 --> 00:06:15,000
ezker Azpizuhaitza baino gutxiago edo nodo balio berdinak diren balioak baino ez ditu;

120
00:06:15,000 --> 00:06:16,000
nodo guztiak Azpizuhaitza

121
00:06:16,000 --> 00:06:19,000
baino ez diren balioak baino handiagoa edo nodo balio berdinak;

122
00:06:19,000 --> 00:06:25,000
bai ezkerreko eta eskuineko nodo guztiak subtrees ere binary bilaketa zuhaitzak dira.

123
00:06:25,000 --> 00:06:28,000
Zuhaitz hau itxura ezberdina izan arren, hau da baliozko bitar bilaketa zuhaitza da

124
00:06:28,000 --> 00:06:30,000
zenbakiak multzo berean.

125
00:06:30,000 --> 00:06:32,000
Izan ere, materia gisa, ahalik eta modu asko daude, sortzen dituzun

126
00:06:32,000 --> 00:06:35,000
baliozko bitar bilaketa zenbaki horiek zuhaitz bat.

127
00:06:35,000 --> 00:06:38,000
Beno, goazen bat sortu dugu lehen itzuli.

128
00:06:38,000 --> 00:06:40,000
Beraz, zer egin dezaket dugu zuhaitz horiek?

129
00:06:40,000 --> 00:06:44,000
Beno, oso besterik gabe, gutxieneko eta gehieneko balioak aurkituko ditugu.

130
00:06:44,000 --> 00:06:46,000
Gutxieneko balioak beti ezkerreko aurkitu daitezke

131
00:06:46,000 --> 00:06:48,000
no gehiago daude nodo bisitatzeko arte.

132
00:06:48,000 --> 00:06:53,000
Aitzitik, gehienezko bat aurkitzeko, besterik gabe, besterik ez jaisten eskubidea aldi bakoitzean.

133
00:06:54,000 --> 00:06:56,000
>> Beste edozein zenbaki aurkitzea ez da gutxieneko edo gehieneko

134
00:06:56,000 --> 00:06:58,000
bezain erraza da.

135
00:06:58,000 --> 00:07:00,000
Esan 89 zenbakia bilatzen ari gara.

136
00:07:00,000 --> 00:07:03,000
Nodo bakoitzaren balioa egiaztatu besterik ez dugu, eta joan ezkerrera edo eskuinera,

137
00:07:03,000 --> 00:07:06,000
Nodo balioa baino txikiagoa edo baino handiagoa den ala ez arabera

138
00:07:06,000 --> 00:07:08,000
bat bilatzen ari gara.

139
00:07:08,000 --> 00:07:11,000
Beraz, 13 erro hasita, 89 handiagoa ikusiko dugu,

140
00:07:11,000 --> 00:07:13,000
eta, beraz, eskubidea dugu.

141
00:07:13,000 --> 00:07:16,000
Ondoren, 34 nodo ikusiko dugu, eta berriro joateko eskubidea dugu.

142
00:07:16,000 --> 00:07:20,000
89 55 baino handiagoa da oraindik, beraz, eskuinera jarraituko dugu.

143
00:07:20,000 --> 00:07:24,000
Ondoren etorri gara 144 balioa nodo bat eta ezkerrera joan.

144
00:07:24,000 --> 00:07:26,000
Lo eta behold, 89 bertan.

145
00:07:26,000 --> 00:07:31,000
>> Inorder traversal bat egitean zenbakiak guztiak inprimatu ahal izango dugu beste gauza bat da.

146
00:07:31,000 --> 00:07:35,000
Traversal inorder bat esan nahi guztia inprimatu ezkerreko Azpizuhaitza

147
00:07:35,000 --> 00:07:37,000
nodoaren inprimatzean berak

148
00:07:37,000 --> 00:07:40,000
eta, ondoren, guztia inprimatzeko eskubidea Azpizuhaitza ondoren.

149
00:07:40,000 --> 00:07:43,000
Esate baterako, dezagun gure gogoko binary bilaketa zuhaitz

150
00:07:43,000 --> 00:07:46,000
inprimatu eta ordena ordenatuko zenbakiak.

151
00:07:46,000 --> 00:07:49,000
Erro 13 hasiko gara, baina inprimatze 13 baino lehen inprimatu behar dugu

152
00:07:49,000 --> 00:07:51,000
ezkerreko Azpizuhaitza dena.

153
00:07:51,000 --> 00:07:55,000
Beraz, 5. Dugu oraindik sakonago behera joan zuhaitza aurkitzen dugu ezker-nodo arte,

154
00:07:55,000 --> 00:07:57,000
hau da, zero.

155
00:07:57,000 --> 00:08:00,000
Inprimaketa zero ondoren, atzera egin dugu 1 eta out duten inprimatzeko.

156
00:08:00,000 --> 00:08:03,000
Ondoren, joan eskuinera Azpizuhaitza, hau da, 2, eta out duten inprimatzeko.

157
00:08:03,000 --> 00:08:05,000
Orain gaude Azpizuhaitza hori egiten,

158
00:08:05,000 --> 00:08:07,000
itzuli ahal izango da, gehienez ere 3 eta inprimatu.

159
00:08:07,000 --> 00:08:11,000
Atzera Etengabeko sortu, 5 inprimatu dugu eta, ondoren, 8.

160
00:08:11,000 --> 00:08:13,000
Orain dugun osoa utzi Azpizuhaitza

161
00:08:13,000 --> 00:08:17,000
inprimatu ahal izango dugu 13 eta eskubidea Azpizuhaitza lanean hasteko.

162
00:08:17,000 --> 00:08:21,000
Behera hop dugu 34, baina inprimatze 34 baino lehen haren ezkerreko Azpizuhaitza inprimatu ditugu.

163
00:08:21,000 --> 00:08:27,000
Beraz, inprimatu dugu, 21; gero inprimatu eta 34 lortzen dugu eta haren eskuinaldean Azpizuhaitza bisitatzeko.

164
00:08:27,000 --> 00:08:31,000
55 ditu ezker Azpizuhaitza ez denez, inprimatu dugu eta jarraitzeko bere eskubidea Azpizuhaitza.

165
00:08:31,000 --> 00:08:36,000
144 ezker Azpizuhaitza ditu, eta, beraz, inprimatu ditugu, 89, 144, eta ondoren,

166
00:08:36,000 --> 00:08:39,000
eta, azkenik, 233 nodo eskuin-gehienak.

167
00:08:39,000 --> 00:08:44,000
Hor duzu, zenbaki guztiak dira inprimatutako txikiena etatik handiena ordena.

168
00:08:44,000 --> 00:08:47,000
>> Zuhaitzaren zerbait gehitzea nahiko erraza baita.

169
00:08:47,000 --> 00:08:51,000
Guztiak egin behar dugu, ziur jarraituko dugula 3 bitarra bilaketa zuhaitz propietate egin da

170
00:08:51,000 --> 00:08:53,000
eta, ondoren sartu balioa non dago espazioa.

171
00:08:53,000 --> 00:08:55,000
Demagun balioa 7 txertatu nahi dugu.

172
00:08:55,000 --> 00:08:58,000
7 baino txikiagoa da 13 urteaz geroztik, joan ezkerrera dugu.

173
00:08:58,000 --> 00:09:01,000
Baina 5 baino handiagoa da, eta, beraz, zeharkatzeko eskubidea dugu.

174
00:09:01,000 --> 00:09:04,000
Baino gutxiago 8 eta 8 hosto nodo bat denez, 7 gehitzen badiogu, 8 seme-alaba ezker.

175
00:09:04,000 --> 00:09:09,000
Voila! Zenbaki bat gehitu dugu gure bitar bilaketa zuhaitza.

176
00:09:09,000 --> 00:09:12,000
>> Gauzak gehitzen badiogu, hobe dugu gauzak ezabatu baita.

177
00:09:12,000 --> 00:09:14,000
Zoritxarrez guretzat, ezabatzen da, pixka bat zailagoa

178
00:09:14,000 --> 00:09:16,000
ez da hainbeste, baina apur bat.

179
00:09:16,000 --> 00:09:18,000
Badira 3 dugula kontuan hartu beharreko hainbat eszenatoki

180
00:09:18,000 --> 00:09:21,000
elementuak ezabatzen bilaketa zuhaitz bitarra from.

181
00:09:21,000 --> 00:09:24,000
Lehenik eta behin, kasu errazena da elementu hosto nodo bat da.

182
00:09:24,000 --> 00:09:27,000
Kasu honetan, ezabatu besterik ez dugu eta gure enpresa.

183
00:09:27,000 --> 00:09:30,000
Esan 7 besterik ez dugu gehitu ezabatu nahi dugu.

184
00:09:30,000 --> 00:09:34,000
Beno, besterik gabe aurkituko dugu, kendu, eta hori da.

185
00:09:35,000 --> 00:09:37,000
Hurrengo kasua da nodoaren 1 seme-alaba ditu.

186
00:09:37,000 --> 00:09:40,000
Hemen nodoak ezabatu ahal izango dugu, baina lehen, ziurtatu

187
00:09:40,000 --> 00:09:42,000
Azpizuhaitza hori utzi parentless konektatu

188
00:09:42,000 --> 00:09:44,000
nodo guraso ezabatu besterik ez dugu.

189
00:09:44,000 --> 00:09:47,000
Esan 3 ezabatu nahi dugu, gure zuhaitz.

190
00:09:47,000 --> 00:09:50,000
Nodo horren elementu seme-alabak hartuko dugu, eta nodo guraso erantsi.

191
00:09:50,000 --> 00:09:54,000
Kasu honetan, gaur egun ari gara 1 5 erantsiz.

192
00:09:54,000 --> 00:09:57,000
Hau arazo bat izan gabe lan egiten du ezagutzen dugulako, binary bilaketa zuhaitz jabetza arabera,

193
00:09:57,000 --> 00:10:01,000
3 ezker Azpizuhaitza dena 5 baino gutxiago izan zen.

194
00:10:01,000 --> 00:10:05,000
Orain dela 3 Azpizuhaitza tratua da, ezabatu ahal izango dugu.

195
00:10:05,000 --> 00:10:08,000
Hirugarren eta azken kasu konplexuena da.

196
00:10:08,000 --> 00:10:11,000
Kasu honetan nodo ezabatu nahi dugun 2 seme-alaba ditu.

197
00:10:11,000 --> 00:10:15,000
Horretarako, lehen nodoa hurrengo balio handiena aurkituko dugu,

198
00:10:15,000 --> 00:10:18,000
Trukatu bi, eta ondoren galdera nodo ezabatu.

199
00:10:18,000 --> 00:10:22,000
Iragarki hurrengo balio handiena ezin izan 2 haur bera duen nodo

200
00:10:22,000 --> 00:10:26,000
haren ezkerreko seme hurrengo handiena hobeto hautagai bat izango litzateke.

201
00:10:26,000 --> 00:10:30,000
Beraz, 2 seme-alabekin nodo bat ezabatzen 2 nodoen aldaketa kopuruei

202
00:10:30,000 --> 00:10:33,000
eta, ondoren, ezabatzen 1 2 arau horietako kudeatu.

203
00:10:33,000 --> 00:10:37,000
Esate baterako, demagun erroko nodoa, 13 ezabatu nahi dugu.

204
00:10:37,000 --> 00:10:39,000
Egiten dugun lehen gauza da zuhaitza hurrengo balioa handiena aurkituko dugu

205
00:10:39,000 --> 00:10:41,000
Izan ere, kasu honetan, 21.

206
00:10:41,000 --> 00:10:46,000
2 nodo swap dugu, hosto bat 13 eta 21 talde erdiko nodo egiteko.

207
00:10:46,000 --> 00:10:49,000
Orain, besterik gabe, ezabatu ahal izango dugu 13.

208
00:10:50,000 --> 00:10:53,000
>> Bezala lehenago aipatu, ahalik eta modu asko daude baliozko bitar bilaketa zuhaitza egiteko.

209
00:10:53,000 --> 00:10:56,000
Zoritxarrez guretzat, batzuk besteak baino okerragoak dira.

210
00:10:56,000 --> 00:10:59,000
Esate baterako, zer gertatzen den bilaketa bitarra zuhaitz bat eraikitzen dugu

211
00:10:59,000 --> 00:11:01,000
zenbakien zerrenda ordenatuko?

212
00:11:01,000 --> 00:11:04,000
Zenbaki guztiak eskuinera gehitu besterik ez dira urrats bakoitzean.

213
00:11:04,000 --> 00:11:06,000
Zenbaki bat bilatu nahi dugu,

214
00:11:06,000 --> 00:11:08,000
aukeratu dugu, baina soilik eskuinera begiratu Urrats bakoitzean.

215
00:11:08,000 --> 00:11:11,000
Hau ez da bilaketa lineala guztiak baino hobea da.

216
00:11:11,000 --> 00:11:13,000
Estali egingo dugu ez den arren hemen, ez dago beste, konplexuagoak dira,

217
00:11:13,000 --> 00:11:16,000
datuen egitura hau ez dela gertatuko ziurtatu.

218
00:11:16,000 --> 00:11:18,000
Hala eta guztiz ere, simple gauza bat egin daiteke hori saihesteko

219
00:11:18,000 --> 00:11:21,000
besterik ez ausaz nahastu sarrerako balioak.

220
00:11:21,000 --> 00:11:26,000
Oso nekez da aukera ausazko zenbakien zerrenda nahastu bat ordenatuko da.

221
00:11:26,000 --> 00:11:29,000
Kasu bada, casinos ez litzateke enpresa egonaldi luzea.

222
00:11:29,000 --> 00:11:31,000
>> Hor aukera izango duzu.

223
00:11:31,000 --> 00:11:34,000
Bilatzeko bilaketa bitarra eta bitarra zuhaitz buruz gaur egun ezagutzen duzu.

224
00:11:34,000 --> 00:11:36,000
Patrick Schmid naiz, eta hau da CS50.

225
00:11:36,000 --> 00:11:38,000
[CS50.TV]

226
00:11:38,000 --> 00:11:43,000
One bistako zerrenda eskaneatuko litzateke ... [beep]

227
00:11:43,000 --> 00:11:46,000
... Elementu kopurua ... Bai

228
00:11:46,000 --> 00:11:50,000
[Barreak]

229
00:11:50,000 --> 00:11:55,000
... 234 ... augh nodo bidaltzeko.

230
00:11:55,000 --> 00:11:58,000
>> Yay! Hori izan zen