1
00:00:00,000 --> 00:00:02,000
[Powered by Google Translate] [Kërko Binary]

2
00:00:02,000 --> 00:00:04,000
[Patrick Schmid - Universiteti i Harvardit]

3
00:00:04,000 --> 00:00:07,000
[Kjo është CS50. - CS50.TV]

4
00:00:07,000 --> 00:00:09,000
>> Nëse unë ju dha një listë të emrave të karakterit Disney në rend alfabetik

5
00:00:09,000 --> 00:00:11,000
dhe i kërkoi që ju të gjeni Mickey Mouse,

6
00:00:11,000 --> 00:00:13,000
si do të shkojë për të bërë këtë?

7
00:00:13,000 --> 00:00:15,000
Një mënyrë e qartë do të jetë për të scan listë nga fillimi

8
00:00:15,000 --> 00:00:18,000
dhe kontrolloni çdo emër për të parë nëse ajo është Mickey.

9
00:00:18,000 --> 00:00:22,000
Por si ju lexoni Aladdin, Alice, Ariel, dhe kështu me radhë,

10
00:00:22,000 --> 00:00:25,000
ju do të shpejt të kuptojë se duke filluar në pjesën e përparme të listës nuk ishte një ide e mirë.

11
00:00:25,000 --> 00:00:29,000
Mirë, ndoshta ju duhet të fillojnë të punojnë prapa nga fundi i listës.

12
00:00:29,000 --> 00:00:33,000
Tani ju lexoni Tarzan, thur, borë të bardhë, dhe kështu me radhë.

13
00:00:33,000 --> 00:00:36,000
Megjithatë, kjo nuk duket si mënyra më e mirë për të shkuar në lidhje me të.

14
00:00:36,000 --> 00:00:38,000
>> E pra, një tjetër mënyrë që ju mund të shkoni për të bërë këtë është që të përpiqen për të ngushta poshtë

15
00:00:38,000 --> 00:00:41,000
lista e emrave që ju duhet të shikoni në.

16
00:00:41,000 --> 00:00:43,000
Që ju e dini se ata janë në rend alfabetik,

17
00:00:43,000 --> 00:00:45,000
ju mund të shikoni vetëm në emrat e në mes të listës

18
00:00:45,000 --> 00:00:49,000
dhe kontrolloni nëse Mickey Mouse është para apo pas këtij emri.

19
00:00:49,000 --> 00:00:51,000
Kërkoni në emrin e fundit në kolonën e dytë

20
00:00:51,000 --> 00:00:54,000
ju do të kuptojë se M për Mickey J vjen pas për Jasmine,

21
00:00:54,000 --> 00:00:57,000
kështu që ju do të thjesht injoroni gjysmën e parë të listës.

22
00:00:57,000 --> 00:00:59,000
Atëherë ju ndoshta do të shikoni në krye të kolonës e fundit

23
00:00:59,000 --> 00:01:02,000
dhe të shohim se ajo fillon me Rapunzel.

24
00:01:02,000 --> 00:01:06,000
Mickey vjen para Rapunzel, duket sikur ne mund të injorojë kolonën e fundit si.

25
00:01:06,000 --> 00:01:08,000
Vazhdimi strategjinë e kërkimit, ju do të shpejt të shihni se Mickey

26
00:01:08,000 --> 00:01:11,000
është në gjysmën e parë të listës së mbetur të emrave

27
00:01:11,000 --> 00:01:14,000
dhe më në fund të gjeni Mickey fshehur mes Merlin dhe Minnie.

28
00:01:14,000 --> 00:01:17,000
>> Çfarë ju vetëm e bëri ishte kërko thelb binar.

29
00:01:17,000 --> 00:01:22,000
Si kjo emri nënkupton, ajo kryen strategjinë e saj të kërkoni në një çështje binar.

30
00:01:22,000 --> 00:01:24,000
Çfarë do të thotë kjo?

31
00:01:24,000 --> 00:01:27,000
E pra, jepet një listë e artikujve të renditura, kërko binar algorithm merr një vendim binar -

32
00:01:27,000 --> 00:01:33,000
majtas ose djathtas, më i madh sesa ose më pak se, alfabetike para ose pas - në çdo pikë.

33
00:01:33,000 --> 00:01:35,000
Tani që ne kemi një emër që shkon së bashku me këtë algorithm e kërkimit,

