1
00:00:00,000 --> 00:00:02,000
[Powered by Google Translate] [Binārā meklēšana]

2
00:00:02,000 --> 00:00:04,000
[Patrick Schmid - Hārvarda]

3
00:00:04,000 --> 00:00:07,000
[Tas ir CS50. - CS50.TV]

4
00:00:07,000 --> 00:00:09,000
>> Ja es tev sarakstu ar Disney raksturs nosaukumiem alfabētiskā secībā

5
00:00:09,000 --> 00:00:11,000
un lūdza jums atrast Mickey Mouse,

6
00:00:11,000 --> 00:00:13,000
kā jūs iet par to izdarīt?

7
00:00:13,000 --> 00:00:15,000
Viens acīmredzams veids būtu skenēt sarakstu no sākuma

8
00:00:15,000 --> 00:00:18,000
un pārbaudīt katru vārdu, lai redzētu, vai tas ir Mickey.

9
00:00:18,000 --> 00:00:22,000
Bet kā jūs lasīt Aladdin, Alise, Ariel, un tā tālāk,

10
00:00:22,000 --> 00:00:25,000
jūs ātri saprast, ka sākot priekšā sarakstā nebija laba ideja.

11
00:00:25,000 --> 00:00:29,000
Labi, varbūt jums vajadzētu sākt strādāt atpakaļ no saraksta beigās.

12
00:00:29,000 --> 00:00:33,000
Tagad jūs lasīt Tarzan, sašuj, Snow White, un tā tālāk.

13
00:00:33,000 --> 00:00:36,000
Tomēr, tas nav šķist labākais veids, kā iet par to.

14
00:00:36,000 --> 00:00:38,000
>> Nu, vēl viens veids, ka jūs varētu iet par to izdarīt, ir mēģināt sašaurināt

15
00:00:38,000 --> 00:00:41,000
sarakstu vārdi, kas jums ir, lai apskatīt.

16
00:00:41,000 --> 00:00:43,000
Tā kā jūs zināt, ka tie ir alfabētiskā secībā,

17
00:00:43,000 --> 00:00:45,000
Jūs varētu vienkārši apskatīt nosaukumus vidū saraksta

18
00:00:45,000 --> 00:00:49,000
un pārbaudīt, ja Mickey Mouse ir pirms vai pēc šī nosaukuma.

19
00:00:49,000 --> 00:00:51,000
Aplūkojot pēdējo vārdu otrajā ailē

20
00:00:51,000 --> 00:00:54,000
jūs apzināties, ka M Mickey nāk pēc J Jasmine,

21
00:00:54,000 --> 00:00:57,000
tāpēc jūs vienkārši ignorēt pirmo pusi saraksta.

22
00:00:57,000 --> 00:00:59,000
Tad jūs, iespējams apskatīt augšpusē pēdējās slejas

23
00:00:59,000 --> 00:01:02,000
un redzēt, ka tas sākas ar Rapunzel.

24
00:01:02,000 --> 00:01:06,000
Mickey nāk pirms Rapunzel; izskatās, ka mēs varam ignorēt pēdējo aili, kā arī.

25
00:01:06,000 --> 00:01:08,000
Turpinot meklēšanas stratēģijas, jūs ātri redzēt, ka Mickey

26
00:01:08,000 --> 00:01:11,000
ir pirmajā pusē atlikušo vārdu sarakstu

27
00:01:11,000 --> 00:01:14,000
un beidzot atrast Mickey slēpjas starp Merlin un Minnie.

28
00:01:14,000 --> 00:01:17,000
>> Ko jūs tikko izdarīja, bija pamatā bināro meklēšanu.

29
00:01:17,000 --> 00:01:22,000
Tā kā šis vārds nozīmē, tas veic savu meklēšanu pēc stratēģiju bināro jautājumā.

30
00:01:22,000 --> 00:01:24,000
Ko tas nozīmē?

31
00:01:24,000 --> 00:01:27,000
Nu, ņemot vērā, sarakstu šķirotas preces, bināro meklēšanas algoritms bināro lēmumu -

32
00:01:27,000 --> 00:01:33,000
kreisi vai pa labi, lielāks vai mazāks nekā, alfabētiski pirms vai pēc - katrā punktā.

33
00:01:33,000 --> 00:01:35,000
Tagad, kad mums ir vārds, kas iet kopā ar šo meklēšanas algoritmu,

