Главная | Обратная связь | Поможем написать вашу работу!

Представления множеств

Обычно списки применяются для представления множеств. При этом объем памяти, необходимый для представления множества, пропорционален числу его элементов. Время, требуемое для выполнения операции над множествами, зависит от природы операции. Например, пусть А и В — два множества. Операция требует времени, по крайней мере пропорционального сумме размеров этих множеств, поскольку как список, представляющий А, так и список, представляющий В, надо просмотреть хотя бы один раз.

Подобным же образом операция требует времени, пропорционального сумме размеров множеств, поскольку надо выделить элементы, входящие в оба множества, и вычеркнуть один экземпляр каждого такого элемента. Если же и не пересекаются, можно найти за время, не зависящее от размера и . Для этого достаточно сделать конкатенацию списков. Задача объединения двух непересекающихся множеств усложняется, если необходимо быстро определять, входит ли данный элемент в данное множество.

Другой способ представления множества, отличный от представления его в виде списка,— представление в виде двоичного (битового) вектора. Пусть U — универсальное множество (т. е. все рассматриваемые множества являются его подмножествами), состоящее из элементов. Линейно упорядочим его. Подмножество представляется в виде вектора из битов, такого, что t-й разряд в равен 1 тогда и только тогда, когда i-й элемент множества принадлежит S. Будем называть характеристическим вектором для S.

Для представления множеств посредством характеристических 0-1-векторов необходимо иметь оценку мощности универсального множества (т.к. массив – статическая структура данных) и установить взаимно однозначное соответствие[18] между элементами универсального множества и областью допустимых значений индексов массива-вектора. При таком представлении базовые операции для множеств реализуются с хорошими характеристиками по времени, но по памяти оно может оказаться расточительным, если универсальное множество очень большое, а используемые его подмножества относительно очень маленькие (получаем случай очень разреженного массива). Для реализации теоретико-множественных операций (È, Ç, разность) потребуется полный просмотр такого вектора (размером, равным мощности универсального множества).

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

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

Для представления более сложных АТД используются более сложно организованные структуры данных.

Графы

Известно несколько представлений графа G=(V, E). Один из них — матрица смежностей, т.е. матрица А размера ||V||x||V||, состоящая из 0 и 1, в которой =1 тогда и только тогда, когда есть ребро из узла i в узел у. Представление в виде матрицы смежностей удобно для тех алгоритмов на графах, которым часто нужно знать, есть ли в графе данное ребро, ибо время, необходимое для определения наличия ребра, фиксировано и не зависит от ||V|| и \\E\\. Основной недостаток применения матрицы смежностей заключается в том, что она занимает память объема даже тогда, когда граф содержит только ребер. Уже начальное заполнение матрицы смежностей посредством "естественной" процедуры требует времени , что сводит на нет алгоритмы сложности при работе с графами, содержащими лишь ребер. Хотя разработаны методы для преодоления этой трудности, почти неизбежно возникают другие проблемы, которые приводят к тому, что алгоритмы сложности О(||V||), основанные на работе с матрицей смежностей, встречаются редко. Интересной альтернативой является представление строк и (или) столбцов матрицы смежностей в виде двоичных векторов. Такое представление может способствовать значительной эффективности алгоритмов на графах.

Еще одно возможное представление графа — с помощью списков. Списком смежностей для узла v называется список всех узлов w, смежных с v. Граф можно представить с помощью списков смежностей, по одному для каждого узла.

Деревья.

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

Определение. Ориентированный граф без циклов называется ориентированным ациклическим графом. (Ориентированное) дерево (иногда его называют корневым деревом) — это ориентированный ациклический граф, удовлетворяющий следующим условиям:

1) имеется в точности один узел, называемый корнем, в который не входит ни одно ребро,

2) в каждый узел, кроме корня, входит ровно одно ребро,

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

Ориентированный граф, состоящий из нескольких деревьев, называется лесом. Леса и деревья — столь часто встречающиеся частные случаи ориентированных ациклических графов, что для описания их свойств стоит ввести специальную терминологию.

