Двоично-троичные справочники

Двоичное дерево называют хорошо сбалансированным, если оба его поддерева имеют примерно одинаковую глубину (или размер) и сами сбалансированы. Глубина сбалансированного дерева приближенно равна log n, где n — число вершин дерева. Время, необходимое для вычислений, производимых отношениями внутри, добавить и удалить над двоичными справочниками, пропорционально глубине дерева. Таким образом, в случае двоичных справочников это время имеет порядок log n. Логарифмический рост сложности алгоритма, проверяющего принадлежность элемента множеству, — это определенное достижение по сравнению со списковым представлением, поскольку в последнем случае мы имеем линейный рост сложности с ростом размера множества. Однако плохая сбалансированность дерева ведет к деградации производительности алгоритмов, работающие со справочником. В крайнем случае, двоичный справочник вырождается в список, как показано на рис. 10.1. Форма справочника зависит от той последовательности, а которой в всего записываются элементы данных. В лучшей случае мы получаем хорошую балансировку и производительность порядка log n, а в худшем — производительность будет порядка n. Анализ показывает, что в среднем сложность алгоритмов внутри, добавить и удалить сохраняет порядок log n в допущении, что все возможные входные последовательности равновероятны. Таким образом, средняя производительность, к счастью, оказывается ближе к лучшему случаю, чек к худшему. Существует, однако, несколько довольно простых механизмов, которые поддерживают хорошую сбалансированность дерева, вне зависимости от входной последовательности, формирующей дерево. Эти механизмы гарантируют производительность алгоритмов внутри, добавить и удалить порядка log n даже в худшем случае. Один из этих механизмов - двоично-троичные деревья (кратко, 2-3 деревья), а другой — AVL-деревья.

Рис. 10.1. Полностью разбалансированный двоичный справочник. Производительность его та же, что и у списка.

2-3 дерево определяется следующим образом: оно или пусто, или состоит из единственной вершины, или удовлетворяет следующим условиям:

• каждая внутренняя вершина имеет две или три дочерних вершины, и

• все листья дерева находятся на одном и том же уровне.

Двоично-троичным (2-3) справочником называется 2-3 дерево, все элементы данных которого хранятся в листьях и упорядочены слева направо. На рис. 10.2 показан пример. Внутренние вершины содержат метки, равные минимальным элементам тех или иных своих поддеревьев, в соответствии со следующими правилами:

• если внутренняя вершина имеет два поддерева, то она содержит минимальный элемент второго из них;

• если внутренняя вершина имеет три поддерева, то она содержит минимальные элементы второго и третьего поддеревьев.

Рис. 10.2. 2-3 справочник. Отмеченный путь показывает процесс поиска элемента 10.

При поиске элемента X в 2-3 справочнике мы начинаем с корня и двигаемся в направлении самого нижнего уровня, руководствуясь при этом метками внутренних вершин дерева. Пусть корень содержит метки M1 и M2, тогда

• если X < M1, то поиск продолжается в левом поддереве, иначе

• если X < M2, то поиск продолжается в среднем поддереве, иначе —

• в правом поддереве.

Если в корне находится только одна метка М, то переходим к левому поддереву при X < M и к правому поддереву — в противоположном случае. Продолжаем применять сформулированные выше правила, пока не окажемся на самом нижнем уровне дерева, где и выяснится, найден ли элемент X, или же поиск потерпел неудачу.

Так как все листья 2-3 дерева находятся на одном и том же уровне, 2-3 дерево идеально сбалансировано с точки зрения глубины составляющих его поддеревьев. Все пути от корня до листа, которые мы проходим при поиске, имеют одну и ту же длину порядка log n, где n — число элементов, хранящихся в дереве.

При добавлении нового элемента данных 2-3 дерево может расти не только в глубину, но и в ширину. Каждая внутренняя вершина, имеющая два поддерева, может приобрести новое поддерево, что приводит к росту вширь. Если же, с другой стороны, у вершины уже есть три поддерева, и она должна принять еще одно, то она расщепляется на две вершины, каждая из которых берет на себя по два из имеющихся четырех поддеревьев. Образовавшаяся при этом новая вершина передается вверх по дереву для присоединения к одной из выше расположенных вершин. Если же эта ситуация возникает на самом высоком уровне, то дерево вынуждено "вырасти" на один уровень вверх. Рис. 10.3 иллюстрирует описанный принцип.