34
00:01:35,000 --> 00:01:38,000
pieņemsim apskatīt vēl viens piemērs, bet tas ar sarakstu šķirotu numuriem laiks.

35
00:01:38,000 --> 00:01:43,000
Saka, ka mēs meklējam numuru 144 šajā sarakstā sakārtoti numuriem.

36
00:01:43,000 --> 00:01:46,000
Tāpat kā līdz šim, mēs atrast numuru, kas ir pa vidu -

37
00:01:46,000 --> 00:01:50,000
kas šajā gadījumā ir 13 - un redzēt, ja 144 ir lielāks vai mazāks par 13.

38
00:01:50,000 --> 00:01:54,000
Tā kā tas ir acīmredzami lielāka nekā 13 mēs varam ignorēt visu, kas ir 13 vai mazāk

39
00:01:54,000 --> 00:01:57,000
un tikai koncentrēties uz atlikušo pusi.

40
00:01:57,000 --> 00:01:59,000
Tā kā mums tagad ir pat vienību skaitu pa kreisi,

41
00:01:59,000 --> 00:02:01,000
Mēs vienkārši izvēlēties numuru, kas ir tuvu vidū.

42
00:02:01,000 --> 00:02:03,000
Šajā gadījumā mēs izvēlamies 55.

43
00:02:03,000 --> 00:02:06,000
Mēs varētu būt tikpat viegli izvēlēti 89.

44
00:02:06,000 --> 00:02:11,000
Labi. Atkal, 144 ir lielāks par 55, tāpēc mums iet uz labo pusi.

45
00:02:11,000 --> 00:02:14,000
Par laimi mums, nākamais vidus skaits ir 144,

46
00:02:14,000 --> 00:02:16,000
viens mēs meklējam.

47
00:02:16,000 --> 00:02:21,000
Tātad, lai atrastu 144 izmantojot bināro meklēšanu, mēs esam spējīgi atrast tikai 3 soļi.

48
00:02:21,000 --> 00:02:24,000
Ja mēs būtu izmantota lineārā meklēt šeit, tas būtu jāņem mums 12 soļiem.

49
00:02:24,000 --> 00:02:28,000
Kā Faktiski, jo šī meklēšanas metode pusītes vienību skaitu

50
00:02:28,000 --> 00:02:31,000
tas ir skatīties uz katru soli, tas atradīs posteni tiek meklējot

51
00:02:31,000 --> 00:02:35,000
kas par žurnālu skaitu posteņu sarakstā.

52
00:02:35,000 --> 00:02:37,000
Tagad, ka mēs esam redzējuši 2 piemēri, pieņemsim to apskatīt

53
00:02:37,000 --> 00:02:41,000
daži pseudocode par rekursīvs funkciju, kas īsteno bināro meklēšanu.

54
00:02:41,000 --> 00:02:44,000
Sākot no augšas, mēs redzam, ka mums ir jāatrod funkciju, kas aizņem 4 argumentus:

55
00:02:44,000 --> 00:02:47,000
Galvenais, masīvs, min, un maks.

56
00:02:47,000 --> 00:02:51,000
Galvenais ir numurs, ko mēs meklējam, tā 144 iepriekšējā piemērā.

57
00:02:51,000 --> 00:02:54,000
Masīvs ir saraksts skaitļu ka mēs meklējam.

58
00:02:54,000 --> 00:02:57,000
Min un max ir indeksi minimālo un maksimālo amatos

59
00:02:57,000 --> 00:02:59,000
ka mēs šobrīd meklē.

60
00:02:59,000 --> 00:03:03,000
Tātad, kad mēs sākam, min būs nulle un maks būs maksimālais indekss masīvā.

61
00:03:03,000 --> 00:03:07,000
Kā mēs sašaurinātu meklēšanu uz leju, mēs atjaunināt min un max

62
00:03:07,000 --> 00:03:10,000
ir tikai diapazonā, ka mēs joprojām meklējam collas

63
00:03:10,000 --> 00:03:12,000
>> Pieņemsim izlaist līdz interesantu daļai pirmās.

64
00:03:12,000 --> 00:03:14,000
Pirmā lieta, ko mēs darām, ir atrast viduspunktā,

65
00:03:14,000 --> 00:03:19,000
indekss, kas ir pusceļā starp min un max masīva, ka mēs joprojām apsver.

66
00:03:19,000 --> 00:03:22,000
Tad mēs apskatīt vērtību masīva šajā viduspunktā vietā