Определение. Пусть F=(V, E) — граф, являющийся лесом. Если принадлежит Е, то называется отцом узла , a — сыном узла . Если есть путь из в , то называется предком узла , a — потомком узла . Более того, если , то называется подлинным предком узла , a — подлинным потомком узла . Узел без подлинных потомков называется листом. Узел и его потомки вместе образуют поддерево леса F, и узел называется корнем этого поддерева.

Глубина узла v в дереве — это длина пути из корня в v. Высота узла v в дереве — это длина самого длинного пути из v в какой-нибудь лист. Высотой дерева называется высота его корня. Уровень узла v в дереве равен разности высоты дерева и глубины узла v.

Например, на рис. 2.7,а узел 3 имеет глубину 2, высоту 0 и уровень 1. Упорядоченным деревом называется дерево, в котором множество сыновей каждого узла упорядочено. При изображении упорядоченного дерева мы будем считать, что множество сыновей каждого узла упорядочено слева направо. Двоичным (бинарным) деревом называется такое упорядоченное дерево, что

1) каждый сын произвольного узла идентифицируется либо как левый сын, либо как правый сын,

2) каждый узел имеет не более одного левого сына и не более одного правого сына.

Поддерево , корнем которого является левый сын узла v (если такое существует), называется левым поддеревом узла v. Аналогично поддерево корнем которого является правый сын узла v (если такое существует), называется правым поддеревом узла v. Все узлы в расположены левее всех узлов в .

Двоичное дерево обычно представляют в виде двух массивов ЛЕВЫЙСЫН и ПРАВЫЙСЫН. Пусть узлы двоичного дерева занумерованы целыми числами от 1 до . В этом случае ЛЕВЫЙСЫН[i]=j тогда и только тогда, когда узел с номером j является левым сыном узла с номером i. Если у узла i нет левого сына, то ЛЕВЫЙСЫН[i]=0. ПРАВЫЙСЫН[i] определяется аналогично.

Двоичное дерево называется полным, если для некоторого целого числа k каждый узел глубины меньшей k имеет как левого, так и правого сына и каждый узел глубины k является листом. Полное двоичное дерево высоты k имеет ровно узлов.

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

Определение. Пусть Т — дерево о корнем и сыновьями , . При k=0 это дерево состоит из единственного узла .

Прохождение дерева Т в прямом порядке определяется следующей рекурсией:

1) посетить корень ,

2) посетить в прямом порядке поддеревья с корнями в указанной последовательности.

Прохождение дерева Т в обратном порядке определяется следующей рекурсией:

1) посетить в обратном порядке поддеревья с корнями в указанной последовательности,

2) посетить корень .

Прохождение двоичного дерева во внутреннем порядке определяется следующей рекурсией:

1) посетить во внутреннем порядке левое поддерево корня (если оно существует),

2) посетить корень,

3) посетить во внутреннем порядке правое поддерево корня (если оно существует)

При нумерации в прямом порядке все узлы поддерева с корнем имеют номера, не меньшие . Точнее, если — множество потомков узла , то v будет номером некоторого узла из тогда и только тогда, когда . Поставив в соответствие каждому узлу v его номер в прямом порядке и количество его потомков, легко определить, является ли некоторый узел w потомком для v. После того как номера присвоены (в соответствии с прямым порядком) и вычислено количество потомков каждого узла, на вопрос, является ли w потомком для v, можно ответить за фиксированное время, не зависящее от размера дерева. Номера, соответствующие обратному порядку, обладают аналогичным свойством. Номера узлов двоичного дерева, соответствующие внутреннему порядку, обладают тем свойством, что номера узлов в левом поддереве для v меньше v, а в правом поддереве больше v. Таким образом, чтобы найти узел с номером w, надо сравнить w с корнем . Если , то искомый узел найден. Если , то надо повторить этот процесс для левого поддерева; если , то повторить процесс для правого поддерева. В конце концов узел с номером w будет найден.

