Алгоритмы и структуры данных
3.3. Реализация деревьев
В этом разделе мы представим несколько основных реализаций деревьев и обсудим их возможности для поддержки операторов, введенных в разделе 3.2.
Представление деревьев с помощью массивов
Пусть Т — дерево с узлами 1, 2, . п. Возможно, самым простым представлением дерева Т, поддерживающим оператор PARENT (Родитель), будет линейный массив А, где каждый элемент A[i] является указателем или курсором на родителя узла і. Корень дерева Т отличается от других узлов тем, что имеет нулевой указатель или указатель на самого себя как на родителя. В языке Pascal указатели на элементы массива недопустимы, поэтому мы будем использовать схему с курсорами, тогда A[i] = j, если узел j является родителем узла і, и А[i] = 0, если узел і является корнем.
Данное представление использует то свойство деревьев, что каждый узел, отличный от корня, имеет только одного родителя. Используя это представление, родителя любого узла можно найти за фиксированное время. Прохождение по любому пути, т.е. переход по узлам от родителя к родителю, можно выполнить за время, пропорциональное количеству узлов пути. Для реализации оператора LABEL можно использовать другой массив L, в котором элемент L[i] будет хранить метку узла і, либо объявить элементы массива А записями, состоящими из целых чисел (курсоров) и меток.
Пример 3.6. На рис. 3.7 показаны дерево и массив А курсоров на родителей этого дерева.
Использование указателей или курсоров на родителей не помогает в реализации операторов, требующих информацию о сыновьях. Используя описанное представление, крайне тяжело для данного узла п найти его сыновей или определить его высоту. Кроме того, в этом случае невозможно определить порядок сыновей узла (т.е. какой сын находится правее или левее другого сына). Поэтому нельзя реализовать операторы, подобные LEFTMOST_CHILD и RIGHTJ3IBLING. Можно ввести искусственный порядок нумерации узлов, например нумерацию сыновей в возрастающем порядке слева направо. Используя такую нумерацию, можно реализовать оператор RIGHT_SIBLING, код для этого оператора приведен в листинге 3.4. Для задания типов данных node (узел) и TREE (Дерево) используется следующее объявление:
TREE = array [1..maxnodes] of node;
В этой реализации мы предполагаем, что нулевой узел Λ представлен О
Листинг 3.4. Оператор определения правого брата
procedure RIGHT_SIBLING ( n: node; Т: TREE ) : node;
Представление деревьев с использованием списков сыновей
Важный и полезный способ представления деревьев состоит в формировании для каждого узла списка его сыновей. Эти списки можно представить любым методом, описанным в главе 2, но, так как число сыновей у разных узлов может быть разное, чаще всего для этих целей применяются связанные списки.
На рис. 3.8 показано, как таким способом представить дерево, изображенное на рис. 3.7, а. Здесь есть массив ячеек заголовков, индексированный номерами (они же имена) узлов. Каждый заголовок (header) указывает на связанный список, состоящий из «элементов»-узлов. Элементы списка header[i] являются сыновьями узла і, например узлы 9 и 10 — сыновья узла 3.
Прежде чем разрабатывать необходимую структуру данных, нам надо в терминах абстрактного типа данных LIST (список узлов) сделать отдельную реализацию списков сыновей и посмотреть, как эти абстракции согласуются между собой. Позднее мы увидим, какие упрощения можно сделать в этих реализациях. Начнем со следующих объявлений типов:
labels: array[1..maxnodes] of labeltype;
Мы предполагаем, что корень каждого дерева хранится отдельно в поле root (корень). Для обозначения нулевого узла используется 0.
В листинге 3.5 представлен код функции LEFTMOST_CHILD. Читатель в качестве упражнения может написать коды других операторов.
Листинг 3.5. Функция нахождения самого левого сына
function LEFTMOST_CHILD ( n: node; Т: TREE ): node;
if EMPTY(і) then n является листом >
Теперь представим конкретную реализацию списков, где типы LIST и position имеют тип целых чисел, последние используются как курсоры в массиве записей cellspace (область ячеек):
cellspace: array[1..maxnodes] of record
Для упрощения реализации можно положить, что списки сыновей не имеют ячеек заголовков. Точнее, мы поместим T.header[n] непосредственно в первую ячейку списка, как показано на рис. 3.8. В листинге 3.6 представлен переписанный (с учетом этого упрощения) код функции LEFTMOST_CHILD, а также показан код функции PARENT, использующий данное представление списков. Эта функция более трудна для реализации, так как определение списка, в котором находится заданный узел, требует просмотра всех списков сыновей.
Листинг 3.6. Функции, использующие представление деревьев посредством связанных списков
function LEFTMOST_CHILD ( n: node; Т: TREE >: node;
function PARENT ( n: node; T: TREE ): node;
Представление левых сыновей и правых братьев
Среди прочих недостатков описанная выше структура данных не позволяет также с помощью операторов CREATEi создавать большие деревья из малых. Это является следствием того, что все деревья совместно используют массив cellspace для представления связанных списков сыновей; по сути, каждое дерево имеет собственный массив заголовков для своих узлов. А при реализации, например, оператора CREATE2(v, Т1, Т2) надо скопировать деревья Т1 и Т2 в третье дерево и добавить новый узел с меткой v и двух его сыновей — корни деревьев Т1 и Т2.
Если мы хотим построить большое дерево на основе нескольких малых, то желательно, чтобы все узлы всех деревьев располагались в одной общей области. Логическим продолжением представления дерева, показанного на рис. 3.8, будет замена массива заголовков на отдельный массив nodespace (область узлов), содержащий записи с произвольным местоположением в этом массиве. Содержимое поля header этих записей соответствует «номеру» узла, т.е. номеру записи в массиве cellspace, всвою очередь поле node массива cellspace теперь является курсором для массива nodespace, указывающим позицию узла. Тип TREE в этой ситуации «просто курсор в массиве nodespace, указывающий позицию корня.
Пример 3.7. На рис. 3.9, а показано дерево, а на рис. 3.9, б — структура данных, где узлы этого дерева, помеченные как А, В, С и D, размещены в произвольных позициях массива nodespace. В массиве cellspace также в произвольном порядке размещены списки сыновей.
Структура данных, показанная на рис. 3.9, б, уже подходит для того, чтобы организовать слияние деревьев с помощью операторов CREATEi. Но и эту структуру можно значительно упростить. Для этого заметим, что цепочка указателей поля next массива cellspace перечисляет всех правых братьев.
Используя эти указатели, можно найти самого левого сына следующим образом. Предположим, что cellspace[i].node = п. (Повторим, что «имя» узла, в отличие от его метки, является индексом в массиве nodespace и этот индекс записан в поле cell-space[i].node.) Тогда указатель nodespace[n].header указывает на ячейку самого левого сына узла п в массиве cellspace, поскольку поле node этой ячейки является именем этого узла в массиве nodespace.
Можно упростить структуру, если идентифицировать узел не с помощью индекса в массиве nodespace, а с помощью индекса ячейки в массиве cellspace, который соответствует данному узлу как сыну. Тогда указатель next (переименуем это поле в right_sibling — правый брат) массива cellspace будет точно указывать на правого брата, а информацию, содержащуюся в массиве nodespace, можно перенести в новое поле leftmost_child (самый левый сын) массива cellspace. Здесь тип TREE является целочисленным типом и используется как курсор в массиве cellspace, указывающий на корень дерева. Массив cellspace можно описать как следующую структуру:
Пример 3.8. Новое представление для дерева, показанного на рис. 3.9, а, схематически изображено на рис. ЗЛО. Узлы дерева расположены в тех же ячейках массива, что и на рис. 3.9, б.
Используя описанное представление, все операторы, за исключением PARENT, можно реализовать путем прямых вычислений. Оператор PARENT требует просмотра всего массива cellspace. Если необходимо эффективное выполнение оператора PARENT, то можно добавить четвертое поле в массив cellspace для непосредственного указания на родителей.
В качестве примера операторов, использующих структуры данных рис. З.10, напишем код функции CREATE2, показанный в листинге 3.7. Здесь мы предполагаем, что неиспользуемые ячейки массива cellspace связаны в один свободный список, который в листинге назван как avail, и ячейки этого списка связаны посредством поля right_sibling. На рис. 3.11 показаны старые (сплошные линии) и новые (пунктирные линии) указатели в процессе создания нового дерева.
function CREATE2 ( v: labeltype; Т1, Т2: integer ): integer;
для корня нового дерева >
Можно уменьшить область памяти, занимаемую узлами дерева (но при этом увеличится время выполнения операторов), если в поле right_sibling самого правого сына вместо нулевого указателя поместить указатель на родителя. Но в этом случае, чтобы избежать двусмысленности, необходимо в каждую ячейку поместить еще двоичную (логическую) переменную, которая будет показывать, что содержится в поле right_sibling: указатель на правого брата или указатель на родителя.
При такой реализации можно найти для заданного узла его родителя, следуя за указателями поля right_sibling, пока не встретится указатель на родителя. В этом случае время, необходимое для поиска родителя, пропорционально количеству сыновей у родителя.
Источник
Дерево
Дерево – структура данных, представляющая собой древовидную структуру в виде набора связанных узлов.
Бинарное дерево — это конечное множество элементов, которое либо пусто, либо содержит элемент ( корень ), связанный с двумя различными бинарными деревьями, называемыми левым и правым поддеревьями . Каждый элемент бинарного дерева называется узлом . Связи между узлами дерева называются его ветвями .
Способ представления бинарного дерева: 
- A — корень дерева
- В — корень левого поддерева
- С — корень правого поддерева
Корень дерева расположен на уровне с минимальным значением.
Узел D , который находится непосредственно под узлом B , называется потомком B . Если D находится на уровне i , то B – на уровне i-1 . Узел B называется предком D .
Максимальный уровень какого-либо элемента дерева называется его глубиной или высотой .
Если элемент не имеет потомков, он называется листом или терминальным узлом дерева.
Остальные элементы – внутренние узлы (узлы ветвления).
Число потомков внутреннего узла называется его степенью . Максимальная степень всех узлов есть степень дерева.
Число ветвей, которое нужно пройти от корня к узлу x , называется длиной пути к x . Корень имеет длину пути равную 0 ; узел на уровне i имеет длину пути равную i .
Бинарное дерево применяется в тех случаях, когда в каждой точке вычислительного процесса должно быть принято одно из двух возможных решений.
Имеется много задач, которые можно выполнять на дереве.
Распространенная задача — выполнение заданной операции p с каждым элементом дерева. Здесь p рассматривается как параметр более общей задачи посещения всех узлов или задачи обхода дерева.
Если рассматривать задачу как единый последовательный процесс, то отдельные узлы посещаются в определенном порядке и могут считаться расположенными линейно.
Способы обхода дерева
Пусть имеем дерево, где A — корень, B и C — левое и правое поддеревья.
Существует три способа обхода дерева:
- Обход дерева сверху вниз (в прямом порядке): A, B, C — префиксная форма.
- Обход дерева в симметричном порядке (слева направо): B, A, C — инфиксная форма.
- Обход дерева в обратном порядке (снизу вверх): B, C, A — постфиксная форма.
Реализация дерева
Узел дерева можно описать как структуру:
При этом обход дерева в префиксной форме будет иметь вид
Обход дерева в инфиксной форме будет иметь вид
Обход дерева в постфиксной форме будет иметь вид
Бинарное (двоичное) дерево поиска – это бинарное дерево, для которого выполняются следующие дополнительные условия (свойства дерева поиска):
- оба поддерева – левое и правое, являются двоичными деревьями поиска;
- у всех узлов левого поддерева произвольного узла X значения ключей данных меньше, чем значение ключа данных самого узла X ;
- у всех узлов правого поддерева произвольного узла X значения ключей данных не меньше, чем значение ключа данных узла X .
Данные в каждом узле должны обладать ключами, на которых определена операция сравнения меньше.
Как правило, информация, представляющая каждый узел, является записью, а не единственным полем данных.
Для составления бинарного дерева поиска рассмотрим функцию добавления узла в дерево.
Добавление узлов в дерево
Удаление поддерева
Пример Написать программу, подсчитывающую частоту встречаемости слов входного потока.
Поскольку список слов заранее не известен, мы не можем предварительно упорядочить его. Неразумно пользоваться линейным поиском каждого полученного слова, чтобы определять, встречалось оно ранее или нет, т.к. в этом случае программа работает слишком медленно.
Один из способов — постоянно поддерживать упорядоченность уже полученных слов, помещая каждое новое слово в такое место, чтобы не нарушалась имеющаяся упорядоченность. Воспользуемся бинарным деревом.
В дереве каждый узел содержит:
- указатель на текст слова;
- счетчик числа встречаемости;
- указатель на левого потомка;
- указатель на правого потомка.
Рассмотрим выполнение программы на примере фразы
now is the time for all good men to come to the aid of their party
При этом дерево будет иметь следующий вид 
Результат выполнения 
Источник