Рис. 10.3. Вставление нового элемента в 2-3 справочник. Дерево растет сначала вширь, а затем уже вглубь.

Включение нового элемента в 2-3 справочник мы запрограммируем как отношение

доб23(Дер, X, НовДер)

где дерево НовДер получено введением элемента X в дерево Дер. Основную работу мы поручим двум дополнительным отношениям, которые мы назовем встав. Первое из них имеет три аргумента:

встав(Дер, X, НовДер).

Здесь НовДер — результат вставления элемента X в Дер. Деревья Дер и НовДер имеют одну и ту же глубину. Разумеется, не всегда возможно сохранить ту же глубину дерева. Поэтому существует еще одно отношение с пятью аргументами специально для этого случая:

встав(Дер, X, НДа, Mб, НДб).

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

Рис. 10.4. Объекты, показанные на рисунке, удовлетворяют отношению встав(Дер, 6, НДа, Мб, НДб).

2-3 деревья мы будем представлять в программе следующим образом:

• nil представляет пустое дерево;

• л(X) представляет дерево, состоящее из одной вершины — листа с элементом X;

• в2(Д1, М, Д2) представляет дерево с двумя поддеревьями Д1 и Д2; M — минимальный элемент из Д2;

• в3(Д1, M2, Д2, М3, Д3) представляет дерево с тремя поддеревьями Д1, Д2 и Д3; M2 — минимальный элемент из Д2; М3 — минимальный элемент из Д3; Д1, Д2 и Д3 — 2-3 деревья.

Между доб23 и встав существует следующая связь: если после вставления нового элемента дерево не "вырастает", то

доб23(Дер, X, НовДер):-

встав(Дер, X, НовДер).

Однако если после вставления элемента глубина дерева увеличивается, то встав порождает два поддерева Д1 и Д2, а затем составляет из них дерево большей глубины:

доб23(Дер, X, в2(Д1, М, Д2)):-

встав(Дер, X, Д1, М, Д2).

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

Случай а

встав(в2(Д1, M, Д2), X, в2(НД1, M, Д2)):-

больше(M, X), % M больше, чем X

встав(Д1, X, НД1).

Случай b

встав(в2(Д1, M, Д2), X, в3(НД1а, Мб, НД1б, M, Д2)):-

больше(M, X),

встав(Д1, X, НД1а, Мб, НД1б).

Случай с

встав(в3(Д1, M2, Д2, М3, Д3), X,

в2(НД1а, Мб, НД1б), M2, в2(Д2, М3, Д3)):-

больше(M2, X),

встав(Д1, X, НД1а, Мб, НД1б).

Рис. 10.5. Некоторые из случаев работы отношения встав. (a) встав(в2(Д1, М, Д2), X, в2(НД1, М, Д2)); (b) встав(в2(Д1, М, Д2), X, в3(НД1а, Мб, НД1б, М, Д2)); (c) встав(в3(Д1, M2, Д2, М3, Д3), X, в2(НД1а, Мб, НД1б), M2, в2(Д2, М3, Д3)).

% Вставление элемента в 2-3 справочник

доб23(Дер, X, Дер1):- % Вставить X в Дер, получить Дер1

встав(Дер, X, Дер1). % Дерево растет вширь

доб23(Дер, X, в2(Д1, M2, Д2)):-

встав(Дер, X, Д1, M2, Д2). % Дерево растет вглубь

доб23(nil, X, л(X)).

встав(л(А), X, л(А), X, л(X)):-

больше(X, А).

встав(л(А), X, л(X), А, л(А)):-

больше(А, X).

встав(в2(Д1, М, Д2), X, в2(НД1, М, Д2)):-

больше(М, X),

встав(Д1, X, НД1).

встав(в2(Д1, М, Д2), X, в3(НД1а, Мб, НД1б, М, Д2)):-

больше(М, X),