67
00:03:22,000 --> 00:03:25,000
un redzēt, ja skaitlis, ko mēs meklējam, ir mazāks nekā šī taustiņa.

68
00:03:25,000 --> 00:03:27,000
Ja šajā pozīcijā skaits ir mazāks,

69
00:03:27,000 --> 00:03:31,000
tad tas nozīmē, ka galvenais ir lielāks nekā visas numuriem pa kreisi no šīs pozīcijas.

70
00:03:31,000 --> 00:03:33,000
Tātad, mēs varam zvanīt bināro meklēšanas funkciju atkal,

71
00:03:33,000 --> 00:03:36,000
bet šoreiz atjaunināšanas min un max parametrus, lai lasītu tikai pusi

72
00:03:36,000 --> 00:03:40,000
kas ir lielāks vai vienāds ar vērtību mēs vienkārši paskatījās.

73
00:03:40,000 --> 00:03:44,000
No otras puses, ja galvenais ir mazāks nekā skaits, ņemot vērā pašreizējo viduspunktā masīva,

74
00:03:44,000 --> 00:03:47,000
Mēs gribam doties pa kreisi un ignorēt visus numurus, kas ir lielāka.

75
00:03:47,000 --> 00:03:52,000
Atkal, mēs saucam bināro meklēšanu, bet šoreiz ar loku min un max UPDATED

76
00:03:52,000 --> 00:03:54,000
iekļaut tikai apakšējo pusi.

77
00:03:54,000 --> 00:03:57,000
Ja pie pašreizējā viduspunktā masīvā vērtība ir ne

78
00:03:57,000 --> 00:04:01,000
lielāki nekā ne mazāks kā atslēgu, tad tai ir jābūt vienādai ar atslēgu.

79
00:04:01,000 --> 00:04:05,000
Tātad, mēs varam vienkārši atgriezties pašreizējo viduspunktā indeksu, un mēs esam darīts.

80
00:04:05,000 --> 00:04:09,000
Visbeidzot, šī pārbaude šeit ir lietas, ka numurs

81
00:04:09,000 --> 00:04:11,000
faktiski nav masīvā numurus mēs meklējam.

82
00:04:11,000 --> 00:04:14,000
Ja maksimālais indekss diapazona ka mēs meklējam

83
00:04:14,000 --> 00:04:17,000
ir arvien mazāks par minimāli, tas nozīmē, ka mēs esam aizgājuši pārāk tālu.

84
00:04:17,000 --> 00:04:20,000
Tā skaits nebija ieejas masīvs, mēs atgriežamies -1

85
00:04:20,000 --> 00:04:24,000
norādīt, ka nekas netika atrasts.

86
00:04:24,000 --> 00:04:26,000
>> Jums var būt ievērojuši, ka šis algoritms darbu,

87
00:04:26,000 --> 00:04:28,000
skaitļu saraksts ir sakārtots.

88
00:04:28,000 --> 00:04:31,000
Citiem vārdiem sakot, mēs varam atrast tikai 144 izmantojot bināro meklēšanu

89
00:04:31,000 --> 00:04:34,000
ja visi skaitļi ir pasūtīts no zemākā līdz augstākajam.

90
00:04:34,000 --> 00:04:38,000
Ja tas tā nav, mēs nespētu izslēgt pusi skaitu katrā posmā.

91
00:04:38,000 --> 00:04:40,000
Tātad mums ir 2 iespējas.

92
00:04:40,000 --> 00:04:43,000
Vai nu mēs varam pieņemt nešķirotu sarakstu un šķirot, pirms to izmanto bināro meklēšanu,

93
00:04:43,000 --> 00:04:48,000
vai mēs varam pārliecināties, ka skaitļu saraksts ir sakārtots, jo mēs pievienot numurus uz to.

94
00:04:48,000 --> 00:04:50,000
Tātad, tā vietā, šķirošanu tikai tad, kad mums ir jāmeklē,

95
00:04:50,000 --> 00:04:53,000
kāpēc ne saglabāt sarakstu sakārtoti visu laiku?

96
00:04:53,000 --> 00:04:57,000
>> Viens veids, kā uzturēt sarakstu numurus sakārtoti vienlaikus ļaujot

97
00:04:57,000 --> 00:04:59,000
viens pievienot vai pārvietot numurus no šī saraksta

