1
00:00:00,000 --> 00:00:02,000
[Powered by Google Translate] [Бинарни Пребарување]

2
00:00:02,000 --> 00:00:04,000
[Патрик Шмид - Универзитетот Харвард]

3
00:00:04,000 --> 00:00:07,000
[Ова е CS50. - CS50.TV]

4
00:00:07,000 --> 00:00:09,000
>> Ако ти даде листа на Дизни карактер имиња по азбучен ред

5
00:00:09,000 --> 00:00:11,000
и те праша да се најде Мики Маус,

6
00:00:11,000 --> 00:00:13,000
како ќе одат за тоа?

7
00:00:13,000 --> 00:00:15,000
Еден очигледен начин ќе биде да го скенира листата од почетокот

8
00:00:15,000 --> 00:00:18,000
и проверете секое име да се види дали тоа е Мики.

9
00:00:18,000 --> 00:00:22,000
Но, како што ќе прочитате Аладин, Алис, Ариел, и така натаму,

10
00:00:22,000 --> 00:00:25,000
вие брзо ќе сфатат дека со почеток во предниот дел на листа не е добра идеја.

11
00:00:25,000 --> 00:00:29,000
Океј, можеби ќе треба да почнат да работат наназад од крајот на листата.

12
00:00:29,000 --> 00:00:33,000
Сега ќе прочитате Тарзан, бод, Снежана, и така натаму.

13
00:00:33,000 --> 00:00:36,000
Сепак, ова не изгледа како на најдобар начин да се обратите за тоа.

14
00:00:36,000 --> 00:00:38,000
>> Па, уште еден начин на кој можете да се обратите за тоа е да се обиде да го стесните

15
00:00:38,000 --> 00:00:41,000
листа на имиња кои ќе мора да се погледне.

16
00:00:41,000 --> 00:00:43,000
Бидејќи знаете дека тие се по азбучен ред,

17
00:00:43,000 --> 00:00:45,000
може само да се погледне на имиња во средината на листата

18
00:00:45,000 --> 00:00:49,000
и проверете дали Мики Маус е пред или после ова име.

19
00:00:49,000 --> 00:00:51,000
Гледајќи презиме во втората колона

20
00:00:51,000 --> 00:00:54,000
дека ќе сфатат дека М за Мики доаѓа по J за јасмин,

21
00:00:54,000 --> 00:00:57,000
, па можете едноставно ќе ги игнорира првата половина на листата.

22
00:00:57,000 --> 00:00:59,000
Тогаш веројатно ќе се погледне на врвот на последната колона

23
00:00:59,000 --> 00:01:02,000
и види дека тоа започнува со Rapunzel.

24
00:01:02,000 --> 00:01:06,000
Мики доаѓа пред Rapunzel; изгледа како можеме да го игнорираме последната колона, како и.

25
00:01:06,000 --> 00:01:08,000
Продолжување на пребарување стратегија, вие брзо ќе се види дека Мики

26
00:01:08,000 --> 00:01:11,000
е во првата половина од преостанатите листа на имиња

27
00:01:11,000 --> 00:01:14,000
и конечно најде Мики крие меѓу Мерлин и Мини.

28
00:01:14,000 --> 00:01:17,000
>> Што ли само не беше во основа бинарни пребарување.

29
00:01:17,000 --> 00:01:22,000
Бидејќи ова име имплицира, го врши својата потрага стратегија во бинарен прашање.

30
00:01:22,000 --> 00:01:24,000
Што значи ова?

31
00:01:24,000 --> 00:01:27,000
Па, со оглед на листа на подредени позиции, бинарна пребарување алгоритам прави бинарни одлука -

32
00:01:27,000 --> 00:01:33,000
лево или десно, поголема или помала од, по азбучен ред пред или после - на секоја точка.

33
00:01:33,000 --> 00:01:35,000
Сега кога имаме име кое оди заедно со ова пребарување алгоритам,

