[Powered by Google Translate] [Двоичный поиск] [Патрик Шмид - Гарвардский университет] [Это CS50. - CS50.TV] 

Если бы я дал вам список имен Диснея характера в алфавитном порядке и спросил, можно найти Микки Мауса, как бы вы об этом? Один из очевидных путей было бы просмотреть список с самого начала и проверьте каждое имя, чтобы увидеть, если это Микки. Но, как вы читаете Aladdin, Алиса, Ариэль, и так далее, Вы быстро поймете, что, начиная с передней части списка не было хорошей идеей. Ладно, может быть, вы должны начать работать в обратном направлении от конца списка. Сейчас вы читаете Тарзан, стежка, Белоснежка, и так далее. Тем не менее, это не кажется, что лучший способ это сделать. 

Ну, еще один способ, что вы могли бы идти об этом, чтобы попытаться сузить список имен, которые у вас есть на что посмотреть. Поскольку вы знаете, что они расположены в алфавитном порядке, Вы просто посмотрите на имена в середине списка и проверить, если Микки Мауса до или после этого имени. Глядя на фамилию во втором столбце вы бы поняли, что M Микки приходит после J для Жасмин, так что вам просто игнорировать первой половине списка. Тогда вы, наверное, посмотрите на верхнюю часть последнего столбца и вижу, что она начинается с Рапунцель. Микки доходит до Рапунцель, похоже, что мы можем игнорировать последней колонке, а также. Продолжая стратегию поиска, вы быстро поймете, что Микки В первой половине оставшегося списка имен и, наконец, найти Микки прячется между Мерлином и Минни. 

То, что вы только что сделали был в основном бинарного поиска. Как это следует из названия, она выполняет свою стратегию поиска в бинарном вопрос. Что это значит? Ну, дали список отсортированных элементов, алгоритм бинарного поиска делает двоичных решений - влево или вправо, больше или меньше, в алфавитном порядке, до или после - в каждой точке. Теперь у нас есть имя, которое идет вместе с этим алгоритм поиска, Давайте посмотрим на другой пример, но на этот раз со списком отсортированы номера. Скажем, мы ищем число 144 в этом списке отсортированы номера. Как и раньше, мы находим число, которое находится в середине - который в данном случае составляет 13 - и посмотреть, если 144 больше или меньше, чем 13. Так как это явно больше, чем 13, мы можем игнорировать все, что составляет 13 или менее и просто сосредоточиться на оставшуюся половину. Так как у нас теперь есть четное число предметы, оставленные, Мы просто выбрать число, которое ближе к середине. В этом случае мы выбираем 55. Мы могли бы так же легко выбраны 89. Хорошо. Опять же, 144 больше, чем 55, так что мы идем направо. К счастью для нас, следующее число является средним 144, тот, который мы ищем. Так что для того, чтобы найти 144 с помощью двоичного поиска, мы можем найти его только в 3 этапа. Если бы мы использовали линейный поиск здесь, это заняло бы нам 12 шагов. В самом деле, так как этот метод поиска половинки количество элементов он должен смотреть на на каждом шагу, он найдет элемент, он ищет примерно в журнал число элементов в списке. Теперь, когда мы видели 2 примера, давайте взглянем на некоторые псевдокод рекурсивную функцию, которая реализует бинарный поиск. Начиная с верхнего, мы видим, что мы должны найти функцию, которая принимает 4 аргумента: ключ, массив, мин, макс. Ключ это число, которое мы ищем, поэтому 144 в предыдущем примере. Массив представляет собой список чисел, которые мы ищем. Минимальная и максимальная являются показатели минимальной и максимальной позиции что мы сейчас смотрим. Поэтому, когда мы начнем, мин будет равна нулю и Макс будет максимальным индексом массива. Как сузить поиск вниз, мы будем обновлять минимальное и максимальное быть только диапазон, который мы все еще ищем дюйма 

Давайте переходить к интересной части первой. Первое, что нам сделать, это найти середину, индекс, который находится на полпути между минимальной и максимальной массива, что мы по-прежнему рассматриваем. Тогда мы посмотрим на значение массива в то середина расположения и посмотреть, если число, которое мы ищем меньше, чем ключ. Если число в этой позиции меньше, то это означает, что ключ больше, чем все номера слева от этой позиции. Таким образом, мы можем назвать бинарной функции поиска снова, но на этот раз обновлению минимальных и максимальных параметров прочитать только половину , что больше или равна значению мы только что рассмотрели. С другой стороны, если ключ меньше, чем число в текущем середине массива, Мы хотим, чтобы пойти налево и игнорировать все числа, которые больше. Опять же, мы называем бинарный поиск, но на этот раз с диапазон минимальных и максимальных обновление , чтобы включить только нижнюю половину. Если значение на нынешнем середине массива не является ни больше, ни меньше, чем ключ, то она должна быть равна ключ. Таким образом, мы можем просто вернуть текущий индекс середину, и мы сделали. Наконец, эта проверка здесь для случая, когда число на самом деле не в массив чисел мы ищем. Если максимальный индекс диапазона, который мы ищем это все меньше минимума, это означает, что мы зашли слишком далеко. Поскольку число не было во входном массиве, мы возвращают -1 чтобы показать, что ничего не было найдено. 