98
00:04:59,000 --> 00:05:02,000
ir, izmantojot kaut ko sauc bināro meklēšanas koku.

99
00:05:02,000 --> 00:05:05,000
Binārs meklēšanas koks ir datu struktūra, kas ir 3 īpašības.

100
00:05:05,000 --> 00:05:09,000
Pirmkārt, pa kreisi apakškoka jebkura mezglā ir tikai vērtības, kas ir mazāk nekā

101
00:05:09,000 --> 00:05:11,000
vai vienāds ar mezglu vērtības.

102
00:05:11,000 --> 00:05:15,000
Otrkārt, tiesības apakškoka no mezgla tikai satur vērtības, kas ir lielākas nekā

103
00:05:15,000 --> 00:05:17,000
vai vienāds ar mezglu vērtības.

104
00:05:17,000 --> 00:05:20,000
Un, visbeidzot, gan kreiso un labo subtrees visu mezglu

105
00:05:20,000 --> 00:05:23,000
Ir arī bināro meklēšanas koku.

106
00:05:23,000 --> 00:05:26,000
Apskatīsim piemēru ar tiem pašiem numuriem mēs izmantojām agrāk.

107
00:05:26,000 --> 00:05:30,000
Attiecībā uz tiem no jums, kas nekad nav redzējuši datorzinātnes koks pirms,

108
00:05:30,000 --> 00:05:34,000
ļaujiet man sākt ar stāsta jums, ka datorzinātņu koks aug uz leju.

109
00:05:34,000 --> 00:05:36,000
Jā, atšķirībā kokiem jums ir pieraduši,

110
00:05:36,000 --> 00:05:38,000
No datora zinātnes koku saknes ir augšā,

111
00:05:38,000 --> 00:05:41,000
un lapas ir apakšā.

112
00:05:41,000 --> 00:05:45,000
Katrs maz kaste sauc mezglā, un mezgli ir saistīti viens ar otru ar malām.

113
00:05:45,000 --> 00:05:48,000
Tātad šī koka sakne ir mezglu vērtība ar vērtību 13,

114
00:05:48,000 --> 00:05:52,000
kas ir 2 bērni mezglus ar vērtībām 5 un 34.

115
00:05:52,000 --> 00:05:57,000
Apakškoka ir koks, kas veidojas tikai skatoties uz apakšiedaļu visa koku.

116
00:05:57,000 --> 00:06:03,000
>> Piemēram, kreisā apakškoka no mezgla 3 ir koks, ko rada mezglu 0, 1, 2 un.

117
00:06:03,000 --> 00:06:06,000
Tātad, ja mēs ejam atpakaļ uz bināro meklēšanas koku īpašības,

118
00:06:06,000 --> 00:06:09,000
mēs redzam, ka katrs koks mezgls atbilst visām 3 īpašībām, proti,

119
00:06:09,000 --> 00:06:15,000
kreisi apakškoka satur tikai vērtības, kas ir mazāks vai vienāds ar mezglu vērtības;

120
00:06:15,000 --> 00:06:16,000
tiesības apakškoka visu mezglu

121
00:06:16,000 --> 00:06:19,000
satur tikai vērtības, kas ir lielāka vai vienāda ar mezglu vērtības un

122
00:06:19,000 --> 00:06:25,000
gan kreisās un labās subtrees visu mezglu arī ir binārie meklēšanas koki.

123
00:06:25,000 --> 00:06:28,000
Kaut arī šī koks izskatās atšķirīgi, tas ir derīgs bināro meklēšanas koku

124
00:06:28,000 --> 00:06:30,000
par tiem pašiem numuriem.

125
00:06:30,000 --> 00:06:32,000
Kā Faktiski, ir daudz iespējamie veidi, kā jūs varat izveidot

126
00:06:32,000 --> 00:06:35,000
derīgs bināro meklēšanas koku no šiem skaitļiem.

127
00:06:35,000 --> 00:06:38,000
Nu, iesim atpakaļ uz pirmo mēs izveidojām.

128
00:06:38,000 --> 00:06:40,000
Tātad, ko mēs varam darīt ar šiem kokiem?

129
00:06:40,000 --> 00:06:44,000
Nu, mēs varam ļoti vienkārši atrast minimālās un maksimālās vērtības.

130
00:06:44,000 --> 00:06:46,000
Minimālās vērtības var atrast, vienmēr dodas uz kreiso pusi

