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

2
00:00:02,000 --> 00:00:04,000
[Patrick Schmid - Chuo Kikuu cha Harvard]

3
00:00:04,000 --> 00:00:07,000
[Hii ni CS50. - CS50.TV]

4
00:00:07,000 --> 00:00:09,000
>> Kama Mimi niliwapeni orodha ya majina ya tabia Disney katika herufi

5
00:00:09,000 --> 00:00:11,000
na aliuliza wewe kupata Mickey Mouse,

6
00:00:11,000 --> 00:00:13,000
jinsi gani unaweza kwenda juu ya kufanya hii?

7
00:00:13,000 --> 00:00:15,000
Moja ya njia dhahiri itakuwa Scan orodha tangu mwanzo

8
00:00:15,000 --> 00:00:18,000
na kuangalia kila jina ili kuona kama ni Mickey.

9
00:00:18,000 --> 00:00:22,000
Lakini kama wewe kusoma Aladdin, Alice, Arieli, na kadhalika,

10
00:00:22,000 --> 00:00:25,000
utasikia haraka kutambua kwamba kuanzia saa mbele ya orodha ilikuwa si wazo nzuri.

11
00:00:25,000 --> 00:00:29,000
Sawa, labda unapaswa kuanza kufanya kazi nyuma kutoka mwisho wa orodha.

12
00:00:29,000 --> 00:00:33,000
Sasa unaweza kusoma Tarzan, Stitch, Snow White, na kadhalika.

13
00:00:33,000 --> 00:00:36,000
Hata hivyo, hii haionekani kama njia bora ya kwenda juu yake.

14
00:00:36,000 --> 00:00:38,000
>> Naam, njia nyingine ambayo unaweza kwenda juu ya kufanya hii ni kujaribu nyembamba chini

15
00:00:38,000 --> 00:00:41,000
orodha ya majina ya kwamba una kuangalia.

16
00:00:41,000 --> 00:00:43,000
Tangu unajua kwamba wao ni katika mpango wa herufi,

17
00:00:43,000 --> 00:00:45,000
unaweza tu kuangalia majina katikati ya orodha

18
00:00:45,000 --> 00:00:49,000
na kuangalia kama Mickey Mouse ni kabla au baada ya jina hili.

19
00:00:49,000 --> 00:00:51,000
Kuangalia jina la mwisho katika safu ya pili

20
00:00:51,000 --> 00:00:54,000
Ningependa kutambua kwamba M kwa ajili ya Mickey inakuja baada ya J kwa Jasmine,

21
00:00:54,000 --> 00:00:57,000
hivyo wewe d tu kupuuza nusu ya kwanza ya orodha.

22
00:00:57,000 --> 00:00:59,000
Kisha wewe d pengine kuangalia juu ya safu ya mwisho

23
00:00:59,000 --> 00:01:02,000
na kuona kwamba huanza na Rapunzel.

24
00:01:02,000 --> 00:01:06,000
Mickey inakuja kabla Rapunzel; inaonekana kama tunaweza kupuuza safu mwisho pia.

25
00:01:06,000 --> 00:01:08,000
Inaendelea na mkakati tafuta, itabidi haraka kuona kwamba Mickey

26
00:01:08,000 --> 00:01:11,000
ni katika nusu ya kwanza ya orodha ya majina iliyobaki

27
00:01:11,000 --> 00:01:14,000
na hatimaye kupata Mickey mafichoni kati ya Merlin na Minnie.

28
00:01:14,000 --> 00:01:17,000
>> Nini wewe tu alifanya alikuwa kimsingi binary tafuta.

29
00:01:17,000 --> 00:01:22,000
Kama jina hii ina maana, hufanya kutafuta yake mkakati katika suala binary.

30
00:01:22,000 --> 00:01:24,000
Hii ina maana gani?

31
00:01:24,000 --> 00:01:27,000
Naam, kutokana na orodha ya vitu sorted, tafuta binary algorithm hufanya uamuzi binary -

32
00:01:27,000 --> 00:01:33,000
kushoto au kulia, zaidi au chini, alphabetically kabla au baada ya - katika hatua kila mmoja.

33
00:01:33,000 --> 00:01:35,000
Sasa kwa kuwa tuna jina kwamba huenda pamoja na algorithm hii tafuta,

34
00:01:35,000 --> 00:01:38,000
hebu tuangalie mfano mwingine, lakini wakati huu na orodha ya idadi Iliyopangwa.

