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

2
00:00:02,000 --> 00:00:04,000
[Patrick Schmid - Inivèsite Harvard]

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

4
00:00:07,000 --> 00:00:09,000
>> Si mwen te ban nou yon lis de Disney non karaktè yo nan lòd alfabetik

5
00:00:09,000 --> 00:00:11,000
epi li te mande ou jwenn Mickey Mouse,

6
00:00:11,000 --> 00:00:13,000
ki jan ou ta ale sou fè sa a?

7
00:00:13,000 --> 00:00:15,000
Youn nan fason evidan ta dwe analysis lis la depi nan konmansman an

8
00:00:15,000 --> 00:00:18,000
epi tcheke chak non yo wè si li nan Mickey.

9
00:00:18,000 --> 00:00:22,000
Men, pandan w ap li geladen, Alice, Ariel, ak pou fè,

10
00:00:22,000 --> 00:00:25,000
ou pral byen vit reyalize ke kòmanse an de sou devan lis la pa te yon bon lide.

11
00:00:25,000 --> 00:00:29,000
Okay, petèt ou ta dwe kòmanse travay bak soti nan nan fen lis la.

12
00:00:29,000 --> 00:00:33,000
Koulye a, ou li Tarzan, pikur, nèj Blan, ak pou fè.

13
00:00:33,000 --> 00:00:36,000
Toujou, sa a pa sanble tankou pi bon fason yo ale sou li.

14
00:00:36,000 --> 00:00:38,000
>> Oke, yon lòt fason ke ou ta ka ale sou fè sa se pou yo eseye etwat desann

15
00:00:38,000 --> 00:00:41,000
lis la nan non ki di ou gen fè yon gade nan.

16
00:00:41,000 --> 00:00:43,000
Depi ou konnen yo ke yo se nan òd alfabetik,

17
00:00:43,000 --> 00:00:45,000
ou ta ka jis gade nan non yo nan mitan an nan lis la

18
00:00:45,000 --> 00:00:49,000
epi tcheke si Mickey Mouse se anvan oswa apre sa a non.

19
00:00:49,000 --> 00:00:51,000
Gade nan non an dènye dezyèm kolòn nan

20
00:00:51,000 --> 00:00:54,000
ou ta reyalize ke M pou Mickey vin apre J pou Jasmine,

21
00:00:54,000 --> 00:00:57,000
konsa ou ta tou senpleman inyore pwemye mwatye nan lis la.

22
00:00:57,000 --> 00:00:59,000
Lè sa a, ou ta pwobableman gade nan tèt la nan dènye kolòn nan

23
00:00:59,000 --> 00:01:02,000
ak wè ke li kòmanse ak Rapunzel.

24
00:01:02,000 --> 00:01:06,000
Mickey vini anvan Rapunzel; sanble nou ka inyore dènye kolòn nan kòm byen.

25
00:01:06,000 --> 00:01:08,000
Kontinye estrateji rechèch la, ou pral byen vit wè ke Mickey

26
00:01:08,000 --> 00:01:11,000
se nan pwemye mwatye nan lis la rete nan non

27
00:01:11,000 --> 00:01:14,000
epi finalman jwenn Mickey kache ant mèrlen ak Minnie.

28
00:01:14,000 --> 00:01:17,000
>> Ki sa ou jis te fè fondamantalman binè rechèch.

29
00:01:17,000 --> 00:01:22,000
Kòm non sa implique, li fè chache estrateji li yo nan yon kesyon binè.

30
00:01:22,000 --> 00:01:24,000
Ki sa sa vle di?

31
00:01:24,000 --> 00:01:27,000
Oke, bay yon lis Ranje atik, algorithm nan rechèch binè pran yon desizyon binè -

32
00:01:27,000 --> 00:01:33,000
gòch la oswa dwa, pi gran pase oswa mwens pase, lòd avèk lèt ​​alfabè anvan oswa apre - nan chak pwen.

33
00:01:33,000 --> 00:01:35,000
Kounye a ke nou gen yon non ki ale ansanm ak sa a algorithm rechèch,

34
00:01:35,000 --> 00:01:38,000
kite pou yo gade nan yon lòt egzanp, men fwa sa a ak yon lis Ranje chif yo.

35
00:01:38,000 --> 00:01:43,000
Di nou ap chèche pou yon nimewo pou la 144 nan lis sa a nan Ranje chif yo.