131
00:06:46,000 --> 00:06:48,000
līdz nav vairāk mezgli apmeklēt.

132
00:06:48,000 --> 00:06:53,000
Savukārt, lai iegūtu maksimālo viens vienkārši tikai iet uz leju pa labi katrā laikā.

133
00:06:54,000 --> 00:06:56,000
>> Meklējot kādu citu numuru, kas nav minimālais vai maksimālais

134
00:06:56,000 --> 00:06:58,000
ir tikpat vienkārši.

135
00:06:58,000 --> 00:07:00,000
Saka, ka mēs meklējam skaita 89.

136
00:07:00,000 --> 00:07:03,000
Mēs vienkārši pārbaudītu vērtību katru mezglu un iet pa kreisi vai pa labi,

137
00:07:03,000 --> 00:07:06,000
atkarībā no tā, vai mezgla vērtība ir mazāka vai lielāka par

138
00:07:06,000 --> 00:07:08,000
viens mēs meklējam.

139
00:07:08,000 --> 00:07:11,000
Tātad, sākot saknē 13, redzam, ka 89 ir lielāks,

140
00:07:11,000 --> 00:07:13,000
un tāpēc mēs ejam uz labo pusi.

141
00:07:13,000 --> 00:07:16,000
Tad mēs redzam mezglu 34, un atkal mēs ejam uz labo pusi.

142
00:07:16,000 --> 00:07:20,000
89 joprojām ir lielāka par 55, tāpēc mēs turpinām iet uz labo pusi.

143
00:07:20,000 --> 00:07:24,000
Mēs pēc tam nāk klajā ar mezglu ar vērtību 144 un iet pa kreisi.

144
00:07:24,000 --> 00:07:26,000
Lo un redzi, 89 ir labi tur.

145
00:07:26,000 --> 00:07:31,000
>> Vēl viena lieta, ko mēs varam darīt, ir izdrukāt visus numurus ar veicot inorder šķērsošana.

146
00:07:31,000 --> 00:07:35,000
Inorder šķērsošana nozīmē izdrukāt viss, kas kreisajā apakškoka

147
00:07:35,000 --> 00:07:37,000
seko apdrukāšana mezglā pati

148
00:07:37,000 --> 00:07:40,000
un pēc tam seko apdrukāšana viss, kas labi apakškoka.

149
00:07:40,000 --> 00:07:43,000
Piemēram, pieņemsim mūsu mīļākie bināro meklēšanas koku

150
00:07:43,000 --> 00:07:46,000
un izdrukāt skaitļus sakārtoti secībā.

151
00:07:46,000 --> 00:07:49,000
Mēs sākam pie saknes 13, bet līdz 13 drukāšanas mums ir izdrukāt

152
00:07:49,000 --> 00:07:51,000
viss kreisi apakškoka.

153
00:07:51,000 --> 00:07:55,000
Tāpēc mēs ejam līdz 5. Mums vēl ir iet dziļāk kokā līdz mēs atrast kreisās visvairāk mezglā,

154
00:07:55,000 --> 00:07:57,000
kas ir nulle.

155
00:07:57,000 --> 00:08:00,000
Pēc nulles drukāšanu, mēs ejam atpakaļ līdz 1 un izdrukāt ka out.

156
00:08:00,000 --> 00:08:03,000
Tad mēs ejam uz labo apakškoka, kas ir 2, un drukāt, ka out.

157
00:08:03,000 --> 00:08:05,000
Tagad, ka mēs esam darīts ar to apakškoka,

158
00:08:05,000 --> 00:08:07,000
mēs varam doties atpakaļ līdz 3 un izdrukāt to ārā.

159
00:08:07,000 --> 00:08:11,000
Turpinot atpakaļ uz augšu, mēs drukāt 5 un pēc tam 8.

160
00:08:11,000 --> 00:08:13,000
Tagad, kad mums ir pabeigts viss atstāja apakškoka,

161
00:08:13,000 --> 00:08:17,000
mēs varam izdrukāt 13 un sākt darbu pie labi apakškoka.

162
00:08:17,000 --> 00:08:21,000
Mēs hop līdz 34 gadiem, bet pirms 34 drukāšanas mums ir izdrukāt tās kreisajā apakškoka.

163
00:08:21,000 --> 00:08:27,000
Tāpēc mēs izdrukāt 21, tad mēs izdrukāt 34 un apmeklēt tās tiesības apakškoka.

