7.4 Сильно ветвящиеся деревья

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

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

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

Иван
й
i
Ал-др			Мария			Вл-р
ш						•
•						•
			Павел
			•
			t

Иван
•
	1
Конст-н			Дмитр.
			t
Георгий			Наталья
			•
t			t

Инна

Рис. 23 Сильно ветвящееся дерево

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

Однако имеется практически очень важная область применения сильно ветвящихся деревьев, которая представляет общий интерес.

Это – формирование и использование крупномасштабных деревьев поиска, в которых необходимы вклю­чения и удаления, но для которых оперативная память недостаточно велика или слишком дорога, чтобы ис­пользовать её для долговременного хранения.

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

Если множество данных, состоящее из 1 млн. элементов, хранится в виде бинарного дерева, то для поиска элемента потребуется в среднем log₂10⁶ = 20 шагов поиска. Поэтому желательна такая организация памяти, которая требует меньше числа обращений.

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

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

Рис. 24 Бинарное дерево, разделенное на страницы

Таким образом можно существенно уменьшить число обращений, увеличив количество узлов на странице. Предположим, мы разместили на одной странице 100 узлов (это разумная цифра). Тогда дерево поиска, содер­жащее 1 млн. узлов, потребует в среднем log₁₀₀10⁶ = 3 обращений к страницам вместо 20.

При этом нужно иметь в виду, что в случае сильно ветвящихся деревьев необходима схема управления их ростом, т.к. если дерево растет случайным образом, то наихудший случай может потребовать даже 10⁴ обраще­ний.

Б-деревья

Критерии управления ростом могут быть различными. Очевидно, нужно сразу отвергнуть идеальную сба­лансированность, т.к. она требует слишком больших затрат на балансировку.

Более мягкий критерий был сформулирован Р. Бэйером: каждая страница (кроме одной) содержит от n до 2n узлов при заданном постоянном n. N называется порядком дерева. Следовательно в дереве с N элементами, наихудший случай потребует log_nN обращений к страницам при максимальном размере строк - 2n узлов. При этом коэффициент использования памяти составляет не менее 50%, т.к. страницы заполнены хотя бы наполо­вину. При всех этих преимуществах данная схема требует сравнительно простых алгоритмов поиска, включе­ния и удаления.

Рассматриваемые страницы данных называются Б-деревьями.

Свойства Б-деревьев:

• каждая страница содержит не более 2n элементов (ключей);

• каждая страница, кроме корневой, содержит не менее n элементов;

• каждая страница является либо листом, т.е. не имеет потомков, либо имеет m+1 потомков, где m - чис­ло находящихся на ней ключей;

• все листья находятся на одном и том же уровне. Пример Б-дерева, порядка 2 с 3-мя уровнями:

25

30 40

_Г

10 20 П

5 7 8 13 15 18 22 24 26 27 32 35 38 42 45 46

Все страницы содержат 2, 3 или 4 элемента, кроме корня, который может содержать только 1 элемент. Все листья – на 3-ем уровне. Ключи расположены в возрастающем порядке слева направо, если представить дерево как одноуровневое, вставляя потомков между ключами, находящимися на странице - предке. При таком распо­ложении Б-дерево представляет собой естественное развитие принципа организации бинарных деревьев поис­ка. Отсюда естественно вытекает метод поиска элемента с заданным ключом. Рассмотрим страницу, имеющую вид:

1
P0 Kl PI K2 РЗ КЗ . .	. . PM-1 KM PM

_{1 1}

т.е. содержащую m ключей.

Пусть задан аргумент поиска Х. Предполагая, что страница считана в оперативную память, мы можем ис­пользовать известные методы поиска среди ключей к_ь ..., к_м. (При большом m - бинарный поиск, при неболь­шом - последовательный). При этом время, затрачиваемое на поиск в оперативной памяти, пренебрежимо мало по сравнению со временем, затрачиваемым на считывание страницы в оперативную память.

Если поиск неудачен, то возможны следующие ситуации:

1. к, < х < к₁₊₁ для 1 <= i < m. Продолжаем поиск на странице р,^Л;