35
00:01:38,000 --> 00:01:43,000
Sema sisi ni kuangalia kwa idadi 144 katika orodha hii ya idadi Iliyopangwa.

36
00:01:43,000 --> 00:01:46,000
Tu kama kabla, sisi kupata idadi hiyo ni katika katikati -

37
00:01:46,000 --> 00:01:50,000
ambayo katika kesi hii ni 13 - 144 na kuona kama ni zaidi au chini ya 13.

38
00:01:50,000 --> 00:01:54,000
Tangu ni wazi zaidi kuliko 13, tunaweza kupuuza kila kitu kuwa ni 13 au chini

39
00:01:54,000 --> 00:01:57,000
na tu makini na nusu iliyobaki.

40
00:01:57,000 --> 00:01:59,000
Tangu sasa tuna idadi ya vitu hata kushoto,

41
00:01:59,000 --> 00:02:01,000
sisi tu kuchagua idadi ambayo ni karibu na katikati.

42
00:02:01,000 --> 00:02:03,000
Katika kesi hii sisi kuchagua 55.

43
00:02:03,000 --> 00:02:06,000
Tungeweza urahisi tu kama waliochaguliwa 89.

44
00:02:06,000 --> 00:02:11,000
Sawa. Tena, 144, ni mkubwa kuliko 55, hivyo sisi kwenda kulia.

45
00:02:11,000 --> 00:02:14,000
Bahati nzuri kwa ajili yetu, karibu katikati idadi ni 144,

46
00:02:14,000 --> 00:02:16,000
moja sisi ni kuangalia kwa.

47
00:02:16,000 --> 00:02:21,000
Hivyo ili kupata 144 kwa kutumia tafuta binary, sisi ni uwezo wa kupata hiyo katika hatua 3 tu.

48
00:02:21,000 --> 00:02:24,000
Kama sisi ingekuwa kutumika tafuta linear hapa, ingekuwa kuchukuliwa hatua sisi 12.

49
00:02:24,000 --> 00:02:28,000
Kama jambo la kweli, tangu njia hii tafuta halves idadi ya vitu

50
00:02:28,000 --> 00:02:31,000
ina kuangalia kila hatua, itakuwa kupata bidhaa hiyo ni kwa ajili ya kutafuta

51
00:02:31,000 --> 00:02:35,000
katika kuhusu logi ya idadi ya vitu katika orodha.

52
00:02:35,000 --> 00:02:37,000
Sasa kwa kuwa tumeona mifano 2, hebu tuangalie

53
00:02:37,000 --> 00:02:41,000
baadhi pseudocode kwa ajili ya kazi ya kujirudia kwamba kutekeleza tafuta binary.

54
00:02:41,000 --> 00:02:44,000
Kuanzia juu, tunaona kwamba tuna kupata kazi ambayo inachukua hoja 4:

55
00:02:44,000 --> 00:02:47,000
muhimu, safu, min, na max.

56
00:02:47,000 --> 00:02:51,000
muhimu ni kwamba idadi hiyo sisi ni kuangalia kwa, hivyo 144 katika mfano uliopita.

57
00:02:51,000 --> 00:02:54,000
Array ni orodha ya namba kwamba sisi ni kutafuta.

58
00:02:54,000 --> 00:02:57,000
Min na max ni fahirisi ya nafasi ya chini na upeo

59
00:02:57,000 --> 00:02:59,000
kwamba sisi sasa ni kuangalia.

60
00:02:59,000 --> 00:03:03,000
Hivyo wakati sisi kuanza, min itakuwa sifuri na max itakuwa index upeo wa safu.

61
00:03:03,000 --> 00:03:07,000
Kama sisi nyembamba tafuta chini, sisi update min na max

62
00:03:07,000 --> 00:03:10,000
kwa kuwa tu mbalimbali kwamba sisi bado ni kuangalia in

63
00:03:10,000 --> 00:03:12,000
>> Hebu ruka kwa sehemu ya kuvutia ya kwanza.

64
00:03:12,000 --> 00:03:14,000
Jambo la kwanza sisi kufanya ni kupata midpoint,

65
00:03:14,000 --> 00:03:19,000
index kwamba ni nusu kati ya dk na max ya safu ya kwamba sisi ni bado kuzingatia.