Вы, возможно, заметили, что для этого алгоритма на работу, Список номеров должен быть отсортирован. Другими словами, мы можем найти только 144 с помощью бинарного поиска если все числа упорядочены от низшего к высшему. Если бы это было не так, мы не смогли бы исключить половину номеров на каждом шагу. Поэтому у нас есть 2 варианта. Либо мы можем взять несортированный список и отсортировать его перед использованием бинарного поиска, или мы можем убедиться, что список чисел сортируются по мере добавления номера к ней. Таким образом, вместо сортировки только тогда, когда мы должны искать, почему бы не сохранить список, отсортированный во все времена? 

Один из способов сохранить список номеров отсортированы одновременно позволяя , чтобы добавить или переместить номера из этого списка является использование так называемых бинарных деревьев поиска. Дерево двоичного поиска является структурой данных, которая имеет 3 свойства. Во-первых, левого поддерева любого узла содержит только значения, которые меньше или равное значение узла. Во-вторых, правое поддерево узла содержит только значения, которые больше или равное значение узла. И, наконец, как левое и правое поддеревья всех узлов Также бинарные деревья поиска. Давайте посмотрим на пример с теми же номерами мы использовали ранее. Для тех из вас, кто никогда не видел дерево информатики и раньше, Позвольте мне начать с рассказа о том, что дерево компьютерные науки растет вниз. Да, в отличие от деревьев вы привыкли, корень дерева, компьютерные науки находится на вершине, и листья в нижней части. Каждая коробочка называется узлом, а узлы соединены друг с другом по краям. Так что корень этого дерева является узлом значение с значением 13, который имеет 2 детей узлов со значениями 5 и 34. Поддерево дерева, который образуется, просто взглянув на подраздел всего дерева. 

Например, левое поддерево узла 3 является деревом созданы узлы 0, 1, и 2. Таким образом, если мы вернемся к свойствам бинарное дерево поиска, мы видим, что каждому узлу в дереве соответствует всем 3 свойства, а именно: левое поддерево содержит только значения, которые меньше или равно значению узла; правое поддерево всех узлов содержит только значения, которые больше или равно значению узла, а левого и правого поддеревьев всех узлов и деревья бинарного поиска. Хотя это дерево выглядит по-другому, это действительно бинарное дерево поиска за тот же набор чисел. В самом деле, существует множество возможных способов, которые вы можете создать действительный бинарное дерево поиска с этих номеров. Ну, давайте вернемся к первому мы создали. Так что мы можем сделать с этими деревьями? Ну, мы можем очень просто найти минимальное и максимальное значения. Минимальные значения можно найти всегда будет левый пока больше нет узлов для посещения. И наоборот, чтобы найти максимальный просто просто спускается к правой в каждый момент времени. 

Поиск любой другой номер, который не является минимальным или максимальным Столь же легко. Сказать, что мы ищем число 89. Мы просто проверяем значение каждого узла и пойти налево или направо, в зависимости от того, значение узла меньше или больше, чем тот, который мы ищем. Таким образом, начиная с корня из 13, мы видим, что 89 больше, и поэтому мы идем направо. Тогда мы видим, узел 34, и мы снова идем направо. 89 является еще большей, чем 55, так что мы продолжаем идти с правой стороны. Мы тогда придумали узел со значением 144 и идем налево. И вот, 89 тут же. 