36
00:01:43,000 --> 00:01:46,000
Jis tankou anvan, nou jwenn nimewo a ki nan menm nan mitan yo -

37
00:01:46,000 --> 00:01:50,000
ki nan ka sa a se 13 - ak wè si 144 se pi gran pase oswa mwens pase 13.

38
00:01:50,000 --> 00:01:54,000
Depi li a byen klè pi gran pase 13, nou ka inyore tout bagay ki se 13 oswa mwens

39
00:01:54,000 --> 00:01:57,000
ak jis konsantre sou mwatye nan rete yo.

40
00:01:57,000 --> 00:01:59,000
Depi nou kounye a gen yon nimewo menm nan atik kite,

41
00:01:59,000 --> 00:02:01,000
nou tou senpleman chwazi yon chif ki pi pre mitan yo.

42
00:02:01,000 --> 00:02:03,000
Nan ka sa a nou chwazi 55.

43
00:02:03,000 --> 00:02:06,000
Nou te ka genyen menm jan fasil chwazi 89.

44
00:02:06,000 --> 00:02:11,000
Oke. Yon fwa ankò, 144 se pi wo pase 55, konsa nou ale nan bò dwat la.

45
00:02:11,000 --> 00:02:14,000
Erezman pou nou, nimewo nan mitan pwochen se 144,

46
00:02:14,000 --> 00:02:16,000
yon sèl nan nou ap chèche pou.

47
00:02:16,000 --> 00:02:21,000
Se konsa, yo nan lòd jwenn 144 lè l sèvi avèk yon rechèch binè, nou ap kapab jwenn li nan se sèlman 3 etap.

48
00:02:21,000 --> 00:02:24,000
Si nou ta te itilize lineyè rechèch isit la, li ta yo te pran nou 12 etap.

49
00:02:24,000 --> 00:02:28,000
Kòm yon kesyon de reyalite, depi metòd sa a rechèch mwatye nimewo a nan atik

50
00:02:28,000 --> 00:02:31,000
li gen fè yon gade nan nan chak etap, li pral jwenn atik la li se pou chèche

51
00:02:31,000 --> 00:02:35,000
nan sou boutèy la, ki kantite bagay ki nan lis la.

52
00:02:35,000 --> 00:02:37,000
Kounye a ke nou te wè 2 egzanp, kite a pran yon gade nan

53
00:02:37,000 --> 00:02:41,000
kèk pseudocode pou yon fonksyon repetitif ki aplike rechèch binè.

54
00:02:41,000 --> 00:02:44,000
Kòmanse nan tèt la, nou wè ke nou gen sa yo jwenn yon fonksyon ki pran 4 agiman:

55
00:02:44,000 --> 00:02:47,000
kle yo, etalaj, min, ak max.

56
00:02:47,000 --> 00:02:51,000
Kle a se nimewo a ke nou ap chèche pou, se konsa 144 nan egzanp lan anvan yo.

57
00:02:51,000 --> 00:02:54,000
Etalaj se lis la nan nimewo ke nou ap chèche.

58
00:02:54,000 --> 00:02:57,000
Min ak max se endis yo nan pozisyon yo minimòm ak kantite maksimòm

59
00:02:57,000 --> 00:02:59,000
kounye a ke nou ap chèche a.

60
00:02:59,000 --> 00:03:03,000
Se konsa, lè nou kòmanse, min yo pral zewo ak max pral endèks la maksimòm de etalaj la.

61
00:03:03,000 --> 00:03:07,000
Kòm nou etwat rechèch la desann, nou pral mete ajou min ak max

62
00:03:07,000 --> 00:03:10,000
yo dwe jis ranje a ke nou toujou ap chèche pous

63
00:03:10,000 --> 00:03:12,000
>> Se pou nou Sote ale nan Pati a enteresan premye.

64
00:03:12,000 --> 00:03:14,000
Premye bagay nou fè se jwenn pwen milye a,

65
00:03:14,000 --> 00:03:19,000
endèks la ki se mwatye ant min a ak max nan etalaj la ke nou yo toujou ap konsidere.

66
00:03:19,000 --> 00:03:22,000
Lè sa a, nou gade nan valè a nan etalaj la nan ki kote pwen milye

67
00:03:22,000 --> 00:03:25,000
ak wè si nimewo a ke nou ap chèche pou se mwens pase sa kle.