34
00:01:35,000 --> 00:01:38,000
ајде да погледнеме еден пример, но овој пат со листа на подредени броеви.

35
00:01:38,000 --> 00:01:43,000
Велат ние сме во потрага по бројот 144 во оваа листа на подредени броеви.

36
00:01:43,000 --> 00:01:46,000
Исто како и порано, ги наоѓаме број, кој е во средината -

37
00:01:46,000 --> 00:01:50,000
кој во овој случај е 13 - и види дали 144 е поголема или помала од 13.

38
00:01:50,000 --> 00:01:54,000
Бидејќи тоа е јасно поголема од 13, ние може да го игнорира она што е 13 или помалку

39
00:01:54,000 --> 00:01:57,000
и само се концентрира на преостанатите половина.

40
00:01:57,000 --> 00:01:59,000
Бидејќи ние сега имаат дури и број на ставки лево,

41
00:01:59,000 --> 00:02:01,000
ние едноставно изберете број кој е блиску до средината.

42
00:02:01,000 --> 00:02:03,000
Во овој случај ние да изберат 55.

43
00:02:03,000 --> 00:02:06,000
Ние би можеле да исто како лесно избрани 89.

44
00:02:06,000 --> 00:02:11,000
Во ред. Повторно, 144 е поголем од 55, па ќе одиме кон десно.

45
00:02:11,000 --> 00:02:14,000
За среќа за нас, следниот средината број е 144,

46
00:02:14,000 --> 00:02:16,000
оној што го барате.

47
00:02:16,000 --> 00:02:21,000
Значи, со цел да се најде 144 користење на бинарни пребарување, ние сме во можност да го најдете во само 3 чекори.

48
00:02:21,000 --> 00:02:24,000
Ако ние би ги користеле линеарно пребарување тука, тоа ќе нè однесеше 12 чекори.

49
00:02:24,000 --> 00:02:28,000
Како што, впрочем, бидејќи ова пребарување метод половини на бројот на предмети

50
00:02:28,000 --> 00:02:31,000
тоа треба да се погледне во на секој чекор, ќе најдете ставка што е во потрага по

51
00:02:31,000 --> 00:02:35,000
во врска со најавите на бројот на ставки во листата.

52
00:02:35,000 --> 00:02:37,000
Сега дека ние сме виделе 2 примери, ајде да ги разгледаме во

53
00:02:37,000 --> 00:02:41,000
некои pseudocode за рекурзивен функција што ја спроведува бинарни пребарување.

54
00:02:41,000 --> 00:02:44,000
Почнувајќи од врвот, можеме да видиме дека ние треба да се најде функција која трае 4 аргументи:

55
00:02:44,000 --> 00:02:47,000
клуч, низа, мин, и макс.

56
00:02:47,000 --> 00:02:51,000
Клучот е бројот што го барате, па 144 во претходниот пример.

57
00:02:51,000 --> 00:02:54,000
Низа е на листата на броеви кои се бараат.

58
00:02:54,000 --> 00:02:57,000
Мин и макс се индексите на минималната и максималната позиции

59
00:02:57,000 --> 00:02:59,000
дека ние сме во моментов во потрага на.

60
00:02:59,000 --> 00:03:03,000
Па кога ќе почне, мин ќе биде нула и макс ќе биде максималната индекс на низата.

61
00:03:03,000 --> 00:03:07,000
Како што насочите пребарување надолу, ние ќе ги ажурира мин и макс

62
00:03:07,000 --> 00:03:10,000
да биде само опсег што ние се уште се гледа внатре

63
00:03:10,000 --> 00:03:12,000
>> Ајде да прескокнете на интересен дел во прв план.

64
00:03:12,000 --> 00:03:14,000
Првото нешто што ние направите е да најдете средина,

65
00:03:14,000 --> 00:03:19,000
на индекс, кој е на половина пат помеѓу MIN и MAX на низата дека ние се уште размислува.