164
00:08:27,000 --> 00:08:31,000
Tā 55 ir ne pa kreisi apakškoka, mēs to izdrukāt un tālāk uz tās tiesības apakškoka.

165
00:08:31,000 --> 00:08:36,000
144 ir kreisā apakškoka, un tāpēc mēs izdrukāt 89, seko 144,

166
00:08:36,000 --> 00:08:39,000
un visbeidzot labo visvairāk mezgla 233.

167
00:08:39,000 --> 00:08:44,000
Tur jums ir tas, visi numuri ir izdrukāti, lai no zemākās uz augstāko.

168
00:08:44,000 --> 00:08:47,000
>> Pievienojot kaut uz koku ir salīdzinoši nesāpīga, kā arī.

169
00:08:47,000 --> 00:08:51,000
Viss, kas mums jādara, ir pārliecināties, ka mēs izpildiet 3 binārā meklēšanas koku īpašības

170
00:08:51,000 --> 00:08:53,000
un pēc tam ievietot vērtību, kur ir telpa.

171
00:08:53,000 --> 00:08:55,000
Pieņemsim, ka mēs vēlamies, lai ievietotu vērtību 7.

172
00:08:55,000 --> 00:08:58,000
Tā 7 ir mazāk nekā 13, mēs ejam pa kreisi.

173
00:08:58,000 --> 00:09:01,000
Bet tas ir lielāks par 5, lai mēs traversa pa labi.

174
00:09:01,000 --> 00:09:04,000
Tā kā tas ir mazāk nekā 8 un 8 lapu mezglā, mēs pievienojam 7 līdz kreisajā bērnam gada 8.

175
00:09:04,000 --> 00:09:09,000
Voila! Mēs esam pievienojuši vairākus mūsu bināro meklēšanas koku.

176
00:09:09,000 --> 00:09:12,000
>> Ja mēs varam pievienot lietas, mēs labāk varētu izdzēst lietas, kā arī.

177
00:09:12,000 --> 00:09:14,000
Diemžēl mums, dzēšot ir nedaudz sarežģītāk -

178
00:09:14,000 --> 00:09:16,000
nav daudz, bet tikai nedaudz.

179
00:09:16,000 --> 00:09:18,000
Ir 3 dažādi scenāriji, kas mums ir jāapsver

180
00:09:18,000 --> 00:09:21,000
dzēšot elementus no binārā meklēšanas kokiem.

181
00:09:21,000 --> 00:09:24,000
Pirmkārt, vienkāršākais lieta ir tā, ka elements ir lapu mezglā.

182
00:09:24,000 --> 00:09:27,000
Šajā gadījumā mēs vienkārši izdzēsiet to un iet uz mūsu biznesu.

183
00:09:27,000 --> 00:09:30,000
Saka, ka mēs vēlamies izdzēst 7 ka mēs tikko pievienotās.

184
00:09:30,000 --> 00:09:34,000
Nu, mēs vienkārši atrast, noņemiet to, un tas arī viss.

185
00:09:35,000 --> 00:09:37,000
Nākamais gadījums ir tad, ja mezglā ir tikai 1 bērns.

186
00:09:37,000 --> 00:09:40,000
Šeit mēs varam dzēst mezglā, bet mums vispirms ir jāpārliecinās

187
00:09:40,000 --> 00:09:42,000
savienot apakškoka kas tagad atstāj parentless

188
00:09:42,000 --> 00:09:44,000
uz mātes mezglā mēs vienkārši izdzēsts.

189
00:09:44,000 --> 00:09:47,000
Saka, ka mēs vēlamies, lai izdzēstu 3 no mūsu koka.

190
00:09:47,000 --> 00:09:50,000
Mēs ņemam bērnu elements šajā mezglā un pievienojiet to mātes mezglā.

191
00:09:50,000 --> 00:09:54,000
Šajā gadījumā, mēs tagad pievienojot no 1 līdz 5 x.

192
00:09:54,000 --> 00:09:57,000
Tas darbojas bez problēmām, jo ​​mēs zinām, saskaņā ar bināro meklēšanas koku īpašumu,

193
00:09:57,000 --> 00:10:01,000
ka kreisajā apakškoka gada 3 viss bija mazāks nekā 5.

194
00:10:01,000 --> 00:10:05,000
Tagad, 3'S apakškoka ir rūpēsies, mēs varam izdzēst.