68
00:03:25,000 --> 00:03:27,000
Si nimewo a nan pozisyon sa ki mwens lan,

69
00:03:27,000 --> 00:03:31,000
Lè sa a, sa vle di li kle a se pi gwo pase tout chif nan kite nan pozisyon sa.

70
00:03:31,000 --> 00:03:33,000
Se konsa, nou ka rele binè fonksyon rechèch ankò,

71
00:03:33,000 --> 00:03:36,000
men fwa sa a mete ajou min a ak paramèt max li jis mwatye nan

72
00:03:36,000 --> 00:03:40,000
ki pi gran pase oswa egal a valè a nou jis gade.

73
00:03:40,000 --> 00:03:44,000
Nan lòt men an, si kle a se mwens pase kantite a nan pwen milye aktyèl la nan etalaj la,

74
00:03:44,000 --> 00:03:47,000
nou vle pou yo ale nan bò gòch la ak inyore tout nonb ki se pi plis la.

75
00:03:47,000 --> 00:03:52,000
Yon fwa ankò, nou rele rechèch binè men fwa sa a ak ranje nan min ak max Updated

76
00:03:52,000 --> 00:03:54,000
genyen ladan yo jis mwatye nan pi ba yo.

77
00:03:54,000 --> 00:03:57,000
Si valè a nan pwen milye aktyèl la nan etalaj la se pa ni

78
00:03:57,000 --> 00:04:01,000
pi gwo pase ni pi piti pase kle a, lè sa a li dwe egal a kle a.

79
00:04:01,000 --> 00:04:05,000
Kidonk, nou ka tou senpleman tounen endèks pwen milye a, kounye a, epitou n ap fè a.

80
00:04:05,000 --> 00:04:09,000
Finalman, chèk sa-a isit la se pou ka a nimewo sa a nan

81
00:04:09,000 --> 00:04:11,000
se pa aktyèlman nan etalaj la nan nimewo nou ap chèche.

82
00:04:11,000 --> 00:04:14,000
Si endèks la maksimòm de ranje a ke nou ap chèche pou

83
00:04:14,000 --> 00:04:17,000
se tout tan mwens pase minimòm nan, ki vle di ke nou te ale twò lwen.

84
00:04:17,000 --> 00:04:20,000
Depi nimewo a pa t 'nan etalaj la D', nou tounen -1

85
00:04:20,000 --> 00:04:24,000
pou montre pou ki pa gen anyen te jwenn.

86
00:04:24,000 --> 00:04:26,000
>> Ou ka gen remake ke pou sa a algorithm nan travay,

87
00:04:26,000 --> 00:04:28,000
lis la nan nimerik ki gen yo dwe klase.

88
00:04:28,000 --> 00:04:31,000
Nan lòt mo, nou ka sèlman jwenn 144 lè l sèvi avèk rechèch binè

89
00:04:31,000 --> 00:04:34,000
si tout nimewo yo ap bay lòd soti nan pi ba pi gwo a.

90
00:04:34,000 --> 00:04:38,000
Si sa pa t ka a, nou pa ta dwe kapab eskli mwatye nan nimewo ki nan chak etap.

91
00:04:38,000 --> 00:04:40,000
Se konsa, nou gen 2 opsyon.

92
00:04:40,000 --> 00:04:43,000
Swa nou ka pran yon lis klase epi klase l 'devan lè l sèvi avèk binè rechèch,

93
00:04:43,000 --> 00:04:48,000
oubyen nou ka asire w ke se lis la nan nimewo Ranje jan nou ajoute nimewo li.

94
00:04:48,000 --> 00:04:50,000
Se konsa,, olye pou yo jis Fouye lè nou gen nan rechèch,

95
00:04:50,000 --> 00:04:53,000
poukisa pa kenbe lis la Ranje nan tout fwa?

96
00:04:53,000 --> 00:04:57,000
>> Youn nan fason yo kenbe yon lis nimewo Ranje anmenm tan li ap pèmèt

97
00:04:57,000 --> 00:04:59,000
youn nan ajoute oswa deplase nimewo nan lis sa a

98
00:04:59,000 --> 00:05:02,000
se lè yo itilize yon bagay yo rele yon pyebwa rechèch binè.