66
00:03:19,000 --> 00:03:22,000
Тогаш ние се погледне на вредноста на низата во тоа средина локација

67
00:03:22,000 --> 00:03:25,000
и види дали бројот што го барате е помала од онаа клуч.

68
00:03:25,000 --> 00:03:27,000
Ако бројот на таа позиција е помала,

69
00:03:27,000 --> 00:03:31,000
тогаш тоа значи дека клучот е поголем од сите броеви од лево на таа позиција.

70
00:03:31,000 --> 00:03:33,000
Значи можеме да го наречеме бинарни пребарување функција повторно,

71
00:03:33,000 --> 00:03:36,000
но овој пат ажурирање на мин и макс параметри за да прочитате само половина

72
00:03:36,000 --> 00:03:40,000
што е поголема или еднаква на вредноста ние само погледна.

73
00:03:40,000 --> 00:03:44,000
Од друга страна, ако клучот е помал од бројот на моменталната средина на низа,

74
00:03:44,000 --> 00:03:47,000
ние сакаме да одиме на лево и да го игнорира сите броеви кои се многу поголеми.

75
00:03:47,000 --> 00:03:52,000
Повторно, ние го нарекуваме бинарен за пребарување, но овој пат со спектар на мин и макс ажурирани

76
00:03:52,000 --> 00:03:54,000
да се вклучат само на долната половина.

77
00:03:54,000 --> 00:03:57,000
Ако вредноста на тековната средина во низа не е ниту

78
00:03:57,000 --> 00:04:01,000
поголема од ниту помала од клуч, тогаш тоа мора да биде еднаква на клучот.

79
00:04:01,000 --> 00:04:05,000
Така, ние едноставно може да се врати на тековната средина индекс, и ние ќе завршиш.

80
00:04:05,000 --> 00:04:09,000
Конечно, оваа проверка е тука за случајот дека бројот

81
00:04:09,000 --> 00:04:11,000
всушност не е во низа од броеви што се бараат.

82
00:04:11,000 --> 00:04:14,000
Ако максималната индексот на опсег дека ние сме во потрага по

83
00:04:14,000 --> 00:04:17,000
е секогаш помал од минималниот, тоа значи дека ние сме отишле предалеку.

84
00:04:17,000 --> 00:04:20,000
Бидејќи бројот не беше во влез низа, ние се врати -1

85
00:04:20,000 --> 00:04:24,000
за да се покаже дека ништо не беше пронајдена.

86
00:04:24,000 --> 00:04:26,000
>> Може да се забележи дека за овој алгоритам на работа,

87
00:04:26,000 --> 00:04:28,000
листата на броеви мора да бидат подредени.

88
00:04:28,000 --> 00:04:31,000
Со други зборови, ние може само да најде 144 користење на бинарни пребарување

89
00:04:31,000 --> 00:04:34,000
ако сите броеви се подредени од најниските до највисоките.

90
00:04:34,000 --> 00:04:38,000
Ако ова не е случај, ние не би можеле да се исклучат половина на броеви во секој чекор.

91
00:04:38,000 --> 00:04:40,000
Значи имаме 2 опции.

92
00:04:40,000 --> 00:04:43,000
Или можеме да преземе несортиран листа и сортирање пред да го користите бинарни пребарување,

93
00:04:43,000 --> 00:04:48,000
или можеме да бидете сигурни дека на листата на броеви се подредени како што ние додадете броеви во неа.

94
00:04:48,000 --> 00:04:50,000
Така, наместо на сортирање само кога мораме да пребарување,

95
00:04:50,000 --> 00:04:53,000
зошто да не чува листа подредена на сите времиња?

96
00:04:53,000 --> 00:04:57,000
>> Еден начин да чувате листа на броеви подредени додека истовремено овозможувајќи

97
00:04:57,000 --> 00:04:59,000
еден да додадете или преместување броеви од листата