34
00:01:35,000 --> 00:01:38,000
le të shohim një shembull tjetër, por këtë herë me një listë të numrave të renditura.

35
00:01:38,000 --> 00:01:43,000
Thonë se ne jemi duke kërkuar për numrin 144 në këtë listë të numrave të renditura.

36
00:01:43,000 --> 00:01:46,000
Ashtu si më parë, kemi gjetur numrin që është në mes -

37
00:01:46,000 --> 00:01:50,000
e cila në këtë rast është 13 - dhe të shohim nëse është më i madh se 144 apo më pak se 13.

38
00:01:50,000 --> 00:01:54,000
Që nga ajo është e qartë më i madh se 13, ne mund të injorojë gjithçka që është 13 ose më pak

39
00:01:54,000 --> 00:01:57,000
dhe vetëm të përqëndrohet në gjysmën e mbetur.

40
00:01:57,000 --> 00:01:59,000
Që nga viti ne kemi tani një numër të artikujve edhe majtas,

41
00:01:59,000 --> 00:02:01,000
ne thjesht zgjidhni një numër që është i afërt në mes.

42
00:02:01,000 --> 00:02:03,000
Në këtë rast kemi zgjedhur 55.

43
00:02:03,000 --> 00:02:06,000
Ne mund të kemi po aq e lehtë zgjedhur 89.

44
00:02:06,000 --> 00:02:11,000
Rregull. Përsëri, 144 është më i madh se 55, kështu që ne do të shkojmë në të djathtë.

45
00:02:11,000 --> 00:02:14,000
Për fat të mirë për ne, numri ardhshëm mesme është 144,

46
00:02:14,000 --> 00:02:16,000
një ne jemi duke kërkuar për të.

47
00:02:16,000 --> 00:02:21,000
Pra, në mënyrë që të gjeni një kërkim duke përdorur 144 binar, ne jemi në gjendje për të gjetur atë në vetëm 3 hapa.

48
00:02:21,000 --> 00:02:24,000
Në qoftë se ne do të kemi përdorur kërkim linear këtu, kjo do të marrë hapa na 12.

49
00:02:24,000 --> 00:02:28,000
Si një çështje të vërtetë, pasi kjo metodë kërkim gjysmave numrin e artikujve

50
00:02:28,000 --> 00:02:31,000
ajo ka për të parë në në çdo hap, ajo do të gjeni pika ajo është në kërkim për të

51
00:02:31,000 --> 00:02:35,000
në lidhje me log të numrit të artikujve në listë.

52
00:02:35,000 --> 00:02:37,000
Tani që ne kemi parë 2 shembuj, le të marrin një vështrim në

53
00:02:37,000 --> 00:02:41,000
disa pseudokod për një funksion rekursiv që zbaton kërkimin binar.

54
00:02:41,000 --> 00:02:44,000
Duke filluar në krye, shohim se kemi për të gjetur një funksion që merr 4 argumente:

55
00:02:44,000 --> 00:02:47,000
, kyç array, min, max dhe.

56
00:02:47,000 --> 00:02:51,000
Çelësi është numri që ne jemi duke kërkuar për të, kështu 144 në shembullin e mëparshëm.

57
00:02:51,000 --> 00:02:54,000
Array është lista e numrave që ne jemi në kërkim.

58
00:02:54,000 --> 00:02:57,000
Min dhe max janë indekset e pozicioneve minimale dhe maksimale

59
00:02:57,000 --> 00:02:59,000
se ne jemi aktualisht në kërkim në.

60
00:02:59,000 --> 00:03:03,000
Kështu që kur kemi filluar, do të jetë zero min dhe max do të jetë indeksi maksimal të grup.

61
00:03:03,000 --> 00:03:07,000
Siç kemi ngushtuar kërkimin poshtë, ne do update min dhe max

62
00:03:07,000 --> 00:03:10,000
të jetë vetëm varg që ne jemi ende në kërkim in

63
00:03:10,000 --> 00:03:12,000
>> Le të kaloni në pjesën interesante parë.

64
00:03:12,000 --> 00:03:14,000
Gjëja e parë që ne bëjmë është të gjeni midpoint,

65
00:03:14,000 --> 00:03:19,000
indeksi që është në gjysmë të rrugës në mes të min dhe max e grup që ne jemi ende duke konsideruar.

66
00:03:19,000 --> 00:03:22,000
Atëherë ne shikojmë në vlerën e vektorit në atë vend midpoint