2. х > k_m. Продолжаем поиск на странице р_т^Л;

3) x < k1. Продолжаем поиск на странице p₀^.

Если в каком-то случае ссылка равна nil, то элемента с ключом x нет в дереве и поиск заканчивается.

Включение в Б-дерево также выполняется просто. Если элемент вставляется в страницу, содержащую m < 2n элементов, то процесс включения ограничивается только этой страницей. Если страница уже заполнена, то только в этом случае структура дерева меняется и могут появиться новые страницы. Рассмотрим дерево поряд­ка 2:

А 20

_i

7 10 15 18 26 30 35 40

ВС

Пусть нужно включить в дерево ключ 22. Процесс включения разобьется на следующие этапы:

• выясняется, что ключ 22 отсутствует. Включение в страницу С невозможно, т.е. она уже заполнена;

• страница С расщепляется на две страницы: С и D;

• количество m+1 ключей распределяются поровну между С и D, а средний ключ перемещается на один уровень вверх, на страницу-предка А. Получим:

А 20 30

7 10 15 18 22 26 35 40

ВС D

При этом полученное сохраняет все свойства Б-деревьев. В частности, при расщеплении получаем страницы, содержащие ровно n элементов. Разумеется, включение элемента в страницу-предка может вызвать переполне­ние этой страницы. Произойдет распространение расщепления, которое может дойти до корня. В этом случае высота дерева увеличится. Можно сказать, что Б-дерево растет от листьев к корню.

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

Вначале опишем страницу, располагая элементы на ней в форме массива: TYPE PAGE = RECORD

M: INDEX; P0: REF;

E: ARRAY[1..NN] OF ITEM END; где

CONST NN = 2*N; TYPE REF = ^PAGE;

INDEX = 0..NN; ITEM = RECORD

KEY: INTEGER; P: REF;

COUNT: INTEGER END; Компонента COUNT заменяет всевозможную прочую информацию, не играющую никакой роли в процес­се поиска. Каждая страница содержит пространство для 2n элементов. Поле m указывает, сколько элементов размещено в действительности.

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

Схематично процедура поиска с включением выглядит следующим образом: PROCEDURE SEARCH(X: INTEGER; A: REF;

VAR H: BOOLEAN; VAR U: ITEM); BEGIN IF A = NIL THEN BEGIN {Х нет в дереве}

Присвоение значения х элементу U и установка h в true,

указывая, что элемент U передается вверх по дереву END ELSE

WITH А^Л DO BEGIN {поиск х на странице а^л} двоичный поиск в массиве; IF найдено

THEN увеличение счетчика появления элемента ELSE BEGIN

search(X, потомок, Н, U); IF Н THEN {передача вверх элемента U} IF (число элементов на А^Л) < 2N THEN включение в страницу А^Л и установка

Н в false ELSE расщепление страницы и передача вверх среднего элемента END END END;

Здесь булевская переменная h сигнализирует о том, что второй выходной параметр U является передавае­мым вверх элементом (при h=trae), который направляется на страницу включения.

Особенно следует предусмотреть ситуацию, когда происходит расщепление страницы-корня. В этом слу­чае следует создать новую корневую страницу и включить в неё один элемент, переданный через параметр U. Таким образом новая страница-корень будет содержать только один элемент. Использование оператора WITH означает не только то, что внутри оператора идентификаторы полей страницы автоматически относятся к стра­нице А^Л. Если реально страницы размещаются во внешней памяти, оператор WITH дополнительно означает передачу указанной страницы в оперативную память. Поэтому каждое обращение к SEARCH предполагает размещение в памяти одной страницы. Всего же необходимо k = log_nN рекурсивных обращений. Здесь N - ко­личество элементов дерева.

Следовательно, мы должны иметь возможность разместить в памяти К страниц. Это налагает ограничения на размер страницы 2N. Но количество размещаемых страниц может быть больше чем К, т.к. включение может вызвать их расщепление. Корневую же страницу лучше постоянно хранить в оперативной памяти, т.к. каждый поиск всегда начинается с корня.

