1
00:00:00,000 --> 00:00:02,000
[Powered by Google Translate] [Fittex Binarju]

2
00:00:02,000 --> 00:00:04,000
[Patrick Schmid - Università ta 'Harvard]

3
00:00:04,000 --> 00:00:07,000
[Dan huwa CS50. - CS50.TV]

4
00:00:07,000 --> 00:00:09,000
>> Jekk jiena ħadt lista ta 'ismijiet karattru Disney f'ordni alfabetiku

5
00:00:09,000 --> 00:00:11,000
u talab li inti ssib Mickey Mouse,

6
00:00:11,000 --> 00:00:13,000
kif tista 'tmur dwar kif isir dan?

7
00:00:13,000 --> 00:00:15,000
Mod wieħed ovvju ikun li skennjati l-lista mill-bidu

8
00:00:15,000 --> 00:00:18,000
u jivverifikaw kull isem biex tara jekk huwa Mickey.

9
00:00:18,000 --> 00:00:22,000
Imma kif inti taqra Aladdin, Alice, Ariel, u oħrajn,

10
00:00:22,000 --> 00:00:25,000
inti ser malajr tirrealizza li jibdew fuq quddiem tal-lista ma tkunx idea tajba.

11
00:00:25,000 --> 00:00:29,000
Okay, forsi inti għandek tibda taħdem lura mill-aħħar tal-lista.

12
00:00:29,000 --> 00:00:33,000
Issa inti taqra Tarzan, stitch, Snow White, u oħrajn.

13
00:00:33,000 --> 00:00:36,000
Still, dan ma jidher l-aħjar mod biex imorru dwar dan.

14
00:00:36,000 --> 00:00:38,000
>> Ukoll, ieħor mod li inti tista 'tmur dwar kif isir dan huwa li tipprova biex iċekknu

15
00:00:38,000 --> 00:00:41,000
l-lista ta 'ismijiet li inti għandek tfittex fil.

16
00:00:41,000 --> 00:00:43,000
Peress li inti taf li dawn huma fl-ordni alfabetiku,

17
00:00:43,000 --> 00:00:45,000
inti tista 'biss tħares lejn l-ismijiet fin-nofs tal-lista

18
00:00:45,000 --> 00:00:49,000
u jivverifika jekk Mickey Mouse tkun qabel jew wara dan l-isem.

19
00:00:49,000 --> 00:00:51,000
Ħarsa lejn l-isem aħħar fit-tieni kolonna

20
00:00:51,000 --> 00:00:54,000
youd tirrealizza li M għal Mickey wasal wara J għal Jasmine,

21
00:00:54,000 --> 00:00:57,000
hekk youd sempliċiment tinjora l-ewwel nofs tal-lista.

22
00:00:57,000 --> 00:00:59,000
Imbagħad youd probabilment tħares lejn il-quċċata tal-aħħar kolonna

23
00:00:59,000 --> 00:01:02,000
u tara li jibda bil Rapunzel.

24
00:01:02,000 --> 00:01:06,000
Mickey jasal quddiem Rapunzel; qisu nistgħu ninjoraw l-aħħar kolonna ukoll.

25
00:01:06,000 --> 00:01:08,000
Jitkompla l-istrateġija tat-tiftix, inti ser malajr tara li Mickey

26
00:01:08,000 --> 00:01:11,000
huwa fl-ewwel nofs tal-lista li jifdal ta 'l-ismijiet

27
00:01:11,000 --> 00:01:14,000
u finalment issib Mickey ħabi bejn Merlin u Minnie.

28
00:01:14,000 --> 00:01:17,000
>> Dak li inti biss ma kien tfittxija bażikament binarja.

29
00:01:17,000 --> 00:01:22,000
Kif dan l-isem jimplika, li jwettaq l-istrateġija tiftix tagħha fi kwistjoni binarja.

30
00:01:22,000 --> 00:01:24,000
Xi jfisser dan?

31
00:01:24,000 --> 00:01:27,000
Ukoll, tingħata lista ta 'oġġetti magħżula, l-algoritmu tfittxija binarja jagħmel deċiżjoni binarja -

32
00:01:27,000 --> 00:01:33,000
lemin jew xellug, akbar minn jew inqas minn, alfabetikament qabel jew wara - f'kull punt.

33
00:01:33,000 --> 00:01:35,000
Issa li għandna isem li jmur flimkien ma 'dan algoritmu tfittxija,

34
00:01:35,000 --> 00:01:38,000
ejja nħarsu lejn eżempju ieħor, iżda din id-darba ma 'lista ta' numri magħżula.

35
00:01:38,000 --> 00:01:43,000
Say aħna qegħdin ifittxu l-għadd 144 f'din il-lista ta 'numri magħżula.

36
00:01:43,000 --> 00:01:46,000
Eżatt bħal qabel, insibu n-numru li fil-nofs -

37
00:01:46,000 --> 00:01:50,000
li f'dan il-każ huwa 13 - u ara jekk 144 ikun ikbar jew inqas minn 13.

38
00:01:50,000 --> 00:01:54,000
Peress li huwa ċar ikbar minn 13, nistgħu ninjoraw dak kollu li huwa 13 jew anqas

39
00:01:54,000 --> 00:01:57,000
u biss jikkonċentraw fuq il-nofs l-ieħor.

40
00:01:57,000 --> 00:01:59,000
Peress li issa għandna anke numru ta 'oġġetti tax-xellug,

41
00:01:59,000 --> 00:02:01,000
aħna sempliċiment jagħżlu numru li huwa qrib il-linji.

42
00:02:01,000 --> 00:02:03,000
F'dan il-każ nagħżlu 55.

43
00:02:03,000 --> 00:02:06,000
Aħna setgħet daqstant faċilment magħżula 89.

44
00:02:06,000 --> 00:02:11,000
Okay. Għal darb'oħra, 144 huwa akbar minn 55, hekk immorru lejn il-lemin.

45
00:02:11,000 --> 00:02:14,000
Fortunatament għalina, in-numru tan-nofs li jmiss huwa 144,

46
00:02:14,000 --> 00:02:16,000
l-waħda aħna qed tfittex.

47
00:02:16,000 --> 00:02:21,000
Allura biex isibu 144 użu ta 'tfittxija binarja, aħna kapaċi li ssib fil biss 3 passi.

48
00:02:21,000 --> 00:02:24,000
Jekk aħna użaw tfittxija lineari hawn, kien jieħu us 12 passi.

49
00:02:24,000 --> 00:02:28,000
Bħala kwistjoni ta 'fatt, peress li dan il-metodu tfittxija nofsijiet-numru ta' oġġetti

50
00:02:28,000 --> 00:02:31,000
hija għandha tħares lejn f'kull stadju, se ssib l-oġġett li qed tfittex

51
00:02:31,000 --> 00:02:35,000
f'madwar l-ġurnal tan-numru ta 'oġġetti fil-lista.

52
00:02:35,000 --> 00:02:37,000
Issa li aħna stajt tidher 2 eżempji, ejja tagħti ħarsa lejn

53
00:02:37,000 --> 00:02:41,000
xi pseudocode għal funzjoni rikursivi li timplimenta tfittxija binarja.

54
00:02:41,000 --> 00:02:44,000
Tibda fil-quċċata, naraw li għandna biex isibu funzjoni li jieħu 4 argumenti:

55
00:02:44,000 --> 00:02:47,000
, ewlenin array, min, u max.

56
00:02:47,000 --> 00:02:51,000
Il-muftieħ huwa n-numru li qed infittxu, hekk 144 fl-eżempju preċedenti.

57
00:02:51,000 --> 00:02:54,000
Array hija l-lista ta 'numri li aħna tiftix.

58
00:02:54,000 --> 00:02:57,000
Min u max huma l-indiċijiet tal-pożizzjonijiet minimi u massimi

59
00:02:57,000 --> 00:02:59,000
li aħna bħalissa tfittex fuq.

60
00:02:59,000 --> 00:03:03,000
Allura meta nibdew, min se jkun żero u max se jkun l-indiċi massimu tal-firxa.

61
00:03:03,000 --> 00:03:07,000
Kif aħna dejqa-tfittxija isfel, aħna se taġġorna min u max

62
00:03:07,000 --> 00:03:10,000
li jkun biss il-medda li għadna tfittex pulzieri

63
00:03:10,000 --> 00:03:12,000
>> Ejja skip għall-parti interessanti ewwel.

64
00:03:12,000 --> 00:03:14,000
L-ewwel ħaġa li għandna tagħmel hu li ssib l-punt fokali,

65
00:03:14,000 --> 00:03:19,000
l-indiċi li huwa fin-nofs bejn il-min u max ta 'l-array li għadna jikkunsidraw.

66
00:03:19,000 --> 00:03:22,000
Imbagħad aħna nħarsu lejn il-valur ta 'l-array f'dak il-post punt tan-nofs

67
00:03:22,000 --> 00:03:25,000
u ara jekk in-numru li qed infittxu huwa inqas minn dak ċavetta.

68
00:03:25,000 --> 00:03:27,000
Jekk in-numru f'dik il-pożizzjoni huwa inqas,

69
00:03:27,000 --> 00:03:31,000
allura dan ifisser il-muftieħ huwa akbar minn numri kollha lejn ix-xellug ta 'dik il-pożizzjoni.

70
00:03:31,000 --> 00:03:33,000
Allura nistgħu sejħa funzjoni ta 'tfittxija binarja mill-ġdid,

71
00:03:33,000 --> 00:03:36,000
iżda din id-darba l-aġġornament il-min u parametri max li taqra biss in-nofs

72
00:03:36,000 --> 00:03:40,000
li huwa ikbar minn jew ugwali għall-valur aħna biss ħares lejn.

73
00:03:40,000 --> 00:03:44,000
Min-naħa l-oħra, jekk il-muftieħ huwa anqas minn numru fil-punt tan-nofs attwali tal-firxa,

74
00:03:44,000 --> 00:03:47,000
irridu imorru lejn ix-xellug u jinjora numri kollha li huma akbar.

75
00:03:47,000 --> 00:03:52,000
Għal darb'oħra, nagħmlu sejħa tfittxija binarja iżda din id-darba mal-firxa ta 'min u max aġġornata

76
00:03:52,000 --> 00:03:54,000
li tinkludi biss l-nofs t'isfel.

77
00:03:54,000 --> 00:03:57,000
Jekk il-valur fil-punt tan-nofs attwali fil-firxa la

78
00:03:57,000 --> 00:04:01,000
akbar minn lanqas iżgħar minn l-ewlenin, allura għandu jkun ugwali għad-ċavetta.

79
00:04:01,000 --> 00:04:05,000
Għalhekk, nistgħu sempliċement lura l-indiċi punt fokali attwali, u aħna qed isir.

80
00:04:05,000 --> 00:04:09,000
Fl-aħħarnett, dan il-kontroll hawnhekk huwa għall-każ li n-numru

81
00:04:09,000 --> 00:04:11,000
ma tkunx attwalment fil-firxa ta 'numri aħna tiftix.

82
00:04:11,000 --> 00:04:14,000
Jekk l-indiċi massimu tal-grad li aħna qed ifittxu għall-

83
00:04:14,000 --> 00:04:17,000
huwa dejjem anqas mill-minimu, dan ifisser li aħna stajt marret wisq.

84
00:04:17,000 --> 00:04:20,000
Peress li n-numru ma kienx fil-firxa input, nerġgħu lura -1

85
00:04:20,000 --> 00:04:24,000
li jindika li xejn ma nstab.

86
00:04:24,000 --> 00:04:26,000
>> Inti jista 'jkollok ndunat li għal dan il-algoritmu li taħdem,

87
00:04:26,000 --> 00:04:28,000
il-lista ta 'numri għandha tkun magħżula.

88
00:04:28,000 --> 00:04:31,000
Fi kliem ieħor, nistgħu biss isibu 144 bl-użu tfittxija binarju

89
00:04:31,000 --> 00:04:34,000
jekk il-numri huma ordnati mill-iżgħar sa l-ogħla.

90
00:04:34,000 --> 00:04:38,000
Jekk dan ma jkunx il-każ, aħna mhux se tkun tista 'teskludi nofs il-numri f'kull pass.

91
00:04:38,000 --> 00:04:40,000
Allura aħna għandna 2 għażliet.

92
00:04:40,000 --> 00:04:43,000
Jew nistgħu nieħdu lista mhux magħżul u sort qabel tuża tfittxija binarja,

93
00:04:43,000 --> 00:04:48,000
jew nistgħu kun żgur li l-lista ta 'numri huwa magħżul kif aħna żid in-numri lilha.

94
00:04:48,000 --> 00:04:50,000
Għalhekk, minflok l-għażla biss meta għandna biex tfittex,

95
00:04:50,000 --> 00:04:53,000
għaliex ma żżomm il-lista magħżula fil-ħinijiet kollha?

96
00:04:53,000 --> 00:04:57,000
>> Mod wieħed biex iżommu lista ta 'numri magħżula filwaqt li fl-istess ħin jippermettu

97
00:04:57,000 --> 00:04:59,000
wieħed biex iżżid jew jiċċaqalqu numri minn din il-lista

98
00:04:59,000 --> 00:05:02,000
huwa bl-użu xi ħaġa imsejħa siġra tfittxija binarja.

99
00:05:02,000 --> 00:05:05,000
A siġra tfittxija binarju huwa struttura tad-data li għandha 3 proprjetajiet.

100
00:05:05,000 --> 00:05:09,000
L-ewwel, il-subtree xellug ta 'kwalunkwe node fih valuri biss li huma inqas minn

101
00:05:09,000 --> 00:05:11,000
jew ugwali għall-valur tal-node s.

102
00:05:11,000 --> 00:05:15,000
It-tieni nett, id-dritt subtree ta 'nodu fiha biss valuri li huma akbar minn

103
00:05:15,000 --> 00:05:17,000
jew ugwali għall-valur tal-node s.

104
00:05:17,000 --> 00:05:20,000
U, finalment, kemm il-subtrees xellug u lemin ta 'kull għoqiedi

105
00:05:20,000 --> 00:05:23,000
huma wkoll siġar tat-tiftix binarja.

106
00:05:23,000 --> 00:05:26,000
Ejja nħarsu lejn eżempju bl-istess numri aħna użati qabel.

107
00:05:26,000 --> 00:05:30,000
Għal dawk minnkom li qatt ma raw siġra xjenza tal-kompjuter qabel,

108
00:05:30,000 --> 00:05:34,000
let me tibda billi tghidlek li siġra xjenza tal-kompjuter tikber isfel.

109
00:05:34,000 --> 00:05:36,000
Iva, b'differenza siġar inti mdorri,

110
00:05:36,000 --> 00:05:38,000
l-għerq ta 'siġra xjenza tal-kompjuter hija fil-quċċata,

111
00:05:38,000 --> 00:05:41,000
u l-weraq huma fil-qiegħ.

112
00:05:41,000 --> 00:05:45,000
Kull kaxxa ftit jissejjaħ node, u l-lymph huma konnessi ma 'xulxin mill-truf.

113
00:05:45,000 --> 00:05:48,000
Allura l-għerq ta 'din is-siġra hija valur node mal-valur 13,

114
00:05:48,000 --> 00:05:52,000
li tkun 2 nodi tat-tfal mal-valuri 5 u 34.

115
00:05:52,000 --> 00:05:57,000
A subtree hi s-siġra li huwa ffurmat biss billi tħares lejn subsezzjoni tas-siġra kollu.

116
00:05:57,000 --> 00:06:03,000
>> Per eżempju, il-subtree xellug tal-magna 3 node huwa l-siġra maħluqa mill-lymph 0, 1, u 2.

117
00:06:03,000 --> 00:06:06,000
Għalhekk, jekk immorru lura għall-proprjetajiet ta 'siġra tfittxija binarju,

118
00:06:06,000 --> 00:06:09,000
naraw li kull node fil-siġra jikkonforma mal-proprjetajiet kollha 3, jiġifieri,

119
00:06:09,000 --> 00:06:15,000
the subtree xellug fih biss valuri li huma inqas minn jew ugwali għal valur tal-node ta;

120
00:06:15,000 --> 00:06:16,000
id-dritt subtree ta 'l-lymph

121
00:06:16,000 --> 00:06:19,000
fiha biss valuri li huma ikbar minn jew ugwali għall-valur tal-node-organizzazzjoni u

122
00:06:19,000 --> 00:06:25,000
subtrees kemm tax-xellug u lemin ta 'kull lymph wkoll huma siġar tat-tiftix binarja.

123
00:06:25,000 --> 00:06:28,000
Għalkemm din is-siġra jistenna differenti, din hija siġra valida tfittxija binarju

124
00:06:28,000 --> 00:06:30,000
għall-istess sett ta 'numri.

125
00:06:30,000 --> 00:06:32,000
Bħala kwistjoni ta 'fatt, hemm bosta modi possibbli li inti tista' toħloq

126
00:06:32,000 --> 00:06:35,000
validu binarja tfittxija siġra minn dawn in-numri.

127
00:06:35,000 --> 00:06:38,000
Ukoll, ejja mur lura għall-ewwel waħda ħloqna.

128
00:06:38,000 --> 00:06:40,000
Allura x'nistgħu nagħmlu ma 'dawn is-siġar?

129
00:06:40,000 --> 00:06:44,000
Well, nistgħu ħafna sempliċement issib il-valuri minimi u massimi.

130
00:06:44,000 --> 00:06:46,000
Il-valuri minimi tista 'tinstab billi dejjem tmur lejn ix-xellug

131
00:06:46,000 --> 00:06:48,000
sakemm ma jkunx hemm għoqiedi mhux aktar li jżuru.

132
00:06:48,000 --> 00:06:53,000
Bil-maqlub, biex isibu l-waħda massimu sempliċiment biss jinżel lejn il-lemin f'kull ħin.

133
00:06:54,000 --> 00:06:56,000
>> Tfittxija kwalunkwe numru ieħor li mhuwiex il-minimu jew il-massimu

134
00:06:56,000 --> 00:06:58,000
huwa daqstant faċli.

135
00:06:58,000 --> 00:07:00,000
Say aħna qed tfittex għall-numru 89.

136
00:07:00,000 --> 00:07:03,000
Aħna sempliċiment jivverifika l-valur ta 'kull node u jmorru lejn ix-xellug jew il-lemin,

137
00:07:03,000 --> 00:07:06,000
skond jekk il-valur tal-node hija inqas minn jew akbar minn

138
00:07:06,000 --> 00:07:08,000
l-waħda aħna qed tfittex.

139
00:07:08,000 --> 00:07:11,000
Allura, tibda fil-għerq ta '13, naraw li 89 hija akbar,

140
00:07:11,000 --> 00:07:13,000
u għalhekk immorru lejn il-lemin.

141
00:07:13,000 --> 00:07:16,000
Imbagħad naraw il-node għal 34, u għal darb'oħra immorru lejn il-lemin.

142
00:07:16,000 --> 00:07:20,000
89 għadu akbar minn 55, hekk aħna tkompli tmur lejn il-lemin.

143
00:07:20,000 --> 00:07:24,000
Aħna mbagħad toħroġ bi node mal-valur ta '144 u jmorru lejn ix-xellug.

144
00:07:24,000 --> 00:07:26,000
Lo u behold, 89 huwa dritt hemmhekk.

145
00:07:26,000 --> 00:07:31,000
>> Ħaġa oħra li nistgħu nagħmlu huwa jistampa numri kollha billi jwettqu traversal inorder.

146
00:07:31,000 --> 00:07:35,000
L traversal inorder ifisser li jistampa kollox fil-subtree xellug

147
00:07:35,000 --> 00:07:37,000
segwita mill-istampar tal-node innifsu

148
00:07:37,000 --> 00:07:40,000
u mbagħad segwit minn stampar kollox fl-dritt subtree.

149
00:07:40,000 --> 00:07:43,000
Per eżempju, ejja tagħti siġra favoriti tagħna tfittxija binarja

150
00:07:43,000 --> 00:07:46,000
u jistampa in-numri fl-ordni magħżula.

151
00:07:46,000 --> 00:07:49,000
Nibdew fil-għerq ta '13, iżda qabel l-istampar 13 rridu li jistampa

152
00:07:49,000 --> 00:07:51,000
kollox fil-subtree xellug.

153
00:07:51,000 --> 00:07:55,000
Allura aħna jmorru sa 5. Għad għandna biex tmur fil-fond fl-siġra sakemm insibu l-node tax-kbira,

154
00:07:55,000 --> 00:07:57,000
li huwa żero.

155
00:07:57,000 --> 00:08:00,000
Wara l-istampar żero, immorru lura sa l-1 u jistampa l barra.

156
00:08:00,000 --> 00:08:03,000
Imbagħad immorru l-subtree dritt, li huwa 2, u jistampa l barra.

157
00:08:03,000 --> 00:08:05,000
Issa li aħna qed isir ma 'dan subtree,

158
00:08:05,000 --> 00:08:07,000
nistgħu mmorru lura sa l-3 u ipprintjaha.

159
00:08:07,000 --> 00:08:11,000
Kontinwa back up, aħna jistampaw il-5 u allura l-8.

160
00:08:11,000 --> 00:08:13,000
Issa li aħna temmew l kollu xellug subtree,

161
00:08:13,000 --> 00:08:17,000
nistgħu jistampa l-13 u jibdew jaħdmu fuq il-lemin subtree.

162
00:08:17,000 --> 00:08:21,000
Aħna tal-ħops sa 34, iżda qabel l-istampar 34 għandna li jistampa subtree xellug tagħha.

163
00:08:21,000 --> 00:08:27,000
Allura aħna jistampa 21; allura aħna nikseb li jistampa 34 u żur dritt subtree tagħha.

164
00:08:27,000 --> 00:08:31,000
Peress li 55 m'għandha l-ebda subtree xellug, aħna ipprintjaha u tkompli fuq li subtree dritt tiegħu.

165
00:08:31,000 --> 00:08:36,000
144 għandha subtree xellug, u hekk aħna jistampa l-89, segwita mill-144,

166
00:08:36,000 --> 00:08:39,000
u finalment il-node dritt aktar ta '233.

167
00:08:39,000 --> 00:08:44,000
Hemm ikollok; il-numri huma stampati fl-ordni mill-iżgħar sa l-ogħla.

168
00:08:44,000 --> 00:08:47,000
>> Żieda xi ħaġa li l-siġra huwa relattivament mingħajr tbatija kif ukoll.

169
00:08:47,000 --> 00:08:51,000
Kollha għandna tagħmel hu li tagħmel żgur li aħna isegwu 3 proprjetajiet binarji tas-siġar tat-tiftix

170
00:08:51,000 --> 00:08:53,000
u mbagħad daħħal l-valur fejn ikun hemm spazju.

171
00:08:53,000 --> 00:08:55,000
Ejja ngħidu aħna tixtieq li daħħal il-valur ta '7.

172
00:08:55,000 --> 00:08:58,000
Peress 7 huwa inqas minn 13, immorru lejn ix-xellug.

173
00:08:58,000 --> 00:09:01,000
Iżda huwa ikbar minn 5, hekk aħna travers il-lemin.

174
00:09:01,000 --> 00:09:04,000
Peress li huwa inqas minn 8 u 8 hija node weraq, aħna żid 7 lill-wild xellug ta '8.

175
00:09:04,000 --> 00:09:09,000
Voila! Imxejna miżjud f'numru li siġra tagħna tfittxija binarja.

176
00:09:09,000 --> 00:09:12,000
>> Jekk aħna tista 'żżid affarijiet, aħna aħjar tkun tista' tħassar l-affarijiet ukoll.

177
00:09:12,000 --> 00:09:14,000
Sfortunatament għalina, tħassir huwa ftit aktar kumplikata -

178
00:09:14,000 --> 00:09:16,000
mhux wisq, iżda biss ftit.

179
00:09:16,000 --> 00:09:18,000
Hemm 3 xenarji differenti li għandna biex jikkunsidraw

180
00:09:18,000 --> 00:09:21,000
meta tħassir elementi minn siġar tat-tiftix binarja.

181
00:09:21,000 --> 00:09:24,000
L-ewwel, il-każ huwa eħfef li l-element huwa node weraq.

182
00:09:24,000 --> 00:09:27,000
F'dan il-każ, aħna sempliċiment iħassarha u jmorru fuq man-negozju tagħna.

183
00:09:27,000 --> 00:09:30,000
Say irridu li titħassar il-7 li aħna biss miżjud.

184
00:09:30,000 --> 00:09:34,000
Well, aħna sempliċiment jsibuha, neħħi dan, u li hu.

185
00:09:35,000 --> 00:09:37,000
Il-każ li jmiss hija jekk l-node għandha biss 1 tat-tfal.

186
00:09:37,000 --> 00:09:40,000
Hawnhekk nistgħu tħassar l-node, iżda aħna l-ewwel ikollhom jagħmlu ċert

187
00:09:40,000 --> 00:09:42,000
biex jgħaqqdu l-subtree li issa qed jitħalla f'idejn parentless

188
00:09:42,000 --> 00:09:44,000
lill-ġenitur ta 'l-node aħna biss mħassar.

189
00:09:44,000 --> 00:09:47,000
Say irridu li tħassar 3 minn siġra tagħna.

190
00:09:47,000 --> 00:09:50,000
Nieħdu l-element minuri ta 'dik node u jagħtu lill-ġenitur ta' l-node.

191
00:09:50,000 --> 00:09:54,000
F'dan il-każ, aħna qed issa jitwaħħal l-1 għall-5.

192
00:09:54,000 --> 00:09:57,000
Dan jaħdem mingħajr problema għaliex aħna nafu, skond il-binarju tfittxija siġra tal-proprjetà,

193
00:09:57,000 --> 00:10:01,000
li kollox fil-subtree xellug ta '3 kien inqas minn 5.

194
00:10:01,000 --> 00:10:05,000
Issa li l-subtree 3 huwa tittieħed kura ta ', nistgħu iħassarha.

195
00:10:05,000 --> 00:10:08,000
Il-każ tielet u finali hija l-aktar kumplessi.

196
00:10:08,000 --> 00:10:11,000
Dan huwa l-każ meta l-node irridu li titħassar għandu 2 tfal.

197
00:10:11,000 --> 00:10:15,000
Sabiex tagħmel dan, aħna l-ewwel iridu jsibu l-node li għandu l-valur li jmiss akbar,

198
00:10:15,000 --> 00:10:18,000
tpartit it-tnejn, u imbagħad tħassar l-node in kwistjoni.

199
00:10:18,000 --> 00:10:22,000
Avviż tal-node li għandu l-valur li jmiss akbar ma jistax ikollok 2 tfal stess

200
00:10:22,000 --> 00:10:26,000
peress tifel xellug tagħha tkun kandidat aħjar għall-ikbar li jmiss.

201
00:10:26,000 --> 00:10:30,000
Għalhekk, it-tħassir node ma '2-tfal jammonta għal iskambji ta '2 għoqiedi,

202
00:10:30,000 --> 00:10:33,000
u imbagħad tħassar tiġi ttrattata mill-1 tar-regoli msemmija qabel 2.

203
00:10:33,000 --> 00:10:37,000
Per eżempju, ejja ngħidu li rridu li jitħassar il-node għerq, 13.

204
00:10:37,000 --> 00:10:39,000
L-ewwel ħaġa li nagħmlu huwa insibu l-valur li jmiss akbar fl-siġra

205
00:10:39,000 --> 00:10:41,000
li, f'dan il-każ, huwa 21.

206
00:10:41,000 --> 00:10:46,000
Aħna mbagħad tpartit l-lymph 2, tagħmel 13 a werqa u 21-node grupp ċentrali.

207
00:10:46,000 --> 00:10:49,000
Issa nistgħu sempliċement titħassar 13.

208
00:10:50,000 --> 00:10:53,000
>> Kif allużjoni għall preċedenti, hemm bosta modi possibbli biex tagħmel siġra valida tfittxija binarja.

209
00:10:53,000 --> 00:10:56,000
Sfortunatament għalina, xi wħud huma agħar minn oħrajn.

210
00:10:56,000 --> 00:10:59,000
Per eżempju, dak li jiġri meta aħna nibnu siġra tfittxija binarju

211
00:10:59,000 --> 00:11:01,000
minn lista magħżula ta 'numri?

212
00:11:01,000 --> 00:11:04,000
Kollha numri huma biss miżjud għad-dritt f'kull pass.

213
00:11:04,000 --> 00:11:06,000
Meta aħna trid tfittex għal numru,

214
00:11:06,000 --> 00:11:08,000
għandna l-ebda għażla ħlief biss li tħares lejn il-lemin f'kull pass.

215
00:11:08,000 --> 00:11:11,000
Dan mhux aħjar minn tfittxija lineari fil-livelli kollha.

216
00:11:11,000 --> 00:11:13,000
Għalkemm aħna mhux se jkopri lilhom hawnhekk, hemm oħrajn, aktar kumplessi,

217
00:11:13,000 --> 00:11:16,000
data strutturi li jagħmlu ċert li dan ma jseħħx.

218
00:11:16,000 --> 00:11:18,000
Madankollu, ħaġa waħda sempliċi li jista 'jsir biex jiġi evitat dan huwa

219
00:11:18,000 --> 00:11:21,000
biss saltwarjament shuffle-valuri ta 'input.

220
00:11:21,000 --> 00:11:26,000
Huwa ferm improbabbli li b'kumbinazzjoni każwali lista shuffled ta 'numri huwa magħżul.

221
00:11:26,000 --> 00:11:29,000
Jekk dan kien il-każ, casinos ma jibqgħu fin-negozju għal żmien twil.

222
00:11:29,000 --> 00:11:31,000
>> Hemm ikollok.

223
00:11:31,000 --> 00:11:34,000
Inti issa taf dwar tiftix binarju u siġar tfittxija binarja.

224
00:11:34,000 --> 00:11:36,000
Jien Patrick Schmid, u dan huwa CS50.

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

226
00:11:38,000 --> 00:11:43,000
Mod wieħed ovvju ikun li skennjati l-lista minn ... [ħoss]

227
00:11:43,000 --> 00:11:46,000
... L-għadd ta 'oġġetti ... Yep

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

229
00:11:50,000 --> 00:11:55,000
... Post node ta '234 ... augh.

230
00:11:55,000 --> 00:11:58,000
! Yay >> Dan kien -