98
00:04:59,000 --> 00:05:02,000
е со користење на нешто што се нарекува бинарен пребарување дрво.

99
00:05:02,000 --> 00:05:05,000
А бинарни пребарување дрво е податочна структура која има 3 својства.

100
00:05:05,000 --> 00:05:09,000
Прво, лево поддрво на било кој јазол содржи само вредности кои се помалку од

101
00:05:09,000 --> 00:05:11,000
или еднаква на вредноста на јазол.

102
00:05:11,000 --> 00:05:15,000
Второ, право поддрво на еден јазол содржи само вредности кои се поголеми од

103
00:05:15,000 --> 00:05:17,000
или еднаква на вредноста на јазол.

104
00:05:17,000 --> 00:05:20,000
И, конечно, и лево и десно subtrees на сите јазли

105
00:05:20,000 --> 00:05:23,000
Исто така, бинарна пребарување дрвја.

106
00:05:23,000 --> 00:05:26,000
Ајде да погледнеме еден пример со истите бројки што се користи претходно.

107
00:05:26,000 --> 00:05:30,000
За оние од вас кои никогаш не сте виделе компјутерски науки дрвото пред,

108
00:05:30,000 --> 00:05:34,000
дозволете ми да започне со ти го кажувам дека компјутерски науки дрво расте надолу.

109
00:05:34,000 --> 00:05:36,000
Да, за разлика од дрвја сте навикнати да,

110
00:05:36,000 --> 00:05:38,000
коренот на компјутерски науки дрво е на врвот,

111
00:05:38,000 --> 00:05:41,000
а лисјата се на дното.

112
00:05:41,000 --> 00:05:45,000
Секоја мала кутија се нарекува јазол, и јазли се поврзани едни со други преку рабовите.

113
00:05:45,000 --> 00:05:48,000
Па коренот на ова дрво е еден јазол вредност со вредноста 13,

114
00:05:48,000 --> 00:05:52,000
која има 2 деца јазли со вредностите 5 и 34.

115
00:05:52,000 --> 00:05:57,000
А поддрво е дрво, која е формирана само со гледање во подточка на целиот дрво.

116
00:05:57,000 --> 00:06:03,000
>> На пример, лево поддрво на јазол 3 е дрво создадена од страна на јазли 0, 1, и 2.

117
00:06:03,000 --> 00:06:06,000
Значи, ако ние се вратиме на својствата на бинарни пребарување дрво,

118
00:06:06,000 --> 00:06:09,000
можеме да видиме дека секој јазол во стеблото во согласност со сите 3 својства, имено,

119
00:06:09,000 --> 00:06:15,000
левата поддрво содржи само вредности кои се помалку од или еднаква на вредноста на јазол;

120
00:06:15,000 --> 00:06:16,000
право поддрво на сите јазли

121
00:06:16,000 --> 00:06:19,000
содржи само вредности што се поголема или еднаква на вредноста на јазол и

122
00:06:19,000 --> 00:06:25,000
лево и десно subtrees на сите јазли, исто така, се бинарни пребарување дрвја.

123
00:06:25,000 --> 00:06:28,000
Иако ова дрво изгледа различно, ова е валидна бинарни пребарување дрво

124
00:06:28,000 --> 00:06:30,000
за истиот сет на броеви.

125
00:06:30,000 --> 00:06:32,000
Како што, впрочем, постојат многу можни начини на кои можете да креирате

126
00:06:32,000 --> 00:06:35,000
валидна бинарни пребарување дрво од овие броеви.

127
00:06:35,000 --> 00:06:38,000
Па, ајде да се вратиме на првиот ние направивме.

128
00:06:38,000 --> 00:06:40,000
Па што ние да правиме со овие дрвја?

129
00:06:40,000 --> 00:06:44,000
Па, ние многу едноставно може да се најдат на минималните и максималните вредности.

130
00:06:44,000 --> 00:06:46,000
Минималните вредности може да се најде секогаш ќе левата

