Нелинейные структуры данных: деревья, графы. Обходы деревьев в глубину и ширину

Также как и для последовательностей, доступ к компонентам (вершинам) дерева может быть определен как прямой или последовательный. Будем различать понятия: позиция вершины дерева - однозначно идентифицирующая вершину и её положение в дереве, и элемент – информация, ассоциированная с вершиной дерева (в частности, просто хранимая вместе с ней).

Список основных операций навигации по дереву (операций доступа к компонентам дерева) [7 п.3.2; 13 п.6.1.2]:

§ Root(): возвращает позицию корня дерева.

§ Parent(p): возвращает позицию «родителя» для вершины в позиции p.

§ LeftMostChild(p): возвращает позицию «самого левого сына» для вершины в

позиции p.

§ RightSibling(p): возвращает позицию «правого брата» для вершины в позиции p.

§ Element(p): возвращает элемент дерева (хранимую информацию) для вершины в

позиции p.

§ isInternal(p): проверяет, является ли p позицией внутренней вершины (не листа) .

§ isExternal(p): проверяет, является ли p позицией листа дерева.

§ isRoot(p): проверяет, является ли p позицией корня.

Для варианта с последовательным доступом к компонентам аргумент «позиция» (номер) становится не нужным, все операции привязаны к текущей позиции.

Для представления деревьев используются и массивы, и (нелинейные) связные списковые структуры данных (с указателями) и смешанные способы представления. В частности, представление структуры дерева может быть отделено от хранилища информации, привязанной к вершинам (и ребрам) дерева. 18 Фактически перейти от множества к множеству с ключами элементов – словарю.

§ Видимо самый простой способ представления – основан на том, что для каждой вершины (не корня) однозначно определена родительская вершина. Дерево с (пронумерованными) вершинами 1..n представляется вектором v[1..n], где v[i] – номер родительской вершины для вершины i . Ясно, что для такого представления хорошо реализуется операция перехода к родителю, но неэффективно – операции перехода к сыновьям. § В основу представления бинарного дерева может быть положен принцип нумерации вершин. Каждая вершина дерева получает порядковый номер p(v):

• если v является корнем, то p(v) = 1;

• если v - левый сын вершины u, то p(v) = 2*p(u);

• если v - правый сын вершины u, то p(v) = 2*p(u)+ l.

Эта нумерационная функция известна как уровневая нумерация (level numbering) вершин бинарного дерева, поскольку нумерует вершины (начиная с корня) на каждом уровне (сверху вниз) в возрастающем порядке слева направо, но пропускает номера отсутствующих вершин, соответствующего полного бинарного дерева. Бинарное дерево представляется вектором, в котором вершине v соответствует элемент с индексом p(v). Аналогичную нумерационную функцию и представление можно предложить и для деревьев с не более чем m сыновьями (у каждой вершины). Все вышеприведенные операции навигации реализуемы для такого представления с константным временем выполнения. Но по памяти такое представление неэкономично для существенно неполных деревьев, оно потребует примерно 2k единиц памяти, где k – длина самой длинной ветви (даже если такая ветвь только одна, а все остальные существенно короче). Т.к. в таком векторе имеется позиция для каждой вершины полного дерева, а в нашем дереве большая часть вершин этого полного дерева может отсутствовать, то мы можем получить экспоненциальный перерасход памяти.

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

Реализация операций модификации структуры дерева (удаления и добавления вершин) существенно зависит от их специфики и условий применения и соответствующего этой специфике способа представления дерева.

Отметим, что деревья общего вида (с переменным числом сыновей большим двух) можно представлять бинарными, подходящим способом различая в представляющем бинарном дереве ребра связи (исходного дерева) с родителем и ребра связи с братьями, как показано на рисунке (пунктиром соединены вершины представляющего дерева, ассоциируемые с вершинами-братьями исходного дерева):

¨ Поисковые деревья (search tree). [13 гл.9]

Поисковое дерево – это упорядоченное дерево, имеющее следующие свойства:

§ Каждая (нелистовая) вершина имеет по крайней мере две дочерние вершины;

§ Каждая вершина с дочерними вершинами v1, v2, ..., vd хранит d-1 ключей k1 £ ...

£ kd-1;

§ Будем считать, что k0= -¥, a kd= +¥. Для каждого ключа k, хранящегося в поддереве вершины vi (i=1..d), выполнено соотношение: ki-1 £ k £ ki.

