Лекции по структурам и алгоритмам обработки данных (СиАОД). Первый семестр 9

Procedure Delete(X: string; var P: ref);

{ память освобождается, описатель var - обязателен }

Var

Q: ref;

Procedure Del(var R: ref); { сначала R=Q^.Left }

{ замещение Q^ самым правым элементом левого поддерева }

Begin

if R^.Right<>Nil then Del(R^.Right)

else

begin { R-самая правая вершина левого поддерева }

Q^.key:=R^.Key;

Q^.Count:=R^.Count;

Q:=R;

R:=R^.Left; { подтянули левое поддерево }

Dispose(Q)

end

End;

Begin

if P=Nil then

WriteLn('Слова нет в дереве !')

else

if X<P^.Key then Delete(X, P^.Left)

else

if X>P^.Key then Delete(X, P^.Right)

else { X=P^.Key - нашли слово }

if P^.Count>1 then P^.Count:=P^.Count-1

else

begin { полное удаление слова }

Q:=P; { Q – указатель на удаляемую вершину }

if Q^.Right=Nil then

begin

P:=Q^.Left; { подтянули левое поддерево }

Dispose(Q)

{ работает, благодаря рекурсии: меняя P, меняется }

{ P^.Left или P^.Right у отцовской вершины }

end

else if Q^.Left=Nil then

begin

P:=Q^.Right; { подтянули правое поддерево }

Dispose(Q)

end

else Del(Q^.Left); { замена }

end

End;

Procedure PrintTree(W: ref; L: integer);

{ W-корень, L-число точек, показывающее уровень дерева }

Var

I: integer;

Begin

if W<>Nil then

with W^ do

begin

PrintTree(Left, L+1);

For I:=1 to L do

Write('.');

WriteLn(Key, ' ', Count);

PrintTree(Right, L+1)

end

End;

Begin

ClrScr;

Rab:=' ';

Root:=Nil;

B:=True;

While B do

begin

Write('Укажите слово для ввода (к-признак конца) ');

Readln(Rab);

if Rab<>'к' then

begin

Search(Rab, Root);

PrintTree(Root, 0)

end

else B:=False

end;

B:=True;

While B do

begin

Write('Укажите слово для удаления (к-признак конца) ');

Readln(Rab);

if Rab<>'к' then

begin

Delete(Rab, Root);

PrintTree(Root, 0)

end

else B:=False

end;

End.

5.3. Балансировка деревьев поиска

Трудоемкость нахождения заданного элемента в дереве поиска зависит от структуры этого дерева. Например, если ни у одной вершины нет левого сына, то дерево вырождается в линейный список, и поиск сводится к последовательному перебору вершин. В связи с этим появляется необходимость в поддержке определенной сбалансированности дерева поиска.

По определению Вирта, дерево поиска является идеально сбалансированным, если для каждой его вершины количество вершин в левом и правом поддеревьях отличается не более, чем на 1.

В процессе корректировки идеальная балансировка дерева часто нарушается. Имеется более мягкое определение: дерево сбалансированно, если высота (глубина, количество уровней) левого и правого поддеревьев любой вершины отличается не более, чем на 1. Сбалансированные деревья поиска называют АВЛ-деревьями по именам авторов Адельсон-Вельского и Ландиса. В АВЛ-деревьях необходимость в операциях балансировки появляется реже, а сами эти операции достаточно просты.

Восстановление баланса в АВЛ-деревьях достигается путем преобразований, называемых поворотами. Имеются четыре типа поворотов: LL-поворот, RR-поворот, LR-поворот и RL-поворот. Первые два из них считаются одинарными, а последние два – двойными. Это связано с количеством операций, необходимых для восстановления баланса.

Мнемонические обозначения типов поворота связаны с ситуациями нарушения баланса, возникающими в некоторой вершине в результате включения новой вершины. Если оказывается, что в этой вершине высота левого поддерева больше на 2 уровня высоты правого поддерева, то первой буквой в мнемоническом обозначении поворота будет L. Если для левого сына этой вершины высота левого поддерева остается большей, то потребуется LL-поворот. Аналогично определяются обозначения других типов поворотов.

Рассмотрим следующие примеры. Пусть имеется АВЛ-дерево (......) и включается элемент с ключом 4 или 7. В результате LL-поворота получится дерево (.....)

или (.....)

Если же в исходное дерево включается элемент с ключом 12 или 17, то LR-поворот приведет к дереву (.....)

или (.....)

Пусть дерево описано в виде динамической структуры с указателями Left и Right на левого и правого сыновей для каждой вершины, а указатель P показывает на вершину, в которой возникло нарушение баланса. Тогда LL-поворот выражается тремя операторами

P1:=P^.Left;

P^.Left:=P1^.Right;

P1^.Right:=P;

а LR-поворот шестью операторами

P1:=P^.Left; P2:=P1^.Right;

P1^.Right:= P2^.Left; P2^.Left:=P1;

P^.Left:=P2^.Right; P2^.Right:=P;

Рассмотрим примеры более сложных деревьев. Пусть имеется дерево (.....)

При включении элемента с ключом 1 или 3 потребуется LL-поворот в вершине с ключом 20, который в соответствии с указанными операторами приведет к дереву (....)

или (....)

При включении же элемента с ключом 11 или 14 потребуется LR-поворот, приводящий к дереву (.....)

или