66
00:03:19,000 --> 00:03:22,000
Kisha sisi kuangalia thamani ya safu katika eneo kwamba midpoint

67
00:03:22,000 --> 00:03:25,000
na kuona kama idadi ya kwamba sisi ni kuangalia kwa ni chini ya muhimu ambayo.

68
00:03:25,000 --> 00:03:27,000
Kama idadi katika nafasi ya kuwa ni chini,

69
00:03:27,000 --> 00:03:31,000
basi ina maana muhimu ni kubwa kuliko idadi yote ya kushoto ya nafasi hiyo.

70
00:03:31,000 --> 00:03:33,000
Hivyo tunaweza kuwaita binary tafuta kazi tena,

71
00:03:33,000 --> 00:03:36,000
lakini wakati huu uppdatering min na vigezo max kusoma tu nusu

72
00:03:36,000 --> 00:03:40,000
kwamba, ni mkubwa kuliko au sawa na thamani sisi alimwangalia.

73
00:03:40,000 --> 00:03:44,000
Kwa upande mwingine, kama ufunguo ni chini ya idadi ya sasa katika midpoint wa safu,

74
00:03:44,000 --> 00:03:47,000
tunataka kwenda kwa upande wa kushoto na kupuuza idadi yote kwamba ni kubwa zaidi.

75
00:03:47,000 --> 00:03:52,000
Tena, sisi kuwaita binary tafuta lakini wakati huu na aina mbalimbali ya dk na max updated

76
00:03:52,000 --> 00:03:54,000
kwa pamoja na nusu tu ya chini.

77
00:03:54,000 --> 00:03:57,000
Kama thamani katika midpoint ya sasa katika safu ni wala

78
00:03:57,000 --> 00:04:01,000
kubwa kuliko wala ndogo kuliko muhimu, basi ni lazima kuwa sawa na muhimu.

79
00:04:01,000 --> 00:04:05,000
Hivyo, tunaweza tu kurudi sasa midpoint index, na sisi ni kosa.

80
00:04:05,000 --> 00:04:09,000
Hatimaye, hii hapa ni kuangalia kwa kesi hiyo namba

81
00:04:09,000 --> 00:04:11,000
si kweli katika safu ya idadi sisi ni kutafuta.

82
00:04:11,000 --> 00:04:14,000
Kama index upeo wa mbalimbali kwamba sisi ni kuangalia kwa

83
00:04:14,000 --> 00:04:17,000
ni milele chini ya kiwango cha chini, hiyo ina maana kwamba tumeenda mbali sana.

84
00:04:17,000 --> 00:04:20,000
Tangu idadi ilikuwa si katika safu ya pembejeo, sisi kurudi -1

85
00:04:20,000 --> 00:04:24,000
zinaonyesha kwamba hakuna found.

86
00:04:24,000 --> 00:04:26,000
>> Unaweza kuwa niliona kuwa kwa algorithm hii kazi,

87
00:04:26,000 --> 00:04:28,000
orodha ya idadi ina sorted.

88
00:04:28,000 --> 00:04:31,000
Kwa maneno mengine, tunaweza tu kupata 144 kwa kutumia binary tafuta

89
00:04:31,000 --> 00:04:34,000
ikiwa idadi yote ni amri kutoka chini mpaka juu.

90
00:04:34,000 --> 00:04:38,000
Kama huyu si kesi, tunataka kuwa na uwezo wa kuwatenga nusu ya idadi ya kila hatua.

91
00:04:38,000 --> 00:04:40,000
Hivyo tuna chaguzi 2.

92
00:04:40,000 --> 00:04:43,000
Aidha tunaweza kuchukua orodha zisizochambuliwa na aina hiyo kabla ya kutumia search binary,

93
00:04:43,000 --> 00:04:48,000
au tunaweza kuhakikisha kwamba orodha ya namba ni Iliyopangwa kama sisi kuongeza idadi hiyo.

94
00:04:48,000 --> 00:04:50,000
Hivyo, badala ya kuchagua tu wakati tuna kutafuta,

95
00:04:50,000 --> 00:04:53,000
kwa nini kuweka orodha Iliyopangwa wakati wote?

96
00:04:53,000 --> 00:04:57,000
>> Moja ya njia ya kuweka orodha ya namba sorted wakati huo huo kuruhusu

97
00:04:57,000 --> 00:04:59,000
moja ya kuongeza au hoja namba kutoka kwenye orodha hii

