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
Но докато четете Aladdin, Алис, Ариел, и така нататък,

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
Сега сте прочели Тарзан, Stitch, Снежанка и т.н..

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
и да видим, че тя започва с Рапунцел.

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

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 с помощта на двоично търсене, ние сме в състояние да го намерите само в три стъпки.

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
Сега, когато съм виждал два примери, нека да разгледаме

53
00:02:37,000 --> 00:02:41,000
някои pseudocode за рекурсивна функция, която изпълнява двоично търсене.

54
00:02:41,000 --> 00:02:44,000
Започвайки от горната част, виждаме, че ние трябва да се намери функция, която приема четири аргументи:

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
Array е от списъка с номера, че ние търсим.

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
индекс, който е по средата между мин. и макс на масива, че ние сме все още обмисля.

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
Така че имаме две възможности.

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
Двоично търсене дърво е структура от данни, която има три свойства.

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
И накрая, както лявото и дясното поддървета на всички възли

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
, която има две деца възли с ценностите, 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
виждаме, че всеки възел в дървото отговаря на всички три имота, а именно,

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
левите, и десните поддървета на всички възли също са дървета за двоично търсене.

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 прекосява.

146
00:07:31,000 --> 00:07:35,000
Един Inorder прекосява означава да отпечатате всичко в лявото поддърво

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
Тогава отиваме право поддърво, което е два и отпечатвате, че от.

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
Всичко, което трябва да направим, е да сме сигурни, че следват три двоични Търсене на имоти дървета

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
Има три различни сценарии, които ние трябва да се помисли

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
Да кажем, че искате да изтриете три от нашето дърво.

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
че всичко в лявото поддърво на три по-малко от 5.

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

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

196
00:10:08,000 --> 00:10:11,000
Това е случаят, когато възел искаме да изтриете има две деца.

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
Обърнете внимание на възел, който е следващата по големина стойност не може да има две деца

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

201
00:10:26,000 --> 00:10:30,000
Ето защо, изтриване възел с две деца възлиза на размяна на два възли,

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

203
00:10:33,000 --> 00:10:37,000
Например, нека кажем, че искате да изтриете коренът, 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
След това разменете две възли, което прави 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
просто случайно разбъркване на входните стойности.

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
Един очевиден начин е да се сканира списък от ... [BEEP]

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
>> Ура! Това беше -