Базовые структуры данных. Деревья, страница 3

2.2  Поиск в двоичном дереве

Процедура поиска в дереве проста и обычно эффективна. Рассмотрим ее рекурсивный вариант. Начинается поиск с корня дерева. Если заданный ключ равен ключу дерева, то поиск завершается. Если заданный ключ меньше текущего, продолжаем поиск в левом поддереве (согласно свойству упорядоченности, заданный ключ может быть только там), если больше – в правом. При этом максимально время (длина пути поиска) равна O(h), где h – высота дерева.

2.3  Максимальный и минимальный элементы

Минимальный элемент дерева можно найти, пройдя по левым веткам начиная от корня и до листа. И правда, правее корня лежат вершины, ключи которых больше ключа корня по определению, поэтому рассматриваем ключи левого поддерева. В нем абсолютно аналогичная ситуация. Соответственно максимальный элемент можно найти, спустившись по правым веткам от корня. Оба этих алгоритма требуют времени порядка O(h), где h – высота дерева.

2.4  Следующий и предыдущий элементы

Алгоритм поиска следующего элемента дерева предельно прост. Если правое поддерево заданной вершины x не пусто, следующим элементом будет минимальный элемент правого поддерева. Иначе мы начинаем двигаться вверх по дереву от вершины x до корня, пока не встретим вершину, которая является левым ребенком своего родителя. Этот родитель и будет следующим элементом.

2.5  Добавление элемента

Добавление элемента аналогично поиску. Мы спускаемся от корня к листьям, выбирая направление из расчета новая вершина больше или меньше текущей. Как только встречаем вершину, необходимый путь из которой ведет в «пустоту», вставляем новую вершину в этом направлении. При этом необходимо обработать случай, когда дерево пустое.

2.6  Удаление элемента

При удалении элемента могут возникнуть следующие ситуации:

·  удаляемая вершина не имеет детей. Тогда мы просто удаляем ее из дерева;

·  удаляемая вершина имеет ровно одного ребенка. Тогда следует поставить ребенка на место удаляемой вершины;

·  удаляемая вершина имеет двух детей. В этом случае мы сводим задачу к предыдущему случаю. Заменим ключ удаляемой вершины значением ключа непосредственно следующей за ней (см. 2.4) и удалим следующую вершину.

3  Представление корневых деревьев

Как же хранить деревья, чтобы обеспечить максимальную скорость и удобство использования? Рассмотрим сначала двоичные деревья, а затем расширим их использование до деревьев с произвольным ветвлением.

Каждая вершина дерева будет записью с несколькими полями. Одним из них является ключ, а остальные предназначены для хранения дополнительных данных и указателей на другие вершины.

Следует особо отметить использование массивов для хранения деревьев. Вместо полей каждой вершины мы можем завести несколько массивов (например, key для ключей, left для указателей левых детей и т. д.) Тогда указателем на вершину будет являться просто целочисленный индекс в массиве. При этом чтобы получить ключ, используем key[x], чтобы получить индекс левого ребенка, записываем left[x].

3.1  Двоичные деревья

Для представления вершины x двоичного дерева T используются поля p, left и right, в которых хранятся указатели соответственно на родителя, левого ребенка и правого ребенка. Если p = 0, то x – корень; если left или right равны 0, то у вершины x нет левого либо правого ребенка соответственно. Кроме того, со всем деревом связано поле root, указывающее на корневую вершину; при root = 0 дерево пусто.