98
00:04:59,000 --> 00:05:02,000
ni kwa kutumia kitu kinachoitwa binary tafuta mti.

99
00:05:02,000 --> 00:05:05,000
tafuta binary mti ni muundo data kwamba ana mali 3.

100
00:05:05,000 --> 00:05:09,000
Kwanza, subtree kushoto wa nodi ina maadili tu kwamba ni chini ya

101
00:05:09,000 --> 00:05:11,000
au sawa na thamani ya nodi.

102
00:05:11,000 --> 00:05:15,000
Pili, haki subtree ya nodi tu ina maadili ambayo ni kubwa kuliko

103
00:05:15,000 --> 00:05:17,000
au sawa na thamani ya nodi.

104
00:05:17,000 --> 00:05:20,000
Na, hatimaye, wote subtrees kushoto na kulia ya nodes wote

105
00:05:20,000 --> 00:05:23,000
ni pia binary tafuta miti.

106
00:05:23,000 --> 00:05:26,000
Hebu tuangalie mfano kwa idadi sawa sisi kutumika mapema.

107
00:05:26,000 --> 00:05:30,000
Kwa wale ambao hawajawahi kuonekana sayansi ya kompyuta mti kabla,

108
00:05:30,000 --> 00:05:34,000
napenda kuanza kwa kuwaambia kwamba sayansi ya kompyuta mti huu hukua chini.

109
00:05:34,000 --> 00:05:36,000
Ndiyo, tofauti na miti wewe wamezoea,

110
00:05:36,000 --> 00:05:38,000
mizizi ya mti sayansi ya kompyuta ni saa ya juu,

111
00:05:38,000 --> 00:05:41,000
na majani yake ni ya chini.

112
00:05:41,000 --> 00:05:45,000
Kila sanduku kidogo inaitwa nodi, na tezi ni kushikamana na kila mmoja kwa edges.

113
00:05:45,000 --> 00:05:48,000
Hivyo mizizi ya mti huu ni thamani ya nodi thamani 13,

114
00:05:48,000 --> 00:05:52,000
ambayo ina watoto 2 nodes na maadili 5 na 34.

115
00:05:52,000 --> 00:05:57,000
subtree ni mti ni sumu tu kwa kuangalia kifungu cha mti mzima.

116
00:05:57,000 --> 00:06:03,000
>> Kwa mfano, subtree kushoto wa 3 nodi ni mti umba nodes 0, 1, na 2.

117
00:06:03,000 --> 00:06:06,000
Hivyo, kama sisi kwenda nyuma ya mali ya mti tafuta binary,

118
00:06:06,000 --> 00:06:09,000
sisi kuona kuwa kila nodi katika mti inajilainisha na mali yote 3, yaani,

119
00:06:09,000 --> 00:06:15,000
subtree kushoto tu ina maadili ambayo ni chini ya au sawa na thamani ya nodi;

120
00:06:15,000 --> 00:06:16,000
haki subtree ya nodes wote

121
00:06:16,000 --> 00:06:19,000
tu ina maadili ambayo ni kubwa kuliko au sawa na thamani ya nodi; na

122
00:06:19,000 --> 00:06:25,000
subtrees wote wa kushoto na wa kulia wa nodi yote pia ni binary tafuta miti.

123
00:06:25,000 --> 00:06:28,000
Ingawa mti huu huonekana tofauti, hii ni halali binary tafuta mti

124
00:06:28,000 --> 00:06:30,000
kwa seti moja ya namba.

125
00:06:30,000 --> 00:06:32,000
Kama jambo la kweli, kuna wengi iwezekanavyo njia ambazo unaweza kuunda

126
00:06:32,000 --> 00:06:35,000
halali binary tafuta mti kutokana na namba hizi.

127
00:06:35,000 --> 00:06:38,000
Naam, hebu kwenda nyuma ya kwanza sisi aliumba.

128
00:06:38,000 --> 00:06:40,000
Basi nini tunaweza kufanya kwa miti hii?

129
00:06:40,000 --> 00:06:44,000
Naam, tunaweza sana tu kupata maadili ya chini na kiwango cha juu.

130
00:06:44,000 --> 00:06:46,000
maadili ya chini inaweza kupatikana kwa mara kwenda kushoto

131
00:06:46,000 --> 00:06:48,000
mpaka hakuna zaidi nodes kutembelea.