99
00:05:02,000 --> 00:05:05,000
Yon pye bwa rechèch binè se yon estrikti done ki gen 3 pwopriyete yo.

100
00:05:05,000 --> 00:05:09,000
Premyèman, subtree gòch la nan nenpòt ki ne gen valè sèlman ki gen mwens pase

101
00:05:09,000 --> 00:05:11,000
oswa egal a valè ne la.

102
00:05:11,000 --> 00:05:15,000
Dezyèmman, dwa subtree a nan yon ne sèlman gen valè ki pi gran pase

103
00:05:15,000 --> 00:05:17,000
oswa egal a valè ne la.

104
00:05:17,000 --> 00:05:20,000
, E finalman, tou de agoch ​​ak adwat subtrees yo nan tout nœuds

105
00:05:20,000 --> 00:05:23,000
yo tou pye bwa rechèch binè.

106
00:05:23,000 --> 00:05:26,000
Se pou yo gade nan yon egzanp ak nonb yo menm nou itilize pi bonè.

107
00:05:26,000 --> 00:05:30,000
Pou moun nan nou ki pa janm wè yon pye bwa syans konpitè anvan,

108
00:05:30,000 --> 00:05:34,000
kite m 'kòmanse pa di ou ke yon pye bwa syans konpitè ap grandi bès.

109
00:05:34,000 --> 00:05:36,000
Wi, kontrèman ak pye bwa ou yo abitye,

110
00:05:36,000 --> 00:05:38,000
rasin nan yon pyebwa syans òdinatè se nan tèt la,

111
00:05:38,000 --> 00:05:41,000
Se ak fèy li yo se nan pati anba nan.

112
00:05:41,000 --> 00:05:45,000
Chak bwat ti kras rele yon ne, ak nœuds yo yo ki konekte nan chak lòt nan bor.

113
00:05:45,000 --> 00:05:48,000
Se konsa, rasin lan nan pyebwa sa a se yon valè ne ak valè a 13,

114
00:05:48,000 --> 00:05:52,000
ki te gen 2 timoun nœuds avèk valè ki 5 ak 34.

115
00:05:52,000 --> 00:05:57,000
Yon subtree se pyebwa sa a, ki te fòme yo senpleman gade sou yon seksyon nan pye bwa a tout antye.

116
00:05:57,000 --> 00:06:03,000
>> Pou egzanp, subtree gòch la nan 3 a ne se pye bwa a ki te kreye pa 0 nœuds yo, 1, ak 2.

117
00:06:03,000 --> 00:06:06,000
Se konsa, si nou tounen nan pwopriyete yo nan yon pye bwa rechèch binè,

118
00:06:06,000 --> 00:06:09,000
nou wè ke chak ne nan pye bwa a koresponn nan tout pwopriyete 3, savwa,

119
00:06:09,000 --> 00:06:15,000
subtree gòch la sèlman gen valè moral ki te gen mwens pase oswa egal a valè ne a;

120
00:06:15,000 --> 00:06:16,000
dwa subtree nan tout nœuds

121
00:06:16,000 --> 00:06:19,000
sèlman gen valè ki pi gran pase oswa egal a valè ne a; ak

122
00:06:19,000 --> 00:06:25,000
tou de agoch ​​ak adwat subtrees nan tout nœuds tou yo se pye bwa rechèch binè.

123
00:06:25,000 --> 00:06:28,000
Malgre ke pye bwa sa a parèt diferan, sa a se yon binè pyebwa ki valab rechèch

124
00:06:28,000 --> 00:06:30,000
pou mete nan menm nan nimewo yo.

125
00:06:30,000 --> 00:06:32,000
Kòm yon kesyon de reyalite, gen anpil fason posib ke ou kapab kreye

126
00:06:32,000 --> 00:06:35,000
yon valab rechèch binè pyebwa soti nan nimewo sa yo.

127
00:06:35,000 --> 00:06:38,000
Oke, kite la tounen nan youn nan premye nou te kreye.

128
00:06:38,000 --> 00:06:40,000
Se konsa, sa nou ka fè ak sa yo pyebwa yo?

129
00:06:40,000 --> 00:06:44,000
Oke, nou ka anpil tou senpleman jwenn valè yo minimòm ak maksimòm.

130
00:06:44,000 --> 00:06:46,000
Valè yo minimòm ka jwenn pa toujou ale nan bò gòch la

