Деревья

Деревья являются одним из способов организации данных, который

позволяет с высокой эффективностью осуществлять обработку таблицы

имен. Элемент дерева содержит элемент таблицы и указатели на несколько

потомков. Рассмотрим вариант организации таблицы в виде двоичного дере-

ва, в котором каждый элемент может иметь не более двух потомков (рис.

1.8).

Корень

Элемент

Элемент

Левый Правый

Элемент

Левый

Правый

Левый

Правый

Рис_. 1.8. Организация деревьев

Существуют различные классы двоичных деревьев, различающихся

алгоритмами поиска, включения и удаления. Остановимся на обычном дво-

ичном дереве.

Обычное двоичное дерево - это упорядоченная структура, в левом

поддереве которого хранятся элементы, меньшие того, который хранится в

корне, а в правом - большие.

Поиск осуществляется путем сравнения искомого элемента с элемен-

том дерева и продвижением далее по правому или левому поддереву в за-

висимости от результата сравнения. Оптимальная организация алгоритма в

этом случае - рекурсивная. Элемент не найден, если поиск заканчивается на

элементе дерева, не имеющем потомков (такой элемент называется лист).

Включение. Если элемент не найден, т.е. поиск прекращен при дос-

тижении элемента дерева, не имеющего соответствующего потомка, то

элемент включается на свободное место.

Удаление. Если элемент не содержит потомков, то он удаляется без ка-

ких-либо затруднений. Если у элемента один потомок, то этот потомок за-

мещает удаляемый элемент. Если элемент содержит оба потомка, то уда-

ляемый элемент заменяется на самый правый лист левого поддерева или на

самый левый лист правого поддерева, т.е. достигаемый при движении по са-

мой правой или самой левой ветви дерева.

Пример.

Заданная последовательность включений:

3 6 2 4 5 1 7

Полученное дерево:

Л П

Л П

Л П

Л П

Л П

Л П

Л П

Удаление элемента со значением 6.

1. С заменой на самый правый элемент левого поддерева:

Л П

Л П

Л П

Л П

Л П

Л П

2. С заменой на самый левый элемент правого поддерева:

Л П

Л П

Л П

Л П

Л П

Л П

Преимущества. Гибкость способа организации таблицы и простота

алгоритмов обработки.

Недостатки. Частые операции с динамической памятью для выделе-

ния и освобождения элементов списка. Возможность вырождения дерева.

Возможно моделирование дерева через одномерный массив, которое

осуществляется так же, как и для последовательных списков, но с двумя

индексами для левого и правого поддерева.