131
00:06:46,000 --> 00:06:48,000
додека не се повеќе јазли да ја посетите.

132
00:06:48,000 --> 00:06:53,000
Спротивно на тоа, да се најде на максимум еден едноставно само оди надолу на правото во секое време.

133
00:06:54,000 --> 00:06:56,000
>> Наоѓање на било кој друг број кој не е на минимум или максимум

134
00:06:56,000 --> 00:06:58,000
е исто така лесно.

135
00:06:58,000 --> 00:07:00,000
Велат ние сме во потрага за бројот 89.

136
00:07:00,000 --> 00:07:03,000
Ние едноставно проверете на вредноста на секој јазол и да одат на лево или десно,

137
00:07:03,000 --> 00:07:06,000
зависност од тоа дали вредноста на јазол е помала или поголема од

138
00:07:06,000 --> 00:07:08,000
оној што го барате.

139
00:07:08,000 --> 00:07:11,000
Значи, со почеток во коренот на 13, гледаме дека 89 е поголема,

140
00:07:11,000 --> 00:07:13,000
и така одиме право.

141
00:07:13,000 --> 00:07:16,000
Тогаш можеме да видиме на јазол за 34, и повторно одиме право.

142
00:07:16,000 --> 00:07:20,000
89 е уште поголема од 55, па продолжи да оди кон десно.

143
00:07:20,000 --> 00:07:24,000
Ние тогаш се излезе со еден јазол со вредност од 144 и оди кон лево.

144
00:07:24,000 --> 00:07:26,000
Еве и овде, 89 е во право таму.

145
00:07:26,000 --> 00:07:31,000
>> Друга работа што можеме да направиме е печатење на сите броеви од вршење на inorder traversal.

146
00:07:31,000 --> 00:07:35,000
На inorder traversal значи да се печати се надвор во левата поддрво

147
00:07:35,000 --> 00:07:37,000
проследено со печатење на јазол себе

148
00:07:37,000 --> 00:07:40,000
а потоа следеа од страна на печатење се во право поддрво.

149
00:07:40,000 --> 00:07:43,000
На пример, да го земеме нашиот омилен бинарни пребарување дрво

150
00:07:43,000 --> 00:07:46,000
и печатење на броеви во подредени цел.

151
00:07:46,000 --> 00:07:49,000
Започнуваме во коренот на 13, но пред печатење 13 мораме да испечатите

152
00:07:49,000 --> 00:07:51,000
сè во левата поддрво.

153
00:07:51,000 --> 00:07:55,000
Значи одиме до 5. Ние сè уште треба да се оди подлабоко во дрво се додека не се најде на левата повеќето јазол,

154
00:07:55,000 --> 00:07:57,000
која е нула.

155
00:07:57,000 --> 00:08:00,000
По печатење нула, ние одиме назад до 1 и печатење на тоа.

156
00:08:00,000 --> 00:08:03,000
Потоа одиме на правото поддрво, што е 2, и печатење на тоа.

157
00:08:03,000 --> 00:08:05,000
Сега дека ние сме направиле со тоа поддрво,

158
00:08:05,000 --> 00:08:07,000
можеме да одиме назад до 3 и печати ја надвор.

159
00:08:07,000 --> 00:08:11,000
Продолжувајќи се врати, ние печати 5, а потоа на 8.

160
00:08:11,000 --> 00:08:13,000
Сега кога имаме заврши целиот лево поддрво,

161
00:08:13,000 --> 00:08:17,000
ние може да испечатите на 13 и да почне да работи на десната поддрво.

162
00:08:17,000 --> 00:08:21,000
Ние хоп до 34, но пред печатење 34 мораме да испечатите неговата лева поддрво.

163
00:08:21,000 --> 00:08:27,000
Значи ние печати од 21, а потоа ние да се печати од 34 и посета своето право поддрво.

164
00:08:27,000 --> 00:08:31,000
Од 55 нема лево поддрво, ние го испечатите и продолжи да своето право поддрво.