Исключение из АВЛ-дерева несколько сложнее. Сначала исключение выполняется, как из обычного дерева поиска. Затем анализируется, есть ли нарушения баланса по направлению к корню дерева. Отличие от включения состоит в том, что балансировка может потребоваться более одного раза.

Рассмотрим в качестве примера следующее дерево. (.....)

Это дерево Фибоначчи: АВЛ-дерево заданной высоты с минимальным числом вершин. При удалении вершины с ключом 35 возникает нарушение баланса в вершине с ключом 30. LL-поворот приводит к новому нарушению баланса в корне дерева. В результате еще одного LL-поворота получается дерево (.....)

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

баланс в корне дерева можно восстановить как LL-поворотом, так и LR-поворотом.

5.4. Б-деревья

До сих пор молчаливо предполагалось, что деревья поиска находятся в оперативной памяти. При увеличении их объема это становится невозможным. Конечно, можно хранить дерево и в файле с прямым доступом. В сбалансированном дереве смещение на один уровень вниз при поиске данных сокращает пространство поиска примерно вдвое, поэтому среднее число шагов поиска пропорционально величине log₂N, где N – количество вершин дерева. Если, например, N=10⁶, то эта величина близка к 20, и нерационально столько раз позиционировать файл. С другой стороны, при прямом доступе позиционирование является самой трудоемкой операцией, а чтение одного или нескольких блоков информации мало отличаются по времени. Эти соображения приводят к потребности блокирования элементов в страницы, что порождает множество вопросов.

Эту проблему удалось решить путем применения Б-деревьев - сильно ветвящихся деревьев поиска, вершинами которых являются страницы элементов.

Б-деревом порядка n называется сильно ветвящееся дерево со следующими свойствами.

1. Каждая страница , кроме корня, содержит не менее n элементов.

2. Каждая страница содержит не более 2n элементов.

3. Если страница не лист и имеет m элементов, то у нее ровно m+1 сын.

4. Если элементы нелистовой страницы с ключами A₁, A₂,…, A_m упорядочены по возрастанию ключей, то поддерево с корнем в первом сыне содержит элементы с ключами, меньшими A₁, поддерево с корнем во втором сыне - с ключами, большими A₁, но меньшими A₂ и т. д.

5. Все листовые страницы находятся на одном уровне.

Ниже приведен пример Б-дерева порядка 2. Этот порядок является тестовым, то есть иллюстрирует все принципы работы с Б-деревьями, позволяя, тем не менее, просматривать результаты вручную. В целях наглядности выбраны числовые значения ключей.(.....)

Поиск элемента с заданным ключом проводится по направлению от корня к листьям Б-дерева на основании свойства 4. Число уровней Б-дерева оценивается величиной log_nN, где N – количество элементов дерева. Для рассмотренного случая N=10⁶ эта величина равна 3, то есть по сравнению с бинарным деревом поиска для нахождения элемента требуется перебирать существенно меньшее число вершин.

Включение нового элемента в Б-дерево выполняется следующим образом. Сначала производится поиск листовой страницы, где должен располагаться новый элемент. Если в этой странице менее 2n элементов, то новый элемент добавляется в страницу без изменения структуры дерева. Если же в ней оказывается 2n+1 элемент, то средний по значению ключа элемент отправляется в отцовскую страницу, а элементы, меньшие и большие среднего элемента по значениям ключа, образуют две новые страницы по n элементов. Если в отцовской странице тоже происходит переполнение, то процесс продолжается вверх по дереву. Вытесненный элемент из корневой страницы образует новый корень, увеличивая число уровней дерева. Следовательно, Б-дерево растет снизу вверх.

Рассмотрим следующий пример. Требуется вставить элемент с ключами 7 и 75 в следующее Б-дерево.(....)

Элемент с ключом 7 добавляется в крайнюю левую страницу. На крайней правой листовой странице добавление второго элемента вызовет переполнение, и элемент с ключом 68 будет вытеснен в корень. В корне тоже окажется более 4 элементов, средний из которых образует новый корень. В результате получится дерево (.....)

Начальная организация Б-дерева производится путем последовательного включения элементов. Для Б-дерева второго порядка второй уровень появляется после включения пятого элемента.

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

Если число объединенных элементов окажется не менее 2n+1, то средний элемент располагается в отцовской странице, а элементы, меньшие и большие среднего элемента по значениям ключей, образуют 2 страницы.

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

В качестве примера рассмотрим последнее Б-дерево, полученное после вставки элементов с ключами 7 и 75. При удалении элемента с ключом 36 объединяются элементы с ключами 2, 4, 7, 30, 34. Элемент с ключом 7 отправляется в отцовскую страницу вместо бывшего там элемента с ключом 30, а две измененные листовые страницы будут содержать элементы с ключами 2,4 и 30,34.

Удалим в полученном дереве элемент с ключом 75. Сейчас новую страницу образуют элементы с ключами 65,67,68,69, а в отцовской странице останется единственный элемент с ключом 60, что недопустимо. Этот элемент объединяется с элементами соседней страницы и к ним добавляется элемент с ключом 50 из корня, который остается пустым. После удаления корня дерево примет вид, имевший до вставки элементов с ключами 7 и 75. Число уровней дерева уменьшается с трех до двух.

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

Б-деревья широко применяются для индексации данных. Индексация здесь понимается в более широком смысле как аппарат, обеспечивающий быстрый поиск данных. Почти все современные системы управления базами данных используют идексацию на основе Б-деревьев. Рассмотрим на принципиальном уровне способ индексации с помощью Б-деревьев.

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