131
00:06:46,000 --> 00:06:48,000
jiskaske pa gen okenn plis nœuds nan vizit.

132
00:06:48,000 --> 00:06:53,000
Kontrèman, yo jwenn yon sèl nan maksimòm tou senpleman jis ale desann sou bò dwat la nan chak fwa.

133
00:06:54,000 --> 00:06:56,000
>> Jwenn nenpòt kantite lòt ki pa minimòm la oswa maksimòm la

134
00:06:56,000 --> 00:06:58,000
se jis kòm fasil.

135
00:06:58,000 --> 00:07:00,000
Di nou ap chèche pou yon nimewo pou la 89.

136
00:07:00,000 --> 00:07:03,000
Nou tou senpleman tcheke valè chak ne epi ale nan bò gòch la oswa dwa,

137
00:07:03,000 --> 00:07:06,000
depann sou si valè ne a se mwens pase oswa pi gran pase

138
00:07:06,000 --> 00:07:08,000
yon sèl nan nou ap chèche pou.

139
00:07:08,000 --> 00:07:11,000
Se konsa,, kòmanse nan rasin lan nan 13, nou wè ke 89 se pi gwo a,

140
00:07:11,000 --> 00:07:13,000
epi pou nou ale nan bò dwat la.

141
00:07:13,000 --> 00:07:16,000
Lè sa a, nou wè ne la pou 34, epi ankò nou ale a dwat la.

142
00:07:16,000 --> 00:07:20,000
89 se toujou pi wo pase 55, se konsa nou kontinye ale nan bò dwat la.

143
00:07:20,000 --> 00:07:24,000
Nou Lè sa a, vini ak yon ne ak valè a nan 144 epi ale nan bò gòch li.

144
00:07:24,000 --> 00:07:26,000
Lo men koulye a, 89 se dwa la.

145
00:07:26,000 --> 00:07:31,000
>> Yon lòt bagay ke nou ka fè se enprime soti tout chif a fè yon parcourt inorder.

146
00:07:31,000 --> 00:07:35,000
Yon parcourt inorder vle di enprime tout bagay soti nan subtree gòch la

147
00:07:35,000 --> 00:07:37,000
ki te swiv pa enprime ne a li menm

148
00:07:37,000 --> 00:07:40,000
ak Lè sa a, ki te swiv pa enprime tout bagay soti nan subtree a dwat.

149
00:07:40,000 --> 00:07:43,000
Pou egzanp, kite a pran pi renmen pyebwa binè nou rechèch

150
00:07:43,000 --> 00:07:46,000
epi enprime soti chif yo nan Ranje lòd.

151
00:07:46,000 --> 00:07:49,000
Nou kòmanse nan rasin lan 13 la, men anvan enprime 13 nou dwe enprime soti

152
00:07:49,000 --> 00:07:51,000
tout sa ki nan subtree gòch la.

153
00:07:51,000 --> 00:07:55,000
Se konsa, nou ale nan 5. Nou toujou gen yo ale pi fon desann nan pyebwa a jiskaske nou jwenn ne nan bò goch la nèt,

154
00:07:55,000 --> 00:07:57,000
ki se zewo.

155
00:07:57,000 --> 00:08:00,000
Apre enprime zewo, nou tounen jiska 1 an epi enprime ki deyò.

156
00:08:00,000 --> 00:08:03,000
Lè sa a, nou ale nan subtree nan dwa, ki se 2, epi enprime ki deyò.

157
00:08:03,000 --> 00:08:05,000
Kounye a ke nou ap fè ak ki subtree,

158
00:08:05,000 --> 00:08:07,000
nou ka ale tounen moute nan 3 a ak enprime li.

159
00:08:07,000 --> 00:08:11,000
Kontinye tounen moute, nou enprime 5 an ak Lè sa a, 8 la.

160
00:08:11,000 --> 00:08:13,000
Kounye a ke nou te deja konplete tout la kite subtree,

161
00:08:13,000 --> 00:08:17,000
nou ka enprime soti 13 an ak kòmanse travay sou subtree a dwat.

162
00:08:17,000 --> 00:08:21,000
Nou hop desann nan 34, men anvan enprime 34 nou dwe enprime soti subtree gòch li yo.

163
00:08:21,000 --> 00:08:27,000
Se konsa, nou enprime soti 21; Lè sa a, nou jwenn yo enprime soti 34 ak vizite subtree dwa li yo.