132
00:06:48,000 --> 00:06:53,000
Kinyume chake, na kupata moja upeo tu tu inakwenda chini kwa haki wakati kila.

133
00:06:54,000 --> 00:06:56,000
>> Kupata namba nyingine yoyote ambayo si chini au upeo

134
00:06:56,000 --> 00:06:58,000
ni kama rahisi.

135
00:06:58,000 --> 00:07:00,000
Sema sisi ni kuangalia kwa idadi 89.

136
00:07:00,000 --> 00:07:03,000
Sisi tu kuangalia thamani ya nodi ya kila na kwenda kushoto au kulia,

137
00:07:03,000 --> 00:07:06,000
kutegemea kama thamani nodi ni chini ya au kubwa kuliko

138
00:07:06,000 --> 00:07:08,000
moja sisi ni kuangalia kwa.

139
00:07:08,000 --> 00:07:11,000
Hivyo, kuanzia saa mizizi ya 13, tunaona kuwa 89 ni mkuu,

140
00:07:11,000 --> 00:07:13,000
na hivyo sisi kwenda kulia.

141
00:07:13,000 --> 00:07:16,000
Kisha sisi kuona nodi kwa 34, na tena sisi kwenda kulia.

142
00:07:16,000 --> 00:07:20,000
89 bado ni kubwa kuliko 55, hivyo tunaendelea kwenda kulia.

143
00:07:20,000 --> 00:07:24,000
Sisi basi kuja na nodi na thamani ya 144 na kwenda kushoto.

144
00:07:24,000 --> 00:07:26,000
Hakika na tazama, 89 ni haki pale.

145
00:07:26,000 --> 00:07:31,000
>> Kitu kingine kwamba tunaweza kufanya ni kuchapa nje namba zote kwa kufanya traversal ili kuweza.

146
00:07:31,000 --> 00:07:35,000
traversal ili kuweza maana ya magazeti kila kitu nje katika subtree kushoto

147
00:07:35,000 --> 00:07:37,000
ikifuatiwa na uchapishaji nodi yenyewe

148
00:07:37,000 --> 00:07:40,000
na kisha kufuatiwa na uchapishaji kila kitu nje katika haki subtree.

149
00:07:40,000 --> 00:07:43,000
Kwa mfano, hebu kuchukua binary wetu favorite tafuta mti

150
00:07:43,000 --> 00:07:46,000
na magazeti nje ya idadi ili Iliyopangwa.

151
00:07:46,000 --> 00:07:49,000
Sisi kuanza katika mizizi ya 13, lakini kabla ya uchapishaji 13 tuna magazeti nje

152
00:07:49,000 --> 00:07:51,000
kila kitu katika subtree kushoto.

153
00:07:51,000 --> 00:07:55,000
Hivyo sisi kwenda 5. Sisi bado tuna kwenda zaidi chini katika mti hata sisi kupata nodi kushoto-wengi,

154
00:07:55,000 --> 00:07:57,000
ambayo ni sifuri.

155
00:07:57,000 --> 00:08:00,000
Baada ya uchapishaji sifuri, sisi kurudi nyuma hadi 1 na magazeti kwamba nje.

156
00:08:00,000 --> 00:08:03,000
Kisha sisi kwenda subtree haki, ambayo ni 2, na magazeti kwamba nje.

157
00:08:03,000 --> 00:08:05,000
Sasa kwa kuwa sisi ni kosa na kwamba subtree,

158
00:08:05,000 --> 00:08:07,000
tunaweza kurudi nyuma hadi 3 na magazeti nje.

159
00:08:07,000 --> 00:08:11,000
Kuendelea nyuma juu, sisi magazeti 5 na kisha 8.

160
00:08:11,000 --> 00:08:13,000
Sasa kwa kuwa tuna kukamilika nzima kushoto subtree,

161
00:08:13,000 --> 00:08:17,000
tunaweza magazeti nje 13 na kuanza kazi haki subtree.

162
00:08:17,000 --> 00:08:21,000
Sisi hop chini ya 34, lakini kabla ya uchapishaji 34 tuna magazeti nje subtree wake wa kushoto.

163
00:08:21,000 --> 00:08:27,000
Hivyo sisi magazeti nje 21; basi sisi kupata magazeti nje 34 na kutembelea wake wa kulia subtree.

