Главная » Java, Структуры данных и алгоритмы » Основные алгоритмы, выполняемые над деревьями

0

В этом разделе представлены алгоритмы выполнения операций над деревом с использованием методов АТД, соответствующих интерфейсу InspectableTree.

Исходные положения

Чтобы проанализировать выполнение алгоритмов раздела 6.2, сделаем следующие допущения.

•                          Методы доступа root() и parent() выполняются за 0(1) времени.

•                                     Методы запросов islnternal(v), isExternal(v) и isRoot(v) также выполняются за 0(1) времени.

•                                      Метод доступа children(v) требует 0(cv) времени, где cv — количество дочерних элементов v.

•                                     Общие методы swapElements(v) и replaceElement(v,e) требуют 0(1) времени.

•                                     Общие методы elements() и positions(), возвращающие итераторы, выполняются за 0(п) времени, где п — количество узлов в дереве.

•                                     Для итераторов, возвращаемых методами elements(), positions() и children(v), методы hasNext(), nextObject() или nextPosition() выполняются за 0(1) времени каждый.

В разделе 6.4 представлены отвечающие перечисленным условиям структуры данных деревьев. Прежде чем приступить к описанию реализации АТД «дерево», использующего конкретную структуру данных, поясним применение методов АТД «дерево» для решения нескольких интересных с точки зрения древовидных структур задач.

Глубина и высота

Допустим, v — узел дерева Т. Глубина узла v выражается количеством предков v, исключая сам v. Например, в дереве на рис. 6.2 узел, соответствующий Международному рынку, имеет глубину 2. Заметим, однако, что это определение предполагает, что глубина корня Т равна 0.

Глубина узла v может быть рекурсивно определена и следующим образом:

•                          если v — корень, то его глубина равна 0;

•                                     в противном случае глубина v равна единице плюс глубина родителя V.

Исходя из приведенного определения, рекурсивный алгоритм depth, показанный во фрагменте кода 6.3, вычисляет глубину узла v дерева Г, рекурсивно обращаясь к родителю v и добавляя 1 к возвращаемому значению. Таким образом, каждый предок v получает рекурсивный вызов и возвращает значение глубины, равное 1.

Алгоритм depth (r,v)! if’T.isRoot(v) then

return 0 else

return 1+depth(r, T.parent(i/)) Фрагмент кода 6.3. Алгоритм depth для вычисления глубины узла v дерева Т Простая реализация алгоритма depth показана во фрагменте кода 6.4.

public static int depth (InspectableTree T, Position v) { if (T.isRbot(v)) return 0;

else

return 1 + depth(T, T.parent(v));

}

Фрагмент кода 6.4. Метод depth, написанный на Java

Время выполнения алгоритма depth(77,v) равно 0(1 + dv), где ^указывает глубину узла v дерева Г, поскольку для каждого из предков v алгоритм осуществляет рекурсивную операцию, время выполнения которой- постоянно. Таким образом, в худшем случае алгоритм определения глубины узла требует 0(п) времени, где п — общее количество узлов дерева Т, прц условии, что некоторые узлы могут иметь такую глубину з Г. Хотя такое время выполнения является функцией исходного размера (input size), было бы точнее проанализировать время выполнения с помощью параметра поскольку оно обычно будет гораздо* меньше, чем при п.

Высота узла v дерева Г также определяется рекурсивно:

•           если v является простым узлом, то высота v равна 0;

•          в противнЬм случае высота v равна 1 плюс максимальная высока дочернего элемента узла v.

Высота дерева Т равна высоте корня Т. Например, дерево на рис. 6.2 имеет высоту 4. Кроме того, высота может рассматриваться и нижеприведенным образом.

Утверждение 6.1. Высота дерева Т равна максимальной глубине простого узла дерева Т.

Оставим доказательство этого утверждения для практического упраж- . нения (М-6.4). А здесь представляем алгоритм height 1, показанный во фрагменте кода 6.5 и реализованный на Java во фрагменте кода 6.6, позволяющий вычислять высоту дерева Т, исходя из сделанного только что

утверждения. Этот алгоритм получает итератор всех узлов дерева, чтобы вычислить глубину каждого простого узла с помощью алгоритма depth (фрагмент кода 6.3) в качестве вспомогательного метода, сохраняя на каждом шаге значение максимальной глубины.

Алгоритм heightl(T): h=0

for each v e 7".positions() do if T.isExternal(i/) then h = max(h, depth (T,i/)) return h

Фрагмент кода 6.5. Алгоритм heightl для вычисления высоты дерева Т. Здесь в качестве вспомогательного используется алгоритм depth (фрагмент кода 6.3)

public static int heightl (InspectableTree T) { int h = 0;

Positionlterator positer = T.positions(); while (positer.hasNext()) {

Position v = positer.nextPosition(); if (T.isExternal(v))

h = Math.max(h, depth(T, v));

}

return h;

}

Фрагмент кода 6.6. Метод heightl, написанный на Java. Обратите внимание на использование метода max класса java.lang.Math