Проиллюстрируем процесс построения дерева со следующей последовательностью вставляемых ключей (рис. 25):

20; 40 10 30 15;

35 7 26 18 22; 5;

42 13 46 27 8 32; 38 24 45 25;

а)

б)

; - момент размещения новой страницы.

ж

I 20 I

10 1530 40

в)

г)

20 30

_Г

7 10 15 1822 26 35 40 [То 20 30

5 7 15 1822 2б1 35 40

д)

е)

5 7 813 15~Ti22 2426 2732 35 38 42 45 46

Рис. 25 Рост Б-дерева порядка два

Удаление элементов из Б-дерева просто в общих чертах, но сложно в деталях. Здесь можно выделить два случая.

Удаляемый элемент находится на странице-листе, и тогда алгоритм удаления очевиден и прост.

Элемент не на листе. Тогда его нужно заменить на один из двух лексикографически смежных элемента, которые находятся на страницах-листьях и которые легко удалить.

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

Как в первом, так и во втором случае после удаления элемента мы должны проверить число элементов m на уменьшенной страницы, т.к. при m < п основное свойство Б-деревьев нарушается.

Если это произошло, нам придется отобрать элемент у одной из соседних страниц Q. Поскольку это тре­бует вызова страницы Q в оперативную память и поэтому является достаточно дорогой операцией, заберем с Q сразу побольше элементов. Обычно элементы страниц Р и Q распределяются поровну на обе страницы (это называется балансировкой).

Но может так оказаться, что с Q нельзя забирать элементы, т.к. она уже достигла своего минимального размера п. В этом случае общее число элементов на страницах Р и Q равно 2п-1 и мы можем слить эти страни­цы в одну, добавив один элемент (средний) со страницы-предка. Процесс является обратным по отношению к процессу расщепления страниц (на нашем примере можно наблюдать, пытаясь удалить из полученного дерева ключ 22) (рис. 26).

I 20 301 7 10 15 18 22 26 35 40

I 20 1

7 10 15 18 26 30 35 4о

Рис. 26 Удаление ключа 22 в Б-дереве Но удаление среднего ключа на странице-предке может в свою очередь уменьшить её размер ниже допус­тимой границы п. И тогда потребуется дальнейшая балансировка или слияние уже на более высоком уровне. Этот процесс может распространиться на всем пути к корню. Если корень уменьшается до размера 0, он удаля­ется и высота дерева уменьшается.

10 20 1 8 13 15 18 2

а)

а₁)

10 18 30 40

8 13 15 20 22 26 27 32 35 38 4

5 7 813 15 18 2026 2732 35 38 42 46

б)

5 7 8 13 15 18 20 26 30 40 42 46

в) в₁)

10 22 , | 5 7 15 18 20 26 3

15 18 2026 30 35 40

15 22

_^ZL

г) г₁)

7 10

18 20 26 30 35 40

20

д)

7 10 15 18 26 30 35 40

е)

10 20 30 40

Рис. 27 Распад Б-дерева порядка два

Рассмотрим процесс распада дерева на примере (рис. 27). Пусть имеется исходное дерево (рис. 27 а)) по­рядка два, из которого последовательно нужно удалить ключи: 25, 45, 24; 38, 32; 8, 27, 46, 13, 42; 5, 22; 18, 26, 7, 35, 15; (; – скачки, т.е. освобождение страниц)

Самостоятельно: составить процедуры для:

1. поиска в Б-дереве;

2. включения в Б-дерево;

3. удаление из Б-дерева.

Контрольные вопросы

1. Древовидные структуры данных. Основные понятия.

2. Представление деревьев в ЭВМ.

3. Процедура формирования дерева.

4. Обход бинарного дерева.

5. Поиск в бинарном дереве.

6. Включение нового узла в дерево.

7. Удаление узла из дерева.

8. Сильно ветвящиеся деревья.

9. Б-деревья.

10. Свойства Б-деревьев.

11. Поиск в Б-дереве.

12. Включение в Б-дерево.

13. Удаление из Б-дерева.