164
00:08:27,000 --> 00:08:31,000
Tangu 55 hana subtree kushoto, sisi magazeti ni nje na kuendelea kwa subtree wake wa kulia.

165
00:08:31,000 --> 00:08:36,000
144 ina subtree kushoto, na hivyo sisi magazeti nje 89, ikifuatiwa na 144,

166
00:08:36,000 --> 00:08:39,000
na hatimaye nodi haki-zaidi ya 233.

167
00:08:39,000 --> 00:08:44,000
Kuna nayo; namba zote ni kuchapishwa kwa amri kutoka chini mpaka juu.

168
00:08:44,000 --> 00:08:47,000
>> Kuongeza kitu mti ni kiasi painless pia.

169
00:08:47,000 --> 00:08:51,000
Wote sisi kufanya ni kuhakikisha kwamba sisi kufuata 3 binary mali mti tafuta

170
00:08:51,000 --> 00:08:53,000
na kisha Insert thamani ambapo kuna nafasi.

171
00:08:53,000 --> 00:08:55,000
Hebu sema tunataka Insert thamani ya 7.

172
00:08:55,000 --> 00:08:58,000
Tangu 7 ni chini ya 13, sisi kwenda kushoto.

173
00:08:58,000 --> 00:09:01,000
Lakini ni mkuu zaidi kuliko 5, hivyo sisi tembeeni kwa haki.

174
00:09:01,000 --> 00:09:04,000
Tangu ni chini ya 8 na 8 ni nodi jani, sisi kuongeza 7 kwa mtoto wa kushoto wa 8.

175
00:09:04,000 --> 00:09:09,000
Voilà! Tumeongeza idadi ya mti binary yetu ya utafutaji.

176
00:09:09,000 --> 00:09:12,000
>> Kama tunaweza kuongeza mambo, sisi ni bora kuwa na uwezo wa kufuta mambo kama vizuri.

177
00:09:12,000 --> 00:09:14,000
Bahati mbaya kwa ajili yetu, kufuta ni kidogo ngumu zaidi -

178
00:09:14,000 --> 00:09:16,000
si mengi, lakini kidogo tu.

179
00:09:16,000 --> 00:09:18,000
Kuna 3 tofauti matukio kwamba tuna kufikiria

180
00:09:18,000 --> 00:09:21,000
wakati kufuta vipengele kutoka miti binary tafuta.

181
00:09:21,000 --> 00:09:24,000
Kwanza, kesi rahisi ni kwamba kipengele ni nodi jani.

182
00:09:24,000 --> 00:09:27,000
Katika kesi hiyo, sisi kufuta tu na kuendelea na biashara yetu.

183
00:09:27,000 --> 00:09:30,000
Sema sisi unataka kufuta 7 kwamba sisi tu aliongeza.

184
00:09:30,000 --> 00:09:34,000
Naam, sisi tu kupata hiyo, kuondoa hiyo, na hiyo ni yake.

185
00:09:35,000 --> 00:09:37,000
kesi ya pili ni kama nodi ina tu 1 mtoto.

186
00:09:37,000 --> 00:09:40,000
Hapa tunaweza kufuta nodi, lakini sisi kwanza kuwa na kuhakikisha

187
00:09:40,000 --> 00:09:42,000
kuungana subtree kwamba ni sasa kushoto wazazi

188
00:09:42,000 --> 00:09:44,000
kwa mzazi wa nodi sisi tu ilifutwa.

189
00:09:44,000 --> 00:09:47,000
Sema sisi unataka kufuta 3 kutoka mti wetu.

190
00:09:47,000 --> 00:09:50,000
Sisi kuchukua kipengele mtoto wa nodi kwamba na ambatisha kwa mzazi wa nodi.

191
00:09:50,000 --> 00:09:54,000
Katika kesi hii, sisi ni sasa attaching 1-5.

192
00:09:54,000 --> 00:09:57,000
Hii kazi bila tatizo kwa sababu tunajua, kulingana na tafuta binary mali mti,

193
00:09:57,000 --> 00:10:01,000
kwamba kila kitu katika subtree kushoto wa 3 ilikuwa chini ya 5.

194
00:10:01,000 --> 00:10:05,000
Sasa kwa kuwa wa 3 subtree ni kuchukuliwa huduma ya, tunaweza kufuta.

195
00:10:05,000 --> 00:10:08,000
kesi ya tatu na ya mwisho ni ngumu zaidi.