67
00:03:22,000 --> 00:03:25,000
dhe të shohim nëse numri që ne jemi duke kërkuar për të është më pak se ajo kyç.

68
00:03:25,000 --> 00:03:27,000
Nëse numri në atë pozicion është më pak,

69
00:03:27,000 --> 00:03:31,000
atëherë kjo do të thotë se çelësi është më i madh se të gjithë numrat në të majtë të atij pozitë.

70
00:03:31,000 --> 00:03:33,000
Kështu që ne mund ta quajmë funksion binar kërkimit përsëri,

71
00:03:33,000 --> 00:03:36,000
por këtë herë përditësimin e min dhe parametrat max për të lexuar vetëm gjysmën e

72
00:03:36,000 --> 00:03:40,000
që është më e madhe se ose e barabartë me vlerën ne vetëm shikoi.

73
00:03:40,000 --> 00:03:44,000
Nga ana tjetër, nëse çelësi është më pak se numri në midpoint e tanishme e array,

74
00:03:44,000 --> 00:03:47,000
ne duam të shkojnë në të majtë dhe të injorojë të gjitha numrat që janë më të mëdha.

75
00:03:47,000 --> 00:03:52,000
Përsëri, ne e quajmë kërkimin binar, por këtë herë me varg e min dhe max UPDATED

76
00:03:52,000 --> 00:03:54,000
të përfshijë vetëm gjysma e ulët.

77
00:03:54,000 --> 00:03:57,000
Nëse vlera në midpoint e tanishme në grup nuk është as

78
00:03:57,000 --> 00:04:01,000
madhe se as më e vogël se çelësi, atëherë ajo duhet të jetë e barabartë me kyç.

79
00:04:01,000 --> 00:04:05,000
Kështu, ne thjesht mund të kthehen indeksin aktual midpoint, dhe ne jemi duke bërë.

80
00:04:05,000 --> 00:04:09,000
Së fundi, ky çek këtu është për rastet kur numri

81
00:04:09,000 --> 00:04:11,000
nuk është në të vërtetë në rrjet të numrave ne jemi në kërkim.

82
00:04:11,000 --> 00:04:14,000
Nëse indeksi maksimal i varg që ne jemi duke kërkuar për

83
00:04:14,000 --> 00:04:17,000
është gjithnjë e më pak se minimale, që do të thotë se ne kemi shkuar shumë larg.

84
00:04:17,000 --> 00:04:20,000
Që nga numri nuk ishte në rrjet input, ne kthim -1

85
00:04:20,000 --> 00:04:24,000
për të treguar se asgjë nuk u gjet.

86
00:04:24,000 --> 00:04:26,000
>> Ju mund të keni vënë re se për këtë algoritëm për të punuar,

87
00:04:26,000 --> 00:04:28,000
lista e numrave duhet të zgjidhet.

88
00:04:28,000 --> 00:04:31,000
Me fjalë të tjera, ne mund të gjeni vetëm 144 duke përdorur search binar

89
00:04:31,000 --> 00:04:34,000
nëse të gjithë numrat janë urdhëruar nga më të ulët për më të larta.

90
00:04:34,000 --> 00:04:38,000
Nëse kjo nuk ishte kështu, ne nuk do të jetë në gjendje për të përjashtuar gjysmën e numrave në çdo hap.

91
00:04:38,000 --> 00:04:40,000
Pra, ne kemi 2 opsione.

92
00:04:40,000 --> 00:04:43,000
Ose ne mund të marrë një listë Unsorted dhe zgjidhur atë para duke përdorur search binar,

93
00:04:43,000 --> 00:04:48,000
ose ne mund të sigurohemi se lista e numrave është renditur si ne shtoni numra për të.

94
00:04:48,000 --> 00:04:50,000
Kështu, në vend të zgjidhja vetëm kur kemi për të kërkuar,

95
00:04:50,000 --> 00:04:53,000
pse nuk e mbajnë listën e renditura në çdo kohë?

96
00:04:53,000 --> 00:04:57,000
>> Një mënyrë për të mbajtur një listë të numrave të zgjidhet, ndërsa në të njëjtën kohë duke i lejuar

97
00:04:57,000 --> 00:04:59,000
një për të shtuar apo veprim numrat nga kjo listë

98
00:04:59,000 --> 00:05:02,000
është duke përdorur diçka që quhet një pemë binare kërkim.