Список основных операций навигации по дереву (операций доступа к компонентам дерева) [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 позицией корня.

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

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

§ Видимо самый простой способ представления – основан на том, что для каждой вершины (не корня) однозначно определена родительская вершина. Дерево с (пронумерованными) вершинами 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 сыновьями (у каждой вершины).

Все вышеприведенные операции навигации реализуемы для такого представления с константным временем выполнения. Но по памяти такое представление неэкономично для существенно-неполных деревьев, оно потребует примерно 2^k единиц памяти, где k – длина самой длинной ветви (даже если такая ветвь только одна, а все остальные существенно короче). Т.к. в таком векторе имеется позиция для каждой вершины полного дерева, а в нашем дереве большая часть вершин этого полного дерева может отсутствовать, то мы можем получить экспоненциальный перерасход памяти.

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

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

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

Дерево по определению обладает рекурсивной структурой. Это обстоятельство создает условия использования рекурсивных процедур. Процедуру, которая прямо или косвенно обращается к себе, называют рекурсивной. Применение рекурсии часто позволяет давать более прозрачные и сжатые описания алгоритмов, чем это было бы возможно без рекурсии.

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

Алгоритм 2.1. Нумерация узлов двоичного дерева в соответствии с внутренним порядком

Вход. Двоичное дерево, представленное массивами ЛЕВЫЙСЫН и ПРАВЫЙСЫН.

Выход. Массив, называемый НОМЕР, такой, что НОМЕР[i]— номер узла i во внутреннем порядке.

Метод. Кроме массивов ЛЕВЫЙСЫН, ПРАВЫЙСЫН и НОМЕР, алгоритм использует глобальную переменную СЧЕТ, значение которой — номер очередного узла в соответствии с внутренним порядком. Начальным значением переменной СЧЕТ является 1. Параметр УЗЕЛ вначале равен корню. Cам алгоритм таков:

begin

СЧЕТ 1;

ВНУТПОРЯДОК(КОРЕНЬ)

end?

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

а операторы работы со стеком усложнили бы алгоритм.

procedure ВНУТПОРЯДОК(УЗЕЛ):

begin

1. if ЛЕВЫЙСЫН[УЗЕЛ] 0 then ВНУТПОРЯДОК(ЛЕВЫЙСЫН[УЗЕЛ]);

2. НОМЕР[УЗЕЛ] СЧЕТ;

3. СЧЕТ СЧЕТ + 1;

4. if ПРАВЫЙСЫН[УЗЕЛ] 0 then ВНУТПОРЯДОК(ПРАВЫЙСЫН[УЗЕЛ])

End

Вариант алгоритма во внутреннем порядке без рекурсии

Вход. Тот же, что у предыдущего алгоритма.

Выход. Тот же, что у предыдущего алгоритма.

Метод. При прохождении дерева в стеке запоминаются все узлы, которые еще не были занумерованы и которые лежат на пути из корня в узел, рассматриваемый в данный момент. При переходе из узла v к его левому сыну узел v запоминается в стеке. После

нахождения левого поддерева для v узел v нумеруется и выталкивается из стека. Затем нумеруется правое поддерево для v. При переходе из и к его правому сыну узел v не помещается в стек, поскольку после нумерации правого поддерева мы не хотим возвращаться в у; более того, мы хотим вернуться к тому предку

begin

СЧЕТ 1;

УЗЕЛ КОРЕНЬ;

СТЕК пустой;

левый: while ЛЕВЫЙСЫН[УЗЕЛ] 0 do

begin

затолкнуть УЗЕЛ в СТЕК;

УЗЕЛ ЛЕВЫЙСЫН[УЗЕЛ]

end;

центр: НОМЕР[УЗЕЛ1 СЧЕТ;

СЧЕТ — СЧЕТ+1;

if ПРАВЫЙСЫН[УЗЕЛ[ 0 then

begin

УЗЕЛ ПРАВЫЙ СЫН[УЗЕЛ];

goto левый

end;

if СТЕК не пуст then

begin

УЗЕЛ элемент в вершине СТЕКа;

вытолкнуть из СТЕКа;

goto центр

end

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

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

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

§ Каждая вершина с дочерними вершинами v₁, v₂,..., v_d хранит d-1 ключей k₁ £... £ k_d_-1;

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

§ Бинарное дерево поиска (с уникальными ключами[19]) [4 гл.12; 3 гл.12] – это бинарное упорядоченное дерево, у которого каждой вершине приписан уникальный ключ поиска, причем выполнено соотношение: ключи (всех) вершин левого поддерева < ключ родителя < ключи (всех) вершин правого поддерева. Отметим, что ключи в вершинах такого дерева расположены по возрастанию в соответствии с инфиксным (внутренним) обходом.

Отметим особенность (геометрического характера) таких деревьев – у вершин такого бинарного дерева допускается наличие правого сына при отсутствии левого, т.е. фиксируется не просто порядок на множестве дочерних вершин, но и их позиция (даже если позиция левого свободна). Хотя, с другой стороны, эту ситуацию можно трактовать как наличие двух детей, из которых левый – «пустой» (фиктивный)[20].

Для таких деревьев время поиска по ключу ≤ 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 (АТД «Множество», «Словарь» и «Очередь с приоритетом») сохранялось O (log(n)). Балансировку структуры дерева можно проводить и по высоте, и по объему (весу) поддеревьев [18 п.6.4].

Для бинарных деревьев известны методы балансировки – АВЛ-деревья [13 п.9.2], красно-черные деревья (RB-tree) и их вариации.

§ красно-черные деревья [4,]

Красно-черное дерево - это двоичное дерево поиска, обладающее следующими свойствами(будем называть их RB свойствами):

Ø Каждый узел дерева покрашен либо в черный, либо в красный цвет.

Ø Листьями объявляются NIL-узлы ("виртуальные" узлы, являющиеся сыновьями узлов, которые в двоичном дереве поиска являлись листьями). Листья покрашены в черный цвет.

Ø Если узел красный, то оба его сына являются черными.

Ø На всех ветвях дерева, ведущих от его корня к листьям, число черных узлов одинаково.

Количество черных узлов на ветви от корня до листа называется черной высотой дерева. Перечисленные свойства гарантируют, что самая длинная ветвь, ведущая от корня к листу, не более чем в два раза длиннее любой другой ветви от корня к листу. Чтобы понять, почему это так, рассмотрим дерево с черной высотой . Кратчайшее возможное расстояние от корня до листа равно - когда все узлы черные. Длиннейшее расстояние от корня до листа равно , узлы при этом покрашены таким образом, что цвета чередуются (от корня к листу) так: красный, черный, красный, черный, …, красный, черный. Сюда нельзя добавить черные узлы, поскольку при этом нарушится свойство 4, из которого вытекает корректность понятия черной высоты. Поскольку согласно свойству 3 у красных узлов непременно черные наследники, в подобной последовательности недопустимы и два красных узла подряд. Таким образом, длиннейший путь, который мы можем сконструировать, состоит из чередования красных и черных узлов, что и приводит нас к удвоенной длине пути, проходящего только через черные узлы. Все операции над деревом должны уметь работать с перечисленными свойствами. В частности, при вставке и удалении эти свойства должны сохраниться. При соблюдении RB свойств, имеет место

Лемма[Кормен]. Красно-черное дерево с внутренними вершинами (не считая NIL листьев имеет высоту не более )

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

Восстановление этих свойств требует перекраски некоторых вершин, а также выполнения операций вращения

Операции левого и правого вращения являются обратными друг другу. При добавлении нового узла сначала ведется поиск места этого узла в дереве. Узел красится в красный цвет, его сыновья (NIL-узлы) окрашены в черные цвета. При вставке может быть нарушено RB-свойство 3, поскольку отец вставленной вершины также может быть окрашен в красный цвет. Если необходимо, мы перекрашиваем узел и производим поворот, чтобы сбалансировать дерево. Рассмотрим ситуацию, когда отец нового узла - красный: при этом будет нарушено свойство 3. Достаточно рассмотреть следующие два случая:

Красный отец, красный "дядя": Ситуацию красный-красный иллюстрирует рис. У нового узла X отец А и "дядя" С оказались красными. Простое перекрашивание избавляет нас от красно-красного нарушения. После перекраски нужно проверить "дедушку" нового узла (узел B), поскольку он может оказаться красным. Необходимо обратить внимание на распространение влияния красного узла на верхние узлы дерева. В самом конце корень красится в черный цвет. Если он был красным, то при этом увеличивается черная высота дерева

Красный отец, черный "дядя": На рис. представлен другой вариант красно-красного нарушения - "дядя" нового узла оказался черным. Здесь узлы может понадобиться вращать, чтобы скорректировать поддеревья. В этом месте алгоритм может остановиться из-за отсутствия красно-красных конфликтов и вершина дерева (узел A) окрашивается в черный цвет. Если узел X был в начале правым потомком, то первым применяется левое вращение, которое делает этот узел левым потомком. Каждая корректировка, производимая при вставке узла, заставляет нас подняться в дереве на один шаг. В этом случае до остановки алгоритма будет сделано 1 вращение (2, если узел был правым потомком). Метод удаления рассматривается аналогично.

¨ Splay-дерево [19 п.4.3; 3 п.13.2]

Специфическая структура данных – Splay-дерево. Это бинарное дерево поиска, но при этом не поддерживается явного баланса, оно может оказаться разбалансированным в определенном (традиционном) смысле. Вместо этого после выполнения каждой операции, типовой для бинарных поисковых деревьев, осуществляется перестройка (сохраняющая определяющие свойства поискового дерева) с целью «подтянуть» вершины текущего пути дерева поближе к корню, что ускоряет их нахождение в будущем. Для такого представления вышеупомянутые операции с множествами (и некоторый набор дополнительных операций) имеют время работы 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-ю) последовательность.

Такое позиционное представление ключа эффективно используется в алгоритмах позиционной сортировки (сегментная-поразрядная сортировка, bucket- radix 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]

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

На рисунке приведен пример двоичной невозрастающей пирамиды. Несложно заметить, что ключи в каждой вершине не меньше максимального из ключей левого и правого поддеревьев. Дерево является сбалансированным, высота этого дерева равна , где - число вершин дерева. Заметим, что последовательность элементов, лежащих на пути от листа к корню, всегда линейно упорядочена, а наибольший элемент дерева приписан его корню. Как видно в этой структуре легко находится максимальный элемент, а перестройка дерева в пирамиду после удаления максимального элемента занимает O (log(n)).

Для пирамид представление с помощью массива, основанное на нумерации вершин (см. выше преамбулу п.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(H₁, H₂): создает (и возвращает) новую пирамиду, которая содержит все вершины пирамид H₁ и H₂. Исходные пирамиды должны не иметь общих ключей, и при выполнении этой операции они уничтожаются.

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

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

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

Время выполнения операций у разных реализаций сливаемых пирамид:

Операция	Бинарная пирамида (наихудший случай)	Биномиальная пирамида (наихудший случай)	Пирамида Фибоначчи (амортизированное время)
Make_Heap	Q (1)	Q (1)	Q (1)
Insert	Q (log(n))	O (log(n))	Q (1)
Minimum	Q (1)	O (log(n))	Q (1)
Extract_Min	Q (log(n))	Q (log(n))	O (log(n))
Union	Q (n)	W(log(n))	Q (1)
Decrease_Key	Q (log(n))	Q (log(n))	Q (1)
Delete (см. уточнение ниже)	Q (log(n))	Q (log(n))	O (log(n))
Найти (элемент по ключу), Принадлежать	O (n)	O (n)	O (n)

Все три указанных вида пирамид не могут обеспечить эффективную реализацию поиска элемента с заданным ключом (операции Найти и Принадлежать АТД «Множество» и «Словарь»), поэтому операции Decrease_Key и Delete в качестве параметра получают указатель на вершину, а не значение её ключа.

Замечание. Но дополнительно используя подходящую структуру данных для работы со словарем вершин можно устранить это ограничение.

Фибоначчиевы пирамиды особенно полезны в случае, когда количество операций Extract_Min и Delete относительно мало по сравнению с количеством других операций. Такая ситуация возникает во многих приложениях. Однако с практической точки зрения программная сложность реализации и высокие значения постоянных множителей в формулах времени работы существенно снижают эффективность применения фибоначчиевых пирамид, делая их для многих приложений менее привлекательными, чем обычные бинарные (или к-арные) пирамиды, если не нужна операция Union.

¨ Структуры данных для непересекающихся множеств (отношения эквивалентности). [4 гл.21]

Основные принципы организации таких структур данных и методов работы с ними были проиллюстрированы во введении (Пример 3 Связность).

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

§ Вливание меньшего множества в большее. Это позволяет поддерживать приемлемую сбалансированность деревьев по их объему (а в результате и по длине путей).

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

⇐ Предыдущая 4 5 6 7 8 9 10 111213 Следующая ⇒