196
00:10:08,000 --> 00:10:11,000
Hii ni kesi wakati nodi sisi unataka kufuta ana watoto 2.

197
00:10:11,000 --> 00:10:15,000
Ili kufanya hivyo, sisi kwanza na kupata nodi ambayo ina thamani kubwa ijayo,

198
00:10:15,000 --> 00:10:18,000
wabadilishane mbili, kisha kufuta nodi katika swali.

199
00:10:18,000 --> 00:10:22,000
Notice nodi ambayo ina thamani kubwa ijayo hawezi kuwa na watoto 2 yenyewe

200
00:10:22,000 --> 00:10:26,000
tangu mtoto wake wa kushoto ungekuwa mgombea bora kwa ukubwa ijayo.

201
00:10:26,000 --> 00:10:30,000
Kwa hiyo, kufuta nodi na watoto 2 ni sawa na swapping ya nodes 2,

202
00:10:30,000 --> 00:10:33,000
na kisha kufuta ni kubebwa na 1 ya kanuni 2 aforementioned.

203
00:10:33,000 --> 00:10:37,000
Kwa mfano, hebu kusema tunataka kufuta nodi mizizi, 13.

204
00:10:37,000 --> 00:10:39,000
Jambo la kwanza sisi kufanya ni sisi kupata ijayo kubwa thamani katika mti

205
00:10:39,000 --> 00:10:41,000
ambayo, katika kesi hii, ni 21.

206
00:10:41,000 --> 00:10:46,000
Sisi basi wabadilishane nodes 2, na kufanya 13 na 21 kati jani kundi nodi.

207
00:10:46,000 --> 00:10:49,000
Sasa tunaweza kufuta tu 13.

208
00:10:50,000 --> 00:10:53,000
>> Kama alluded awali, kuna wengi iwezekanavyo njia ya kufanya halali binary tafuta mti.

209
00:10:53,000 --> 00:10:56,000
Bahati mbaya kwa ajili yetu, baadhi ni mbaya zaidi kuliko wengine.

210
00:10:56,000 --> 00:10:59,000
Kwa mfano, kile kinachotokea wakati sisi kujenga binary tafuta mti

211
00:10:59,000 --> 00:11:01,000
kutoka orodha Iliyopangwa ya namba?

212
00:11:01,000 --> 00:11:04,000
Idadi yote ni aliongeza tu kwa haki kwa kila hatua.

213
00:11:04,000 --> 00:11:06,000
Wakati tunataka kutafuta namba,

214
00:11:06,000 --> 00:11:08,000
hatuna uchaguzi bali tu kwa kuangalia haki kwa kila hatua.

215
00:11:08,000 --> 00:11:11,000
Hii si bora kuliko tafuta linear wakati wote.

216
00:11:11,000 --> 00:11:13,000
Ingawa sisi si cover yao hapa, kuna wengine, ngumu zaidi,

217
00:11:13,000 --> 00:11:16,000
data miundo kwamba kuhakikisha kwamba hii haina kutokea.

218
00:11:16,000 --> 00:11:18,000
Hata hivyo, moja rahisi kitu ambayo yanaweza kufanyika ili kuepuka hili ni

219
00:11:18,000 --> 00:11:21,000
tu nasibu shuffle maadili ya pembejeo.

220
00:11:21,000 --> 00:11:26,000
Ni uwezekano mkubwa kwamba kwa bahati random orodha huchanganywa ya idadi ni Iliyopangwa.

221
00:11:26,000 --> 00:11:29,000
Kama hii walikuwa kesi, kasinon hakutaka kukaa katika biashara kwa muda mrefu.

222
00:11:29,000 --> 00:11:31,000
>> Kuna una hiyo.

223
00:11:31,000 --> 00:11:34,000
Wewe sasa kujua kuhusu kutafuta binary na miti binary tafuta.

224
00:11:34,000 --> 00:11:36,000
Mimi nina Patrick Schmid, na hii ni CS50.

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

226
00:11:38,000 --> 00:11:43,000
Moja ya njia dhahiri itakuwa Scan orodha kutoka ... [beep]

227
00:11:43,000 --> 00:11:46,000
... Idadi ya vitu ... yep

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

229
00:11:50,000 --> 00:11:55,000
... Post ya nodi ya 234 ... augh.

230
00:11:55,000 --> 00:11:58,000
>> Yay! Hiyo ilikuwa -