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

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

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

Type

person =Record

Name: string;

Sibling: ^person;

offspring: ^person

End;

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

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

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

Уменьшение количества обращений к диску – а теперь обращение к каждой странице предполагает обращение к диску – может быть значительным. Предположим, что мы решили помещать на странице 100 узлов (это разумная цифра), тогда дерево поиска, содержащее миллион элементов, потребует в среднем только обращений к страницам вместо 20. Но, конечно, если дерево растет «случайным образом», то наихудший случай может потребовать даже 10⁴ обращений! Понятно, что в случае сильно ветвящихся деревьев почти обязательна схема управления их ростом.

B-деревья

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

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

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

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

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

Сформулируем описание страницы (рис. 7.9).

Рис. 7.9. Страница В-дерева

const

nn = 2*n;

type

item = record

key: integer;

p: ref;

………………..

end;

ref = ^page;

page = record

m: index;

p0: ref;

e: array[1..nn] of item;

end;

На рис. 7.10 показано Б-дерево порядка 2 с тремя уровнями. Все страницы содержат 2, 3 или 4 элемента. Исключением является корень, которому разрешается содержать только один элемент. Все листья находятся на уровне 3. Ключи расположены в возрастающем порядке слева направо, если спроектировать дерево на один уровень, вставляя потомков между ключами, находящимися на странице-предке. Такое расположение представляет естественное развитие принципа организации бинарных деревьев поиска и определяет метод поиска элемента с заданным ключом. Рассмотрим страницу, имеющую вид, как показано на рис. 7.9, и пусть задан аргумент поиска х. Предполагая, что страница считана в оперативную память, мы можем использовать известные методы поиска среди ключей k₁, ..., k_m. Если т достаточно велико, можно применить бинарный поиск, если оно сравнительно небольшое, подойдет простой последовательный поиск. (Заметим, что время, требующееся для поиска в оперативной памяти, вероятно, пренебрежимо мало по сравнению со временем, которое занимает считывание страницы с внешнего устройства.)

Рис. 7.10. Б-дерево порядка 2 с тремя уровнями

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

1. k_i<x<k_i+1 для 1£i<m. Мы продолжаем поиск на странице p_i­.

2. k_m<х. Поиск продолжается на странице p_m­.

3. x<k₁. Поиск продолжается на странице p₀­.

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

К удивлению, включение в Б-дерево также выполняется сравнительно просто. Если элемент вставляется в страницу, содержащую т<2п элементов, то процесс включения ограничивается этой страницей. Лишь включение в уже заполненную страницу влияет на структуру дерева и может вызвать появление новых страниц. Чтобы понять, что происходит в этом случае, рассмотрим рис. 7.11, на котором показано включение ключа 22 в Б-дерево порядка 2. Оно состоит из следующих этапов:

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

2. Страница С расщепляется на две страницы, т. е. размещается новая страница D.

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

Рис. 7.11. Включение ключа 22 в Б-дерево порядка 2

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

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

20; 40 10 30 15; 35 7 26 18 22; 5; 42 13 46 27 8 32; 38, 24 45 25.

Точки с запятой указывают моменты размещения новых страниц.

Рис. 7.12. Рост Б-дерева

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

1. Элемент, который нужно удалить, находится на странице-листе; тогда алгоритм удаления прост и очевиден.

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

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

В любом случае после уменьшения размера нужно проверить число элементов т на уменьшенной странице, так как, если т<n, будет нарушено основное свойство Б-деревьев. Единственный выход – одолжить или отобрать элемент с одной из соседних страниц, а поскольку это требует вызова страницы Q в оперативную память – относительно дорогостоящей операции, – то мы попытаемся наилучшим образом воспользоваться этой нежелательной ситуацией и заберем сразу больше одного элемента. Обычно элементы Р и Q поровну распределяются на обе страницы. Это называется балансировкой.

Разумеется, может оказаться, что с Q нельзя забирать элементы, так как она тоже уже достигла своего минимального размера n. В этом случае общее число элементов на Р и Q равно 2n-1 и мы можем слить эти две страницы в одну, добавив средний элемент со страницы-предка Р и Q, а затем можем полностью располагать страницей Q. Это – процесс, в точности обратный расщеплению страниц.

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

На рис. 7.13 показан постепенный распад Б-дерева с рис. 7.12 при последовательном удалении ключей:

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

Точки с запятой снова указывают места «скачков», т. е. освобождения страниц.

Рис. 7.13. Распад Б-дерева