К сожалению, нельзя утверждать, что алгоритм heightl достаточно эффективен. Поскольку алгоритм heightl вызывает для каждого простого узла v дерева Г алгоритм depth, время выполнения heightl будет определяться как 0(п + <S\,??{1 + dv)), где п — количество узлов дерева Г, dv — глубина узла, Е — группа простых узлов дерева Т. Так как dv < h < п – 1 для каждого узла v, а \Е\ < п- 1 (верхний предел достигается в случае, если корень имеет п – 1 дочерних элементов), алгоритм heightl выполняется за время, равное 0(п + SVEEn)> которое в крайнем случае составит 0(п2) (см. упражнение 3-6.5).

Алгоритм height2 (фрагмент кода 6.7, реализация на Java — фрагмент кода 6.8) вычисляет высоту дерева Гболее надежным способом, используя рекурсивное определение высоты. Алгоритм представлен рекурсивным методом height2(7», вычисляющим высоту ветви дерева Г, корнем которого является узел v. Если узел v является простым, алгоритм возвращает 0. В противном случае он получает итератор дочерних элементов узла v, рекурсивно вычисляет высоту каждого из дочерних элементов v и возвращает 1 плюс максимальную высоту из рекурсивных вызовов. Таким образом, определяем высоту дерева Т, вызывая height2(!TfT.rootQ).

Алгоритм height2(7>): if 7".isExternal(i/) then

return 0 else

h=0

for each w e r.children(v) do

h = max(h, height2(T,w)) return 1 + h

Фрагмент кода 6.7. Алгоритм height2 для вычисления высоты ветви дерева Г, корнем которого служит узел v

public static int height2 (InspectableTree T, Position v) { if (T.isExternal(v))

return 0; else {

int h = 0;

Position Iterator children = T.children(v); while (children.hasNext())

h = Math.max(h, height2(T, children. nextPosition())); return 1 + h;

}

}

Фрагмент кода 6.8. Метод height2, написанный на Java

Алгоритм height2 более надежен по сравнению с height 1 (фрагмент кода 6.5). Алгоритм выполняется рекурсивно, и, поскольку вначале происходит обращение к корню дерева Т, производится последовательное обращение к каждому из узлов дерева. Таким образом, определить время выполнения этого алгоритма можно путем суммирования времени, затрачиваемого на каждый из узлов (в не рекурсивной его части). Вычисление итератора children(v) занимает 0(cv) времени, где cv — количество дочерних элементов узла v. К тому же while-циклы выполняют cv итераций, каждая из которых занимает 0(1) времени плюс время для рекурсивного обращения к дочернему элементу узла v. Таким образом, алгоритм height2 затрачивает 0(1 + cv) времени на каждый узел v, а суммарное время его выполнения составляет 0(п + Sv?j(l +cv)). Чтобы придать анализу законченную форму, воспользуемся следующим свойством.

Утверждение 6.2. Допустим, Т — дерево, имеющее п узлов, a cv представляет количество дочерних элементов узла v дерева Т. Тогда

Рис. 6.10. Дерево рис. 6.3, представляющее файловую систему с указаниями имен и размеров соответствующих файлов/директорий внутри каждого узла и дискового пространства директории каждого составного узла

Взяв за основу пример 6.9, алгоритм diskSpace, представленный фрагментом кода 6.14, выполняет обратный проход дерева файловой системы Г, выводя на печать имена и дисковое пространство, используемое под директории, соответствующее каждому составному узлу дерева Т. При обращении к корню дерева Твыполнение diskSpace занимает О(п) времени, где п — количество узлов в дереве, а выполнение вспомогательных методов name и size занимает 0(1) времени.

public static int diskSpace (InspectableTree T, Position v) { int s = size(v); // начать с размера самого узла Positionlterator children = T.children(v); while (children.hasNext())

// добавить рекурсивно вычисленное пространство, используемое // дочерними элементами узла v

s += diskSpace(T, children.nextPosition()); if (T.islnternal(v))

// распечатать имя и используемое дисковое пространство System.out.print(name(v) + ":" + s); return s;

}

Фрагмент кода 6.14. Метод diskSpace распечатывает имя и дисковое пространство, используемое директорией, ассоциируемой с узлом v, для каждого составного узла v дерева файловой системы. Данный метод вызывает вспомогательные методы name и size файла/директории, ассоциируемых с узлом

Хотя прямой и обратный проходы являются традиционными способами обращения к узлам дерева, можно применять и другие виды проходов. Например, пройти по дереву так, чтобы обратиться ко всем узлам с глубиной d, прежде чем перейти к узлам с глубиной d + 1. Такой вид прохода можно реализовать, к примеру, с помощью очереди (queue), в то время как прямой и обратный проходы используют стек (stack) (поскольку здесь имеет место рекурсия, то для описания этих методов стек применяется неявно (имплицитно), но можно использовать его и явно (эксплицитно), чтобы избежать рекурсии). К тому же бинарное дерево, описываемое ниже, поддерживает дополнительный метод-проход, известный как «симметричный проход» (inorder traversal).

Источник: Гудрич М.Т. Г93 Структуры данных и алгоритмы в Java / М.Т. Гудрич, Р. Тамассия; Пер. с англ. A.M. Чернухо. — Мн.: Новое знание, 2003. — 671 е.: ил.

По теме:

  • Комментарии