164
00:08:27,000 --> 00:08:31,000
Depi 55 pa gen okenn subtree gòch, nou enprime li epi yo kontinye sou subtree dwa li yo.

165
00:08:31,000 --> 00:08:36,000
144 a gen yon subtree agoch, epi pou nou enprime soti 89 an, ki te swiv pa 144 la,

166
00:08:36,000 --> 00:08:39,000
epi finalman ne nan dwa-pi fò nan 233.

167
00:08:39,000 --> 00:08:44,000
Genyen ou genyen li; tout nimewo yo ap enprime deyò nan lòd soti nan pi ba pi gwo a.

168
00:08:44,000 --> 00:08:47,000
>> Ajoute yon bagay bò pyebwa ki se relativman fèt san doulè kòm byen.

169
00:08:47,000 --> 00:08:51,000
Tout sa nou dwe fè se asire w ke nou swiv 3 pwopriyete binè pyebwa rechèch

170
00:08:51,000 --> 00:08:53,000
ak Lè sa a, insert valè a kote ki gen espas.

171
00:08:53,000 --> 00:08:55,000
Se pou nou di nou vle insert valè a 7.

172
00:08:55,000 --> 00:08:58,000
Depi 7 se mwens pase 13, nou ale nan bò gòch li.

173
00:08:58,000 --> 00:09:01,000
Men, li la pi gran pase 5, konsa nou Traverse a dwat la.

174
00:09:01,000 --> 00:09:04,000
Depi li nan mwens pase 8 ak 8 se yon ne fèy, nou ajoute 7 a timoun nan gòch nan 8.

175
00:09:04,000 --> 00:09:09,000
Vwala! Nou te ajoute yon nimewo bò pyebwa rechèch binè nou an.

176
00:09:09,000 --> 00:09:12,000
>> Si nou ka ajoute bagay sa yo, nou pi bon kapab efase bagay sa yo kòm byen.

177
00:09:12,000 --> 00:09:14,000
Malerezman pou nou, efase se yon ti jan ti kras pi plis konplike -

178
00:09:14,000 --> 00:09:16,000
pa anpil, men jis yon ti jan.

179
00:09:16,000 --> 00:09:18,000
Gen 3 senaryo diferan ke nou gen yo konsidere

180
00:09:18,000 --> 00:09:21,000
lè efase eleman soti nan pyebwa rechèch binè.

181
00:09:21,000 --> 00:09:24,000
Premyèman, ka a pi fasil se ke eleman an se yon ne fèy.

182
00:09:24,000 --> 00:09:27,000
Nan ka sa a, nou tou senpleman efase l ', li ale nan ak biznis nou an.

183
00:09:27,000 --> 00:09:30,000
Di nou vle efase 7 a ke nou jis te ajoute.

184
00:09:30,000 --> 00:09:34,000
Bon, nou tou senpleman jwenn li, retire li, epi ki nan li.

185
00:09:35,000 --> 00:09:37,000
Ka a pwochen se si ne a gen sèlman 1 timoun.

186
00:09:37,000 --> 00:09:40,000
Isit la nou kapab efase ne la, men nou premye dwe asire nou ke

187
00:09:40,000 --> 00:09:42,000
konekte subtree sa a, ki kounye a kite parentless

188
00:09:42,000 --> 00:09:44,000
bay paran an nan ne an nou jis efase.

189
00:09:44,000 --> 00:09:47,000
Di nou vle efase 3 fwi pyebwa nou yo.

190
00:09:47,000 --> 00:09:50,000
Nou pran eleman nan pitit la ki ne epi mete li ak paran an sou ne a.

191
00:09:50,000 --> 00:09:54,000
Nan ka sa a, nou ap kounye a atache 1 an a 5 an.

192
00:09:54,000 --> 00:09:57,000
Sa a ap travay san yo pa yon pwoblèm paske nou konnen, dapre pwopriyete a pyebwa rechèch binè,

193
00:09:57,000 --> 00:10:01,000
ke tout bagay nan subtree gòch la nan 3 te mwens pase 5.

194
00:10:01,000 --> 00:10:05,000
Kounye a ke nan 3 subtree se pran swen nan, nou ka efase li.

195
00:10:05,000 --> 00:10:08,000
Ka a twazyèm ak dènye ki pi konplèks la.

