Алгоритм бинарного поиска

Известно, что бинарный поиск эффективен, потому что он делит последовательности, в которых производится поиск, на две половины на каждой итерации. То есть большая часть информации даже не проверяется, так как в этом нет необходимости. Единственный недостаток – данные должны быть отсортированы [3].

Такова идея, скрытая за деревом. Такая структура называется деревом из-за ветвей, как у настоящего дерева. Возможно, эту структуру стоило бы назвать корнем бинарного поиска, т.к. это было бы проще увязать с иллюстрацией, походящей скорее на корневую систему, но, к сожалению, в информатике уже укоренилось название «дерево», так что переименование наверно было бы плохой мыслью.

Рисунок 1.1 – Пример бинарного дерева из 10 элементов

Если начать поиск элемента с самого верхнего узла, называемого корнем, можно продолжать поиск заданного элемента, сравнивая его с вершиной на предмет того, меньше ли искомое значение, чем то, что содержится в вершине или же больше. Скажем, нужно найти элемент со значением 3. 3 меньше 5, поэтому двигаться нужно влево и текущей вершиной становится вершина со значением 2. 3 больше 2, поэтому идет смещение вправо и теперь вершиной становится узел 4, идет смещение влево от вершины и вот тот самый элемент 3. 3 равно 3, поиск удался. Следуя этому образцу, вы можете найти любой элемент в дереве.

В случае, если искомого элемента нет, необходимо проделать поиск, как описано выше и, если в результате алгоритм зайдет за нижнюю часть дерева, то поиск можно считать безуспешным. Для того, чтобы зафиксировать выход за нижнюю часть дерева в нем есть специальные узлы, называемые листьями (листовые узлы). Они не содержат данных и, если алгоритм достигает такого листа, значит поиск зашёл в тупик. Для обозначения листьев используются символы тильды ~, а дерево показано на рисунке 1.2.

Рисунок 1.2 – Пример бинарного дерева

Из диаграммы легко увидеть, что при достижении листа поиск заканчивается. Вершина дерева называется корнем. Однако, учитывая то, что деревья могут определяться рекурсивно, каждый узел дерева может быть назван корнем (корень поддерева). Если узел является корнем поддерева, у него есть родительский узел, который ссылается на него. Так узел 2 является родительским узлом (родителем) узла 1, а 5 – родительский узел узла 2. Если смотреть с другой стороны, 2 является дочерним узлом узла 5, а 1 – дочерний узел (потомок) узла 2. В отношении деревьев принята аналогия с семейным древом.

Алгоритм вставки узлов

Вставка в дерево нового узла проста и эффективна, если посмотреть на это с точки зрения безуспешного поиска. Если искать новый элемент, который, отсутствует в дереве, его можно заменить на новый узел с тем значением, которое безуспешно искалось. С помощью сравнений «меньше» или «больше» можно обрабатывать и дубликаты данных. Оба способа работают и дубликаты будут выстраиваться в линию вниз по пути.

Многие вещи, которые хотелось бы сделать с помощью деревьев, вовлекают операцию поиска. Поэтому деревья столь эффективны. В идеале, поиск будет делить диапазон поиска надвое на каждой последующей итерации. Было бы неплохо использовать это обстоятельство и при реализации других операций. Например, вставка нового узла – это вариация алгоритма поиска с безуспешным результатом [4]. Программа ищет значение, которого нет в дереве, достигает листа и заменяете первый лист на новый узел с нужным значением рисунки 1.3 – 1.4.

Рисунок 1.3 – Поиск элемента со значением

Рисунок 1.4 – Вставка нового узла, в связи с отсутствием искомого

Алгоритм удаления узлов

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

Всё, что нужно сделать для удаления внешнего узла – заменить его на его нелистового потомка или на лист, если у данного узла нет иных потомков, кроме листовых узлов. Есть три простых случая удаления внешнего узла. Если у жертвы есть левый дочерний узел, его заменяют на удаляемый узел, который является внешним, левым потомком, потому как его правый потомок с уверенностью окажется листом. Если у удаляемого узла есть правый дочерний узел, то случай симметричен узлу с левым потомком. Если у узла нет дочерних узлов – можно выбрать любой, т.к. они оба будут листьями. И не забыть обновить ссылку родительского узла, чтобы она указывала на новый дочерний узел. Пример на рисунке 1.5.

Рисунок 1.5 – Удаление узлов с одним потомком

В случае, если у удаляемого узла существует 2 потомка, простейшим методом удаления узла 5 на рисунке 1.5 из дерева на рисунке 1.6 будет являться замена 5 на 4 или 7. Данные узлы являются порядковым предшественником и преемником, соответственно. Вся работа сводится к тому, чтобы найти один из этих узлов, потому что всё, что в большинстве деревьев нужно сделать после – скопировать данные одного узла в другой, затем удалить порядкового предшественника или преемника, которым был заменен удаляемый узел. Можно использовать как преемника, так и предшественника, и разницы особой нет.

Рисунок 1.6 – Удаление узла 5

Рисунок 1.7 – Исходное дерево

Из всего этого следует, что удаление узлов, так же, как и вставка узлов, далеко на самая сложная задача.

Не нашли, что искали? Воспользуйтесь поиском по сайту: