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

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

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

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

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

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

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

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

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

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

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

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

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