§ Бинарное дерево поиска (с уникальными ключами19) [4 гл.12; 3 гл.12] – это бинарное упорядоченное дерево, у которого каждой вершине приписан уникальный ключ поиска, причем выполнено соотношение: ключи (всех) вершин левого поддерева < ключ родителя < ключи (всех) вершин правого поддерева. Отметим, что ключи в вершинах такого дерева расположены по возрастанию в соответствии с инфиксным (внутренним) обходом. Отметим особенность (геометрического характера) таких деревьев – у вершин такого бинарного дерева допускается наличие правого сына при отсутствии левого, т.е. фиксируется не просто порядок на множестве дочерних вершин, но и их позиция (даже если позиция левого свободна). Хотя, с другой стороны, эту ситуацию можно трактовать как наличие двух детей, из которых левый – «пустой» (фиктивный). Для таких деревьев время поиска по ключу ≤ O(h), где h – высота дерева. Но при вставке новых вершин (с ключами) могут появляться длинные ветви, поэтому для времени поиска верхняя оценка в худшем O(n), где n – количество вершин в дереве. Статистический анализ показывает, что для бинарных поисковых деревьев с n вершинами оценка высоты в среднем O(log(n)) и она такая же для операций поиска, вставки, удаления и min с множествами мощности n. Поэтому бинарное дерево поиска хороший вариант для представления АТД «Множество»,«Словарь»21 и «Очередь с приоритетом», но эффективна такая реализация только в среднем, т.е. только в среде, в которой случающиеся задержки выполнения операций некритичны, если общее время работы программы длительное и приемлемое для обрабатываемого объема входного потока.

§ Сбалансированные деревья поиска (balanced search tree) [4 гл.13-14,18; 3 гл.

13,16.3]. Верхнюю оценку в худшем для времени поиска получаем O(log(n)), если удается поддерживать сбалансированную структуру дерева поиска – не менее двух сыновей (почти) у каждой вершины и примерно одинаковая высота поддеревьев у каждого сына. На сегодняшний день разработано несколько методов перестройки деревьев поиска, которые позволяют поддерживать сбалансированную структуру дерева поиска с приемлемыми расходами по времени, так чтобы общее время в худшем для операций поиска, вставки, удаления и min (АТД «Множество», «Словарь» и 19 Можно рассматривать и случай с неуникальными ключами, хотя в этом случае придется аккуратно решать некоторые технические проблемы. 20 Аналогичное уточнение следовало бы сделать и в вышеприведенном определении поисковых деревьев общего вида, но предполагается, что эта недоговоренность устраняется использованием фиктивных сыновей. 21 Естественно, использование поискового дерева для представления множеств предполагает задание какого-нибудь линейного порядка на этих множествах, а использование для словарей – возможность сравнивать значения ключей. «Очередь с приоритетом») сохранялось O(log(n)). Балансировку структуры дерева можно проводить и по высоте, и по объему (весу) поддеревьев [18 п.6.4]. Для бинарных деревьев известны методы балансировки – АВЛ-деревья [13 п.9.2], красно-черные деревья (RB-tree) и их вариации. Специфическая структура данных – Splay-дерево [19 п.4.3; 3 п.13.2]. Это бинарное дерево поиска, но при этом не поддерживается явного баланса, оно может оказаться разбалансированным в определенном (традиционном) смысле. Вместо этого после выполнения каждой операции, типовой для бинарных поисковых деревьев, осуществляется перестройка (сохраняющая определяющие свойства поискового дерева) с целью «подтянуть» вершину этой операции (для операции удаления - её родителя), поближе к корню, что ускорит её нахождение в будущем. Для такого представления вышеупомянутые операции с множествами (и некоторый набор дополнительных операций) имеют время работы O(log(n)), но амортизированное.

Перестройка проводится с помощь трех Splay-операций:

§ Zig: Если родитель вершины x является корнем:

§ Zig-Zig: Если родитель вершины x не является конем, но x и егородитель либо оба левые либо оба правые сыновья:

§ Zig-Zag: Если родитель вершины x не является конем, но x – левый сын,а его родитель – правый сын:

Возможности организовать балансировку расширяются, если допускать изменение количества сыновей вершины в фиксированном диапазоне [k,m]. К таким методам балансировки относятся 2-3 деревья, В-деревья и их вариации. Сильно ветвящиеся В-деревья представляют особый интерес при работе с данными, хранящимися во внешней памяти. Существует множество других операций над сбалансированными деревьями, которые поддерживают их сбалансированность. Сбалансированные деревья используются и для представления последовательностей таким образом, что можно будет быстро вставлять элементы в последовательность, преодолевая трудности, которые связаны с последовательным расположением элементов (в массиве), и обеспечивая при этом произвольный доступ к элементам последовательности, т. е. преодолевая сложности связанного размещения элементов. При этом такие представления позволяют эффективно реализовать операции сцепить (конкатенация) и расцепить для последовательностей. Исследуются и известны расширения выше отмеченных структур данных предназначенные для применения в различных предметных областях, естественно имеющих свою специфику интерпретации данных. Например, расширение красно- черных деревьев для работы с ключами вида интервал вещественных чисел [4 п.14.3], которое представляет прямой интерес в задачах вычислительной геометрии.

¨ Деревья цифрового (позиционного) поиска (Digital Search Trees, Trie Trees). [7 п.5.3;

3 гл.15.; 13 п.11.3]