99
00:05:02,000 --> 00:05:05,000
Një kërkim binar pemë është një strukturë e të dhënave që ka 3 veti.

100
00:05:05,000 --> 00:05:09,000
Së pari, subtree e majtë të çdo nyje përmban vlera vetëm që janë më pak se

101
00:05:09,000 --> 00:05:11,000
ose e barabartë me vlerën nyjen së.

102
00:05:11,000 --> 00:05:15,000
Së dyti, e drejta e një subtree nyje përmban vetëm vlerat që janë më të mëdha se

103
00:05:15,000 --> 00:05:17,000
ose e barabartë me vlerën nyjen së.

104
00:05:17,000 --> 00:05:20,000
Dhe, në fund, të dyja tregoje majtë dhe të djathtë të të gjitha nyjet

105
00:05:20,000 --> 00:05:23,000
edhe pemë binare e kërkimit.

106
00:05:23,000 --> 00:05:26,000
Le të shikojmë një shembull me të njëjtin numër kemi përdorur më herët.

107
00:05:26,000 --> 00:05:30,000
Për ata prej jush që kurrë nuk kanë parë një pemë përpara shkenca kompjuterike,

108
00:05:30,000 --> 00:05:34,000
më lejoni të filloj duke ju thënë se një shkencë kompjuterike pema rritet poshtë.

109
00:05:34,000 --> 00:05:36,000
Po, ndryshe nga pemët që janë mësuar të,

110
00:05:36,000 --> 00:05:38,000
rrënja e një peme shkenca kompjuterike është në krye,

111
00:05:38,000 --> 00:05:41,000
dhe gjethet janë në fund.

112
00:05:41,000 --> 00:05:45,000
Çdo kuti të vogël quhet një nyje, dhe nyjet janë të lidhura me njëri-tjetrin nga skajet.

113
00:05:45,000 --> 00:05:48,000
Pra, rrënja e kësaj peme është një vlerë nyje me vlerë 13,

114
00:05:48,000 --> 00:05:52,000
i cili ka 2 fëmijë nyjet me vlerat 5 dhe 34.

115
00:05:52,000 --> 00:05:57,000
Një subtree është pemë që është e përbërë vetëm duke shikuar në një nënseksioni e pemë të tërë.

116
00:05:57,000 --> 00:06:03,000
>> Për shembull, subtree majtë e 3 nyjen është pemë e krijuar nga nyjet 0, 1, dhe 2.

117
00:06:03,000 --> 00:06:06,000
Pra, nëse ne do të shkojmë përsëri në pronat e një pemë kërkim dyor,

118
00:06:06,000 --> 00:06:09,000
ne shohim se çdo nyje në pemë përputhet me të gjitha pronat 3, domethënë,

119
00:06:09,000 --> 00:06:15,000
the subtree majtë përmban vetëm vlerat që janë më pak se ose e barabartë me vlerën nyjen-së;

120
00:06:15,000 --> 00:06:16,000
e drejta e të gjitha nyjet subtree

121
00:06:16,000 --> 00:06:19,000
përmban vetëm vlerat që janë më të mëdha se ose e barabartë me vlerën nyjen së dhe

122
00:06:19,000 --> 00:06:25,000
subtrees dy majtë dhe të djathtë të të gjitha nyjet janë gjithashtu pemë binare e kërkimit.

123
00:06:25,000 --> 00:06:28,000
Edhe pse kjo pemë duket ndryshe, kjo është një kërkim i vlefshëm binar pemë

124
00:06:28,000 --> 00:06:30,000
për të njëjtat e numrave.

125
00:06:30,000 --> 00:06:32,000
Si një çështje të vërtetë, ka shumë mënyra të mundshme që ju mund të krijojë

126
00:06:32,000 --> 00:06:35,000
e vlefshme kërkimit binar pema nga këto numra.

127
00:06:35,000 --> 00:06:38,000
E pra, le të kthehemi në një të parë kemi krijuar.

128
00:06:38,000 --> 00:06:40,000
Pra, çfarë mund të bëjmë me këto pemë?

129
00:06:40,000 --> 00:06:44,000
E pra, ne mund të gjeni shumë thjesht vlerat minimale dhe maksimale.

130
00:06:44,000 --> 00:06:46,000
Vlerat minimale mund të gjenden duke shkuar gjithnjë në të majtë

131
00:06:46,000 --> 00:06:48,000
derisa ka nyje ka më shumë për të vizituar.