196
00:10:08,000 --> 00:10:11,000
Sa a se ka a lè ne a nou vle efase gen 2 timoun yo.

197
00:10:11,000 --> 00:10:15,000
Yo nan lòd yo fè sa, nou premye gen jwenn ne a ki gen valè nan pwochen pi gwo,

198
00:10:15,000 --> 00:10:18,000
swap de a, ak Lè sa a, efase ne a nan kesyon.

199
00:10:18,000 --> 00:10:22,000
Avi ne a ki gen pwochen valè a pi gwo pa ka gen 2 timoun pwòp tèt li

200
00:10:22,000 --> 00:10:26,000
depi timoun gòch li yo ta dwe yon kandida pi bon pou pi gwo kap vini an.

201
00:10:26,000 --> 00:10:30,000
Se poutèt sa, efase yon ne ak 2 timoun MONTAN LAJAN échanjé nan 2 nœuds,

202
00:10:30,000 --> 00:10:33,000
ak Lè sa a, efase se lantremiz 1 nan 2 règ yo susmansyone.

203
00:10:33,000 --> 00:10:37,000
Pou egzanp, kite a di nou vle efase ne nan rasin, 13.

204
00:10:37,000 --> 00:10:39,000
Premye bagay nou fè se nou jwenn pwochen valè a pi gwo nan pye bwa a

205
00:10:39,000 --> 00:10:41,000
ki, nan ka sa a, se 21.

206
00:10:41,000 --> 00:10:46,000
Nou Lè sa a, boukante nœuds yo 2 yo, ki fè 13 yon fèy ak 21 ne nan gwoup santral.

207
00:10:46,000 --> 00:10:49,000
Koulye a, nou ka senpleman efase 13.

208
00:10:50,000 --> 00:10:53,000
>> Kòm mansyone pi bonè, gen anpil fason posib fè yon binè valid pyebwa rechèch.

209
00:10:53,000 --> 00:10:56,000
Malerezman pou nou, gen kèk ki pi mal pase lòt moun.

210
00:10:56,000 --> 00:10:59,000
Pou egzanp, sa ki pase lè nou bati yon pyebwa rechèch binè

211
00:10:59,000 --> 00:11:01,000
nan yon lis Ranje nan nimewo?

212
00:11:01,000 --> 00:11:04,000
Tout nimewo yo se jis ajoute sou bò dwat la nan chak etap.

213
00:11:04,000 --> 00:11:06,000
Lè nou vle pou fè rechèch pou yon nonb,

214
00:11:06,000 --> 00:11:08,000
nou pa gen okenn chwa men se sèlman fè yon gade nan dwa a nan chak etap.

215
00:11:08,000 --> 00:11:11,000
Sa a se pa pi bon pase rechèch lineyè nan tout.

216
00:11:11,000 --> 00:11:13,000
Malgre ke nou pa pral kouvri yo isit la, gen lòt, plis konplèks,

217
00:11:13,000 --> 00:11:16,000
done estrikti ki asire w ke sa pa rive.

218
00:11:16,000 --> 00:11:18,000
Sepandan, yon sèl bagay senp ki kapab fè pou fè pou evite sa a se

219
00:11:18,000 --> 00:11:21,000
jis chefeul owaza valè yo kontribisyon.

220
00:11:21,000 --> 00:11:26,000
Li nan trè fasil ki pa chans o aza se yon lis shuffled nan nimewo Ranje.

221
00:11:26,000 --> 00:11:29,000
Si sa a yo te ka a, kazino pa t 'vle rete nan biznis pou lontan.

222
00:11:29,000 --> 00:11:31,000
>> Genyen ou genyen li.

223
00:11:31,000 --> 00:11:34,000
Ou kounye a konnen sou rechèch binè ak pye bwa rechèch binè.

224
00:11:34,000 --> 00:11:36,000
Mwen Patrick Schmid, e sa se CS50.

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

226
00:11:38,000 --> 00:11:43,000
Youn nan fason evidan ta dwe analysis lis la soti nan ... [BEEP]

227
00:11:43,000 --> 00:11:46,000
... Nimewo a nan atik ... YEP

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

229
00:11:50,000 --> 00:11:55,000
... Afiche ne nan 234 ... augh.

230
00:11:55,000 --> 00:11:58,000
>> Ye! Se te -