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
Сейчас вы читаете Тарзан, стежка, Белоснежка, и так далее.

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
вы бы поняли, что M Микки приходит после 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 с помощью двоичного поиска, мы можем найти его только в 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
некоторые псевдокод рекурсивную функцию, которая реализует бинарный поиск.

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

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
И, наконец, как левое и правое поддеревья всех узлов

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
левого и правого поддеревьев всех узлов и деревья бинарного поиска.

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
>> Другое дело, что мы можем сделать, это распечатать все числа, выполняя симметричного обхода.

146
00:07:31,000 --> 00:07:35,000
Симметричного обхода означает печатать все, что в левом поддереве

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
Например, предположим, что мы хотим, чтобы удалить корневой узел, 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
просто случайно перемешать входных значений.

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
>> Ура! Это было -