В задачах поиска зачастую ключ поиска представлен последовательностью в (достаточно ограниченном) конечном алфавите (цифр или букв). В частности, при желании любой ключ можно трактовать как двоичную (или 16-ю) последовательность. Такое позиционное представление ключа эффективно используется в алгоритмах позиционной сортировки (сегментная-поразрядная сортировка, bucketradix sort). Если длина ключа и размер алфавита ограничены сверху константой, то можно, используя значения позиций, отказаться от полного сравнения ключей (на меньше больше), и упорядочивать множество с такими ключами за линейное время (с мультипликативной константой, зависящей от размера алфавита и длины ключа). См. [7 п.8.5; 4 гл.8; 3 гл.10.], а также Пример 2. Лексикографическая сортировка.

В дереве цифрового поиска разветвления основаны не на полном сравнении ключей, а на значении очередной позиции ключа. Такие деревья широко используются в задачах обработки текстов, а точнее для хранения и поиска слов (и текстов) в поисковых словарях: Это дерево хранит множество слов (ключей поиска) {THE, THEN, THIN, THIS, TIN, SIN, SING}. Корень соответствует пустой строке, а два его сына - префиксам Т и S. Самый левый лист представляет слово THE, следующий лист - слово THEN и т.д.

Для деревьев цифрового поиска временные характеристики основных операций аналогичны таковым для бинарного поискового дерева, т.е. O(log(n)) в среднем, но в худшем случае не превышает количества позиций в искомом ключе (т.е. минимально необходимое, в определенном смысле). Для задач обработки текстов (в частности задачи поиска по ключевым словам с точным и неточным сопоставлением) на основе деревьев цифрового поиска разработаны более сложные структуры данных (например, суффиксные деревья), позволяющие эффективно решать эти задачи [2 п.9.5; 15; 16].

¨ Пирамиды (heap), другое название – сортирующее (или частично упорядоченное)

дерево. [4 гл.6,19-20]

Неубывающая пирамида – это почти полное дерево (только уровень листьев может быть неполным), удовлетворяющее требованию – ключ каждой вершины не меньше ключа родителя. Аналогично определяются невозрастающие пирамиды. Для пирамид представление с помощью массива, основанное на нумерации вершин (см. выше преамбулу п.3.2), эффективно и по памяти, и по времени в худшем, O(log(n)) – для операций АТД «Очередь с приоритетом» (с n элементами). Алгоритм (внутренней) пирамидальной сортировки можно описать как алгоритм, который сначала строит очередь с приоритетом для сортируемой последовательности, а потом выводит её в отсортированном виде, удаляя из очереди выводимый элемент. Он имеет наилучшие (в определенном смысле) характеристики - O(nlog(n)) по времени в худшем, и при этом не требует дополнительной памяти (как например алгоритм сортировки слиянием). Отметим, что на пирамидах не удается реализовать операторы общего вида Найти и Удалить (произвольно заданный) элемент с временем выполнения O(log(n)). Разработаны и исследованы расширения пирамидальных структур данных, которые используются в практике программирования в задачах, требующих большей функциональности, чем базовый АТД очередей с приоритетом. Один из видов таких расширений известен под названием сливаемые пирамиды(mergeable heaps) - биномиальные и фибоначчиевы пирамиды. Главное функциональное отличие этих структур данных – операция слияния двух пирамид, которая создает новую пирамиду (без сохранения исходных). Сливаемые пирамиды позволяют реализовать эту операцию за время W(log(n)) в худшем случае или даже Q(1) в среднем (точнее, это амортизированное время). В то время как бинарная пирамида позволяет реализовать эту операцию только за время в худшем W(n). Основные структурные отличия этих структур данных:

§ Сливаемая пирамида – это не дерево, а лес (связанных) деревьев.

§ Деревья этого леса не почти полные, а имеют более сложную структуру. Но эта структура деревьев (с учетом леса) позволяет организовать приемлемую балансировку, в итоге она дает для операций базового АТД очередей с приоритетом такие же оценки по времени, как и классическая бинарная пирамида.

Список основных операций для (неубывающих) сливаемых пирамид:

§ Make_Heap(): создает и возвращает новую пустую пирамиду.

§ Insert(H, х): вставляет вершину х (с заполненным полем key) в пирамиду Н.

§ Minimum(H): возвращает указатель на вершину в пирамиде Н, обладающую

минимальным ключом.

§ Extract_Min(H): удаляет из пирамиды Н вершину, ключ которой минимален,

возвращая при этом указатель на эту вершину.

§ Union(H1, H2): создает (и возвращает) новую пирамиду, которая содержит все

вершины пирамид H1 и H2. Исходные пирамиды должны не иметь общих ключей, и

при выполнении этой операции они уничтожаются.

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

§ Decrease_Key(H, х, k): присваивает вершине х в пирамиде Н новое значение ключа