встав(Д1, X, НД1а, Мб, НД1б).

встав(в2(Д1, М, Д2), X, в2(Д1, М, НД2)):-

больше(X, М),

встав(Д2, X, НД2).

встав(в2(Д1, М, Д2), X, в3(Д1, М, НД2а, Мб, НД2б)):-

больше(X, М),

встав(Д2, X, НД2а, Мб, НД2б).

встав(в3(Д1, M2, Д2, М3, Д3), X,

в3(НД1, M2, Д2, М3, Д3):-

больше(M2, X),

встав(Д1, X, НД1).

встав(в3(Д1, M2, Д2, М3, Д3), X,

в2(НД1а, Мб, НД1б), M2, в2(Д2, М3, Д3)):-

больше(M2, X),

встав(Д1, X, НД1а, Мб, НД1б).

встав(в3(Д1, M2, Д2, М3, Д3), X,

в3(Д1, M2, НД2, М3, Д3)):-

больше(X, M2), больше(М3, X),

встав(Д2, X, НД2).

встав(в3(Д1, M2, Д2, М3, Д3), X,

в2(Д1, M2, НД2а), Мб, в2(НД2б, М3, Д3)):-

больше(X, M2), больше(М3, X),

встав(Д2, X, НД2а, Мб, НД2б).

встав(в3(Д1, M2, Д2, М3, Д3), X,

в3(Д1, M2, Д2, М3, НД3)):-

больше(X, М3),

встав(Д3, X, НД3).

встав(в3(Д1, M2, Д2, М3, Д3), X,

в2(Д1, M2, Д2), М3, в2(НД3а, Мб, НД3б)):-

больше(X, М3),

встав(Д3, X, НД3а, Мб, НД3б).

Рис. 10.6. Вставление элемента в 2-3 справочник. В этой программе предусмотрено, что попытка повторного вставления элемента терпит неудачу.

Программа для вставления нового элемента в 2-3 справочник показана полностью на рис. 10.6. На рис. 10.7 показана программа вывода на печать 2-3 деревьев.

Наша программа иногда выполняет лишние возвраты. Так, если встав с тремя аргументами терпит неудачу, то вызывается процедура встав с пятью аргументами, которая часть работы делает повторно. Можно устранить источник неэффективности, если, например, переопределить встав как

встав2(Дер, X, Деревья)

где Деревья — список, состоящий либо из одного, либо из трех аргументов:

Деревья = [ НовДер], если встав(Дер, X, НовДер)

Деревья = [ НДа, Мб, НДб],

если встав(Дер, X, НДа, Мб, НДб)

Теперь отношение доб23 можно переопределить так:

доб23(Д, X, Д1):-

встав(Д, X, Деревья),

соединить(Деревья, Д1).

Отношение соединить формирует одно дерево Д1 из деревьев, находящихся в списке Деревья.

% Отображение 2-3 справочников

отобр(Д):-

отобр(Д, 0).

отобр(nil, _).

отобр(л(А), H):-

tab(H), write(A), nl.

отобр(в2(Д1, М, Д2), H):-

H1 is H + 5,

отобр(Д2, H1),

tab(H), write(--), nl,

tab(H), write(M), nl,

tab(H), write(--), nl,

отобр(Д1, H1).

отобр(в3(Д1, M2, Д2, М3, Д3), H):-

H1 is H + 5

отобр(Д3, H1),

tab(H), write(--), nl,

tab(H), write(M3), nl,

отобр(Д2, H1),

tab(H), write(M2), nl,

tab(H), write(--), nl,

отобр(Д1, H1).

(a)

--

--

--

--

--

--

--

--

--

--

--

--

--

--

10.2. AVL-дерево: приближенно сбалансированное дерево

AVL-дерево — это дерево, обладающее следующими свойствами:

(1) Левое и правое поддеревья отличаются по глубине не более чем на 1.

(2) Оба поддерева являются AVL-деревьями.

Деревья, удовлетворяющие этому определению, могут быть слегка разбалансированными. Однако можно показать, что даже в худшем случае глубина AVL-дерева примерно пропорциональна log n, где n — число вершин дерева. Таким образом гарантируется логарифмический порядок производительности операций внутри, добавить и удалить.

Операции над AVL-деревом работают по существу так же, как и над двоичным справочником. В них только сделаны добавления, связанные с поддержанием приближенной сбалансированности дерева. Если после вставления или удаления дерево перестает быть приближенно сбалансированным, то специальные механизмы возвращают ему требуемую степень сбалансированности. Для того, чтобы эффективно реализовать этот механизм, нам придется сохранять некоторую дополнительную информацию относительно степени сбалансированности дерева. На самом деле, нам нужно знать только разность между глубинами поддеревьев, которая может принимать значения -1, 0 или +1. Тем не менее для простоты мы предпочтем сохранять сами величины глубин поддеревьев, а не разности между ними.

Мы определим отношение вставления элемента как

доб_avl(Дер, X, НовДер)

где оба дерева Дер и НовДер — это AVL-деревья, причем НовДер получено из Дер вставлением элемента X. AVL-деревья будем представлять как термы вида

д(Лев, А, Прав)/Глуб

где А — корень, Лев и Прав — поддеревья, а Глуб — глубина дерева. Пустое дерево изображается как nil/0. Теперь рассмотрим вставление элемента X в непустой AVL-справочник

Дер = д(L, A, R)/H

Рис. 10.8. Задача вставления элемента в AVL-справочник (a) AVL-дерево перед вставлением X, X > А; (b) AVL-дерево после вставления X в R; (с) составные части, из которых следует построить новое дерево.

Начнем со случая, когда X больше А. X необходимо вставить в R, поэтому имеем следующее отношение:

доб_аv1(R, X, д(R1, В, R2)/Hb)

На рис. 10.8 показаны составные части, из которых строится дерево НовДер:

L, А, R1, В, R2

Какова глубина деревьев L, R, R1 и R2? L и R могут отличаться по глубине не более, чем на 1. На рис. 10.8 видно, какую глубину могут иметь R1 и R2. Поскольку в R был добавлен только один элемент X, только одно из поддеревьев R1, R2 может иметь глубину h+1.

Рис. 10.9. Три правила построения нового AVL-дepевa.

В случае, когда X меньше, чем А, имеем аналогичную ситуацию, причем левое и правое поддеревья меняются местами. Таким образом, в любом случае мы должны построить дерево НовДер, используя три дерева (назовем их Дер1, Дер2 и Дер3) и два отдельных элемента А и В. Теперь рассмотрим вопрос: как соединить между собой эти пять составных частей, чтобы дерево НовДер было AVL-справочником? Ясно, что они должны располагаться внутри НовДер в следующем порядке (слева направо):

Дер1, А, Дер2, В, Дер3

Рассмотрим три случая:

(1) Среднее дерево Дер2 глубже остальных двух деревьев.

(2) Дер1 имеет глубину не меньше, чем Дер2 и Дер3.

(3) Дер3 имеет глубину не меньше, чем Дер2 и Дер1.

На рис. 10.9 видно, как можно построить дерево НовДер в каждом из этих трех случаев. Например, в случае 1 среднее дерево Дер2 следует разбить на два части, а затем включить их в состав НовДер. Три правила, показанные на pис.10.9, нетрудно запасать на Прологе в виде отношения

соединить(Дер, А, Дер2, В, Дер3, НовДер)

Последний аргумент НовДер — это AVL-дерево, построенное из пяти составных частей, пяти первых аргументов. Правило 1, например, принимает вид:

соединить(Д1/Н1, А, д(Д21, В, Д22)/Н2, С, Д3/Н3,

% Пять частей

д(д(Д1/Н1, А, Д21)/На, В, д(Д22, С, Д3/Н3)/Нс)/Нb):-

% Результат

H2 > H1, H2 > Н3, % Среднее дерево глубже остальных

На is Н1 + 1, % Глубина левого поддерева

Нс is Н3 + 1, % Глубина правого поддерева

Hb is На + 1, % Глубина всего дерева

Программа доб_аvl, вычисляющая также глубину дерева и его поддеревьев, показана полностью на рис. 10.10.