Другое дело, что мы можем сделать, это распечатать все числа, выполняя симметричного обхода. Симметричного обхода означает печатать все, что в левом поддереве с последующей печатью самого узла , а затем с последующей печатью все в правом поддереве. Например, давайте возьмем наш любимый бинарное дерево поиска и распечатать числа в отсортированном порядке. Мы начинаем в корне 13, но перед печатью 13 имеем распечатать все в левом поддереве. Таким образом, мы идем к 5. Мы должны еще глубже вниз по дереву, пока не найдем самый левый узел, которая равна нулю. После печати нулю, мы возвращаемся к 1 и напечатать это. Тогда мы идем к правое поддерево, что на 2, и печатать это. Теперь, когда мы закончили с этого поддерева, мы можем вернуться до 3 и распечатать его. Продолжая обратно, мы выводим 5, а затем 8. Теперь, когда мы завершили все левое поддерево, мы можем напечатать из 13-и начать работать на правое поддерево. Мы хопа до 34, но перед печатью 34, мы должны распечатать его левого поддерева. Таким образом, мы распечатать 21, то мы получим распечатать 34, и посетить его правого поддерева. С 55 не имеет левого поддерева, мы распечатать его и переходите к своим правом поддереве. 144 имеет левое поддерево, и поэтому мы распечатать 89, затем 144, и, наконец, самого правого узла 233. Там вы имеете его, все номера печатаются в порядке от низшего к высшему. 

Добавление что-то в дерево является относительно безболезненно, а также. Все, что нам нужно сделать, это убедиться, что мы следуем 3 двоичных свойства дерева поиска , а затем вставить значение, где есть пространство. Допустим, мы хотим, чтобы вставить значение 7. С 7 меньше, чем 13, мы идем налево. Но это больше 5, так что мы движемся вправо. Поскольку это менее 8 и 8 листовым узлом, мы добавляем 7 до левого ребенка 8. Voila! Мы добавили ряд наших бинарное дерево поиска. 

Если мы можем добавить вещи, мы лучше иметь возможность удалить вещи. К сожалению для нас, удаления немного сложнее - Не много, но только немного. Есть 3 различных сценариев, которые мы должны рассмотреть При удалении элемента из двоичного дерева поиска. Первый, самый простой случай, что элемент является конечным узлом. В этом случае, мы просто удалить его и вернемся к нашему бизнесу. Скажем, мы хотим, чтобы удалить 7, которые мы только что добавили. Ну, мы просто найти его, удалить его, вот и все. Следующий случай, если узел имеет только 1 ребенок. Здесь мы можем удалить узел, но сначала мы должны убедиться, что Для подключения поддерево, что в настоящее время оставила без родителей на родительский узел, который мы только что удалили. Скажем, мы хотим удалить 3 из нашего дерева. Мы дочерний элемент этого узла и прикрепить его к родителю узла. В этом случае, мы сейчас крепления от 1 до 5. Это работает без проблем, потому что мы знаем, в соответствии с деревом собственности бинарный поиск, что все в левом поддереве 3 была меньше 5. Теперь, когда 3 в поддереве заботятся, мы можем удалить его. Третий и последний случай является самым сложным. Это тот случай, когда узел мы хотим удалить имеет 2 детей. Для того, чтобы сделать это, мы должны сначала найти узел, который имеет наибольшее значение, поменять местами два, а затем удалить узел в вопросе. Обратите внимание на узел, который имеет наибольшее значение не может иметь 2 детей сама С его левого ребенок будет лучшим кандидатом для следующей большой. Таким образом, удаление узла с 2 детьми сводится к перекачке 2 узлов, а затем удалить обрабатывается 1 из 2 вышеупомянутого правила. Например, предположим, что мы хотим, чтобы удалить корневой узел, 13. Первое, что мы делаем, мы находим наибольшее значение в дерево который, в данном случае, 21. Затем поменяйте местами 2 узлов, решений 13 листьев и 21 центрального узла группы. Теперь мы можем просто удалить 13. 

Как упоминалось ранее, существует множество возможных способов сделать действительно бинарное дерево поиска. К сожалению для нас, некоторые из них хуже, чем другие. Например, что произойдет, когда мы строим бинарное дерево поиска от отсортированный список чисел? Все номера просто добавил к праву на каждом шагу. Когда мы хотим найти номер, у нас нет выбора, но только чтобы посмотреть на праве на каждом шагу. Это не лучше, чем линейный поиск на всех. Хотя мы не будем рассматривать их здесь, есть и другие, более сложные, структуры данных, чтобы убедиться, что этого не произойдет. Тем не менее, одну простую вещь, что можно сделать, чтобы избежать этого, просто случайно перемешать входных значений. Маловероятно, что по случайности перетасовал список чисел сортируется. Если бы это было так, казино не будет оставаться в бизнесе надолго. 

Там у Вас есть это. Теперь вы знаете о бинарных деревьев поиска и бинарный поиск. Я Патрик Шмид, и это CS50. [CS50.TV] Один из очевидных способов будет сканировать список из ... [сигнал] ... Количество элементов ... да [Смеется] ... Опубликовать узла 234 ... augh. >> Ура! Это было -