132
00:06:48,000 --> 00:06:53,000
Anasjelltas, për të gjetur një maksimal thjesht vetëm shkon poshtë për të drejtën në çdo kohë.

133
00:06:54,000 --> 00:06:56,000
>> Gjetur ndonjë numër tjetër që nuk është minimale apo maksimale

134
00:06:56,000 --> 00:06:58,000
është po aq e lehtë.

135
00:06:58,000 --> 00:07:00,000
Thonë se ne jemi duke kërkuar për numrin 89.

136
00:07:00,000 --> 00:07:03,000
Ne thjesht kontrolloni vlerën e çdo nyje dhe të shkoni në të majtë apo të djathtë,

137
00:07:03,000 --> 00:07:06,000
varësi të faktit nëse vlera Nyja është më pak se ose e madhe se

138
00:07:06,000 --> 00:07:08,000
një ne jemi duke kërkuar për të.

139
00:07:08,000 --> 00:07:11,000
Kështu, duke filluar në rrënjë të 13, shohim se 89 është më e madhe,

140
00:07:11,000 --> 00:07:13,000
dhe kështu ne do të shkojmë në të djathtë.

141
00:07:13,000 --> 00:07:16,000
Pastaj ne e shohim për nyjen 34, dhe përsëri ne do të shkojmë në të djathtë.

142
00:07:16,000 --> 00:07:20,000
89 është ende më i madh se 55, kështu që ne vazhdojmë duke shkuar në të djathtë.

143
00:07:20,000 --> 00:07:24,000
Ne pastaj të dalë me një nyje me vlerën e 144 dhe të shkoni në të majtë.

144
00:07:24,000 --> 00:07:26,000
Ja dhe ja, 89 është e drejtë atje.

145
00:07:26,000 --> 00:07:31,000
>> Një tjetër gjë që mund të bëjmë është të shtypura nga të gjitha numrat duke kryer një traversal inorder.

146
00:07:31,000 --> 00:07:35,000
Një traversal inorder do të thotë për të shtypur çdo gjë në subtree majtë

147
00:07:35,000 --> 00:07:37,000
ndjekur nga shtypi nyjen vetë

148
00:07:37,000 --> 00:07:40,000
dhe më pas duke shtypur çdo gjë në të drejtën subtree.

149
00:07:40,000 --> 00:07:43,000
Për shembull, le të marrin favorite tonë të kërkimit pemë binare

150
00:07:43,000 --> 00:07:46,000
dhe të shtypura nga numrat në mënyrë renditura.

151
00:07:46,000 --> 00:07:49,000
Ne të fillojë në rrënjë të 13, por para printimit 13 ne duhet të shtypura nga

152
00:07:49,000 --> 00:07:51,000
gjithçka në subtree majtë.

153
00:07:51,000 --> 00:07:55,000
Pra, ne do të shkojmë deri në 5. Ne ende kemi për të shkuar më thellë poshtë në pemë deri ne gjeni nyjen e majtë më të madhe,

154
00:07:55,000 --> 00:07:57,000
cila është zero.

155
00:07:57,000 --> 00:08:00,000
Pas shtypjes zero, ne kthehemi deri në 1 dhe të shtypura atë jashtë.

156
00:08:00,000 --> 00:08:03,000
Pastaj ne do të shkojmë në të djathtë subtree, e cila është 2, dhe të shtypura atë jashtë.

157
00:08:03,000 --> 00:08:05,000
Tani që ne jemi bërë me atë subtree,

158
00:08:05,000 --> 00:08:07,000
ne mund të shkojë mbrapa deri në 3 dhe të shtypura it out.

159
00:08:07,000 --> 00:08:11,000
Vazhdimi back up, ne printoni 5 dhe pastaj 8.

160
00:08:11,000 --> 00:08:13,000
Tani që ne kemi përfunduar tërë la subtree,

161
00:08:13,000 --> 00:08:17,000
ne mund të shtypura nga 13 dhe fillojnë të punojnë në të djathtë subtree.

162
00:08:17,000 --> 00:08:21,000
Ne hop deri 34, por para printimit 34 ne duhet të shtypura nga subtree e saj të majtë.

163
00:08:21,000 --> 00:08:27,000
Pra, ne të shtypura nga 21, pastaj ne kemi marrë për të printuar jashtë dhe do të vizitojë 34 subtree të drejtën e saj.