195
00:10:05,000 --> 00:10:08,000
Trešais un pēdējais gadījums ir vissarežģītākais.

196
00:10:08,000 --> 00:10:11,000
Tas ir gadījums, kad mezglu mēs vēlamies izdzēst ir 2 bērni.

197
00:10:11,000 --> 00:10:15,000
Lai to izdarītu, mums vispirms ir jāatrod mezglu, kas ir nākamo lielāko vērtību,

198
00:10:15,000 --> 00:10:18,000
swap divus, un pēc tam izdzēsiet mezglu jautājumu.

199
00:10:18,000 --> 00:10:22,000
Paziņojums mezglu, kas ir nākamais lielākais vērtību nevar būt 2 bērni sevi

200
00:10:22,000 --> 00:10:26,000
jo tās kreisajā bērns būtu labāks kandidāts par nākamo lielāko.

201
00:10:26,000 --> 00:10:30,000
Tādēļ, dzēšot mezglu ar 2 bērniem sasniedz pārnešana no 2 mezgliem,

202
00:10:30,000 --> 00:10:33,000
un pēc tam atmetot strādājot ar 1 no 2 iepriekšminētos noteikumus.

203
00:10:33,000 --> 00:10:37,000
Piemēram, pieņemsim, ka mēs vēlamies izdzēst saknes mezglā, 13.

204
00:10:37,000 --> 00:10:39,000
Pirmā lieta, ko mēs darām, ir mums atrast nākamo lielāko vērtību kokā

205
00:10:39,000 --> 00:10:41,000
kas šajā gadījumā ir 21.

206
00:10:41,000 --> 00:10:46,000
Mēs tad mijmaiņas 2 mezglus, padarot 13 lapu un 21 Centrālā grupa mezglā.

207
00:10:46,000 --> 00:10:49,000
Tagad mēs varam vienkārši izdzēst 13.

208
00:10:50,000 --> 00:10:53,000
>> Kā pieminēja iepriekš, ir daudz iespējamie veidi, kā padarīt derīgu bināro meklēšanas koku.

209
00:10:53,000 --> 00:10:56,000
Diemžēl mums, daži ir sliktāks nekā citi.

210
00:10:56,000 --> 00:10:59,000
Piemēram, kas notiek, ja mēs izveidotu bināro meklēšanas koku

211
00:10:59,000 --> 00:11:01,000
no sakārtoti sarakstu numuriem?

212
00:11:01,000 --> 00:11:04,000
Visi numuri ir tikai pievienota labi pie katra soļa.

213
00:11:04,000 --> 00:11:06,000
Ja mēs gribam, lai meklētu numuru,

214
00:11:06,000 --> 00:11:08,000
Mums nav citas izvēles, bet tikai apskatīt labi pie katra soļa.

215
00:11:08,000 --> 00:11:11,000
Tas nav labāk nekā lineāri meklēšanā vispār.

216
00:11:11,000 --> 00:11:13,000
Kaut arī mēs nesedz tos šeit, tur ir citi, daudz sarežģītāka,

217
00:11:13,000 --> 00:11:16,000
datu struktūras, kas padara pārliecināts, ka tas nenotiek.

218
00:11:16,000 --> 00:11:18,000
Tomēr viena vienkārša lieta, ko var darīt, lai izvairītos no šī ir

219
00:11:18,000 --> 00:11:21,000
līdz tikai nejauši shuffle ievades vērtībām.

220
00:11:21,000 --> 00:11:26,000
Tas ir ļoti maz ticams, ka ar izlases izredzes iegrozījās sarakstu numuriem ir sakārtots.

221
00:11:26,000 --> 00:11:29,000
Ja tas tā būtu, kazino nevarētu palikt biznesā uz ilgu laiku.

222
00:11:29,000 --> 00:11:31,000
>> Tur jums ir to.

223
00:11:31,000 --> 00:11:34,000
Jūs tagad zināt par bināro meklēšanu un bināro meklēšanas koku.

224
00:11:34,000 --> 00:11:36,000
Es esmu Patriks Schmid, un tas ir CS50.

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

226
00:11:38,000 --> 00:11:43,000
Viens acīmredzams veids būtu skenēt sarakstu no ... [pīkstiens]

227
00:11:43,000 --> 00:11:46,000
... Vienību skaits ... yep

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

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

230
00:11:55,000 --> 00:11:58,000
>> Yay! Tas bija -