165
00:08:31,000 --> 00:08:36,000
144 има лево поддрво, и така ние се печати од 89, проследено со 144,

166
00:08:36,000 --> 00:08:39,000
и конечно на десната повеќето јазол од 233.

167
00:08:39,000 --> 00:08:44,000
Таму ќе ја имаат, сите броеви се испечатени со цел од најниските до највисоките.

168
00:08:44,000 --> 00:08:47,000
>> Додавајќи нешто на дрвото е релативно безболно, како и.

169
00:08:47,000 --> 00:08:51,000
Сите ние треба да направите е да бидете сигурни дека ние ја следиме 3 бинарни пребарување дрво својства

170
00:08:51,000 --> 00:08:53,000
и потоа вметнете вредноста каде што постои простор.

171
00:08:53,000 --> 00:08:55,000
Да речеме дека сакаме да вметнете вредноста на 7.

172
00:08:55,000 --> 00:08:58,000
Од 7 е помалку од 13, ние одиме кон лево.

173
00:08:58,000 --> 00:09:01,000
Но, тоа е поголем од 5, па ние напречни десно.

174
00:09:01,000 --> 00:09:04,000
Бидејќи тоа е помалку од 8 и 8 е лист јазол, ние го додадете 7 до левата дете на 8.

175
00:09:04,000 --> 00:09:09,000
Voila! Додадовме голем број на нашите бинарни пребарување дрво.

176
00:09:09,000 --> 00:09:12,000
>> Ако можеме да додадете нешта, подобро да биде во можност да ги избришете работите како добро.

177
00:09:12,000 --> 00:09:14,000
За жал за нас, бришење е малку повеќе комплицирано -

178
00:09:14,000 --> 00:09:16,000
не многу, но само малку.

179
00:09:16,000 --> 00:09:18,000
Постојат 3 различни сценарија дека ние треба да се разгледа

180
00:09:18,000 --> 00:09:21,000
кога бришење елементи од бинарниот пребарување дрвја.

181
00:09:21,000 --> 00:09:24,000
Прво, најлесниот случај е тоа што елементот е лист јазол.

182
00:09:24,000 --> 00:09:27,000
Во овој случај, ние едноставно го избришете и да продолжи со нашиот бизнис.

183
00:09:27,000 --> 00:09:30,000
Велат дека сакаме да го избришете 7 дека ние само додаде.

184
00:09:30,000 --> 00:09:34,000
Па, ние едноставно го најдете, отстранете ја, и тоа е тоа.

185
00:09:35,000 --> 00:09:37,000
Следниот случај е ако јазол има само 1 дете.

186
00:09:37,000 --> 00:09:40,000
Тука можеме да ја избришете јазол, но ние прво мора да бидете сигурни

187
00:09:40,000 --> 00:09:42,000
за да се поврзете на поддрво дека сега е оставена без родители

188
00:09:42,000 --> 00:09:44,000
на родител на јазол ние едноставно избришани.

189
00:09:44,000 --> 00:09:47,000
Велат дека сакаме да го избришете 3 од нашите дрво.

190
00:09:47,000 --> 00:09:50,000
Земаме дете елемент на тој јазол и прикачете го на родител на јазол.

191
00:09:50,000 --> 00:09:54,000
Во овој случај, ние сме сега со приложување на 1 до 5.

192
00:09:54,000 --> 00:09:57,000
Оваа работи без проблем, затоа што знаеме, според бинарни пребарување дрво сопственост,

193
00:09:57,000 --> 00:10:01,000
дека сè во левата поддрво од 3 беше помалку од 5.

194
00:10:01,000 --> 00:10:05,000
Сега дека 3 е поддрво е згрижени, ние може да го избришете.

195
00:10:05,000 --> 00:10:08,000
Третата и последна случај е најсложен.

196
00:10:08,000 --> 00:10:11,000
Ова е случај кога јазол сакаме да ја избришете има 2 деца.