164
00:08:27,000 --> 00:08:31,000
Që 55 nuk ka subtree majtas, ne print it out dhe të vazhdojë në të subtree e saj të drejtë.

165
00:08:31,000 --> 00:08:36,000
144 ka një subtree majtë, dhe kështu që ne të shtypura nga 89, e ndjekur nga 144,

166
00:08:36,000 --> 00:08:39,000
dhe në fund të djathtë më të nyje e 233.

167
00:08:39,000 --> 00:08:44,000
Nuk keni atë, të gjithë numrat janë të shtypura në mënyrë të ulët në më të lartë.

168
00:08:44,000 --> 00:08:47,000
>> Shtimi diçka tek pema është relativisht pa dhimbje si.

169
00:08:47,000 --> 00:08:51,000
Të gjithë ne duhet të bëni është të bëni të sigurtë që ne ndjekim 3 search pronat binare pemë

170
00:08:51,000 --> 00:08:53,000
dhe pastaj futur vlera ku ka hapësirë.

171
00:08:53,000 --> 00:08:55,000
Le të thonë se ne duam të futur vlerën e 7.

172
00:08:55,000 --> 00:08:58,000
Që nga 7 është më pak se 13, ne do të shkojmë në të majtë.

173
00:08:58,000 --> 00:09:01,000
Por kjo është më e madhe se 5, kështu që ne përshkojë në të djathtë.

174
00:09:01,000 --> 00:09:04,000
Që nga ajo është më pak se 8 dhe 8 është një nyje gjethe, ne shtoni 7 me fëmijën e majtë të 8.

175
00:09:04,000 --> 00:09:09,000
Voila! Ne kemi shtuar një numër në pemë binare e kërkimit tonë.

176
00:09:09,000 --> 00:09:12,000
>> Nëse ne mund të shtoni gjërat, ne më mirë të jetë në gjendje për të fshini gjërat si.

177
00:09:12,000 --> 00:09:14,000
Fatkeqësisht për ne, fshirjes është pak më e komplikuar -

178
00:09:14,000 --> 00:09:16,000
jo shumë, por vetëm pak.

179
00:09:16,000 --> 00:09:18,000
Ka 3 skenarë të ndryshëm që ne duhet të marrin në konsideratë

180
00:09:18,000 --> 00:09:21,000
kur fshirjes elemente nga pemë binare e kërkimit.

181
00:09:21,000 --> 00:09:24,000
Së pari, çështja më e lehtë është që elementi është një nyje gjethe.

182
00:09:24,000 --> 00:09:27,000
Në këtë rast, ne thjesht fshini atë dhe të vazhdojë me biznesin tonë.

183
00:09:27,000 --> 00:09:30,000
Thonë se ne duam të fshini 7 që ne vetëm shtuar.

184
00:09:30,000 --> 00:09:34,000
E pra, ne thjesht të gjeni atë, hiqni atë, dhe kjo është ajo.

185
00:09:35,000 --> 00:09:37,000
Rasti tjetër është, nëse nyja ka vetëm fëmijë 1.

186
00:09:37,000 --> 00:09:40,000
Këtu mund të fshini nyjen, por ne së pari duhet të sigurohemi

187
00:09:40,000 --> 00:09:42,000
të lidhë subtree që ka mbetur tani pa prindër

188
00:09:42,000 --> 00:09:44,000
për prindin e nyjeve ne fshihet vetëm.

189
00:09:44,000 --> 00:09:47,000
Thonë se ne duam të fshini 3 nga pema tonë.

190
00:09:47,000 --> 00:09:50,000
Ne kemi marrë elementin fëmijës e asaj nyje dhe atë të bashkëngjitni prind e nyjeve.

191
00:09:50,000 --> 00:09:54,000
Në këtë rast, ne jemi tani bashkëngjitur 1 në 5.

192
00:09:54,000 --> 00:09:57,000
Kjo punon pa problem, sepse ne e dimë, në bazë të kërkimit binar pronës pemë,

193
00:09:57,000 --> 00:10:01,000
se çdo gjë në subtree majtë e 3 ishte më pak se 5.

194
00:10:01,000 --> 00:10:05,000
Tani që e 3 subtree është marrë kujdesin e, ne mund të fshini atë.

195
00:10:05,000 --> 00:10:08,000
Rasti i tretë dhe i fundit është më komplekse.

196
00:10:08,000 --> 00:10:11,000
Ky është rasti kur nyje ne duam të fshini ka 2 fëmijë.

197
00:10:11,000 --> 00:10:15,000
Në mënyrë që të bëni këtë, ne së pari duhet të gjejnë nyjen që ka vlerën më të madh,

198
00:10:15,000 --> 00:10:18,000
bie në ujdi dy, dhe pastaj fshini nyjen në fjalë.

199
00:10:18,000 --> 00:10:22,000
Njoftim nyjen që ka vlera më e madhe e ardhshme nuk mund të ketë 2 fëmijë vetë

200
00:10:22,000 --> 00:10:26,000
që fëmija i tij të majtë do të jetë një kandidat i mirë për të madhe ardhshëm.

201
00:10:26,000 --> 00:10:30,000
Prandaj, fshirjes një nyje me 2 fëmijë arrin të shkëmbejnë prej 2 nyje,

202
00:10:30,000 --> 00:10:33,000
dhe pastaj fshirjes është trajtuar nga 1 e 2 rregullave të lartpërmendura.

203
00:10:33,000 --> 00:10:37,000
Për shembull, le të thonë se ne duam të fshini nyjen rrënjë, 13.

204
00:10:37,000 --> 00:10:39,000
Gjëja e parë që ne bëjmë është që ne të gjeni vlerën më të madh në pemë

205
00:10:39,000 --> 00:10:41,000
cila, në këtë rast, është 21.

206
00:10:41,000 --> 00:10:46,000
Ne pastaj shkëmbim 2 nyje, duke e bërë 13 një fletë dhe 21 nyjen qendrore grup.

207
00:10:46,000 --> 00:10:49,000
Tani ne thjesht mund të fshini 13.

208
00:10:50,000 --> 00:10:53,000
>> Aludoi për sa më herët, ka shumë mënyra të mundshme për të bërë një kërkim të vlefshme pemë binare.

209
00:10:53,000 --> 00:10:56,000
Për fat të keq për ne, disa janë më keq se të tjerët.

210
00:10:56,000 --> 00:10:59,000
Për shembull, çfarë ndodh kur ne kemi ndërtuar një pemë binare kërkimi

211
00:10:59,000 --> 00:11:01,000
nga një listë të renditura të numrave?

212
00:11:01,000 --> 00:11:04,000
Të gjithë numrat janë shtuar vetëm për të drejtën në çdo hap.

213
00:11:04,000 --> 00:11:06,000
Kur ne duam të kërkoni për një numër,

214
00:11:06,000 --> 00:11:08,000
ne nuk kemi asnjë zgjidhje, por vetëm shikoni në të drejtën në çdo hap.

215
00:11:08,000 --> 00:11:11,000
Kjo nuk është më e mirë se kërkim linear në të gjitha.

216
00:11:11,000 --> 00:11:13,000
Edhe pse ne nuk do të mbulojë ata këtu, ka të tjera, më komplekse,

217
00:11:13,000 --> 00:11:16,000
dhënave struktura që bëjnë të sigurt se kjo nuk do të ndodhë.

218
00:11:16,000 --> 00:11:18,000
Megjithatë, një gjë e thjeshtë që mund të bëhet për të shmangur këtë është

219
00:11:18,000 --> 00:11:21,000
në vetëm riorganizimi rastësisht vlerat hyrëse.

220
00:11:21,000 --> 00:11:26,000
Është shumë gjasa që rastësisht një listë riorganizoi e numrave është e renditura.

221
00:11:26,000 --> 00:11:29,000
Nëse ky ishte rasti, kazinove nuk do të qëndrojë në biznes për kohë të gjatë.

222
00:11:29,000 --> 00:11:31,000
>> Nuk keni atë.

223
00:11:31,000 --> 00:11:34,000
Ju tani e dini në lidhje me kërkimin dhe pemë binare e kërkimit binar.

224
00:11:34,000 --> 00:11:36,000
Unë jam Patrick Schmid, dhe kjo është CS50.

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

226
00:11:38,000 --> 00:11:43,000
Një mënyrë e qartë do të jetë për të scan listë nga ... [bip]

227
00:11:43,000 --> 00:11:46,000
Numri ... i artikujve yep ...

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

229
00:11:50,000 --> 00:11:55,000
Postoni ... nyje e 234 ... augh.

230
00:11:55,000 --> 00:11:58,000
Yay >>! Kjo ishte -