197
00:10:11,000 --> 00:10:15,000
Со цел да го направите ова, ние прво треба да се најде на јазол кој има следниот најголем вредност,

198
00:10:15,000 --> 00:10:18,000
трампа на две, а потоа избришете јазол во прашање.

199
00:10:18,000 --> 00:10:22,000
Обрнете внимание на јазол кој има следниот најголемата вредност не може да има 2 деца се

200
00:10:22,000 --> 00:10:26,000
од неговата лева дете ќе биде подобар кандидат за следниот најголем.

201
00:10:26,000 --> 00:10:30,000
Затоа, бришење на јазол со 2 деца изнесува Замена на 2 јазли,

202
00:10:30,000 --> 00:10:33,000
а потоа бришење е постапува од страна 1 од 2 наведените правила.

203
00:10:33,000 --> 00:10:37,000
На пример, да речеме ние сакаме да го избришете root јазол, 13.

204
00:10:37,000 --> 00:10:39,000
Првото нешто што го правиме е ние се најдат на следниот најголемата вредност во дрво

205
00:10:39,000 --> 00:10:41,000
кои, во овој случај, е 21.

206
00:10:41,000 --> 00:10:46,000
Ние тогаш трампа на 2 јазли, правејќи 13 лист и 21 на централната група јазол.

207
00:10:46,000 --> 00:10:49,000
Сега ние едноставно може да избришете 13.

208
00:10:50,000 --> 00:10:53,000
>> Како се алудира погоре, постојат многу можни начини да се направи валидна бинарни пребарување дрво.

209
00:10:53,000 --> 00:10:56,000
За жал за нас, некои се полоши од другите.

210
00:10:56,000 --> 00:10:59,000
На пример, она што се случува кога ќе се изгради бинарни пребарување дрво

211
00:10:59,000 --> 00:11:01,000
од Подредена листа на броеви?

212
00:11:01,000 --> 00:11:04,000
Сите броеви се само додава на правото на секој чекор.

213
00:11:04,000 --> 00:11:06,000
Кога ќе сакате да пребарувате на број,

214
00:11:06,000 --> 00:11:08,000
ние немаме друг избор освен само да се погледне на правото на секој чекор.

215
00:11:08,000 --> 00:11:11,000
Ова не е подобар од линеарно пребарување на сите.

216
00:11:11,000 --> 00:11:13,000
Иако ние не ќе ги покрие тука, постојат и други, посложени,

217
00:11:13,000 --> 00:11:16,000
структури на податоци кои бидете сигурни дека тоа не се случи.

218
00:11:16,000 --> 00:11:18,000
Сепак, една едноставна работа што може да се направи за да се избегне ова е

219
00:11:18,000 --> 00:11:21,000
само случајно shuffle на влезни вредности.

220
00:11:21,000 --> 00:11:26,000
Тоа е многу веројатно дека по случаен случајно мешаат листа на броеви се подредени.

221
00:11:26,000 --> 00:11:29,000
Ако ова е случај, казина не ќе остане во бизнисот за долго.

222
00:11:29,000 --> 00:11:31,000
>> Таму ќе ја имаат.

223
00:11:31,000 --> 00:11:34,000
Вие сега знаете за бинарни пребарување и бинарни пребарување дрвја.

224
00:11:34,000 --> 00:11:36,000
Јас сум Патрик Шмид, и ова е CS50.

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

226
00:11:38,000 --> 00:11:43,000
Еден очигледен начин ќе биде да го скенира листата од ... [ѕвонче]

227
00:11:43,000 --> 00:11:46,000
... На бројот на предмети ... Да

228
00:11:46,000 --> 00:11:50,000
[Се смее]

229
00:11:50,000 --> 00:11:55,000
... Испраќате јазол од 234 ... augh.

230
00:11:55,000 --> 00:11:58,000
>> Yay! Тоа беше -