Virt N. Algoritmy struktury dannyh = programmy (ru)(T)(410s) (522393), страница 47
Текст из файла (страница 47)
В этом случае намного правильнее расположить потомство в виде линейного списка со ссылкой в записи родителей на самого младшего (или самого старшего) отпрыска. Возможное описание типа для такого случая показано в (4.80), а возможная структура данных приведена на рис. 4.43. 2урврегвоп = хесогй пате: а(уа; в(Ийц: 1 реглан; а5зрг(пй: (регеоп евй (4.80) *) О бинарности скорее свидетельствует наличие двух ссылок.
— Прим. лед. Мы замечаем, что при повороте этого рисунка на 45' он будет выглядеть как идеальное бинарное дерево*). Но это неверная точка зрения, поскольку функционально этн две ссылки имеют совершенно различное значение. Обычно нельзя обращаться с братом, как с сыном, поэтому так не следует поступать даже при описании данных. Этот пример легко можно было бы распространить н на более сложные структуры данных, включив еще какие-то компоненты в запись для каждого лица; таким образом можно было бы изображать другие родственные связи. Одна нз таких связей, которую нельзя в принципе вынести из отношений братства н потомства,— это связь между мужем и женой илн обратное отношение отцовства и материнства.
Такая структура быстро разрастается в сложный, реляционный «банк данных», который может отображаться в несколько деревьев. Алгоритмы, работающие с такими структурами, тесно связаны с их описаниями; поэтому яе имеет смысла определять для нпх какие- либо обьцие правила или методы работы. Однако имеется практически очень важная область применения сильно ветвящихся деревьев, которая представляет 281 4.6. Сильно ветвящиеся деревья общий интерес, Это в формирование и использование крупномасштабных деревьев поиска, в которых необходимы н включения, и удаления, но для которых оперативная память недостаточно велика или слишком дорогостояша, чтобы исполь.
зовать ее для долговременного хранения. Предположим, что узлы дерева должны хрангсться на внешнем запоминающем устройстве, таком, как диск. Введенные в этой главе динамические структуры данных особенно подходят и для хранения на внешних запоминающих устройствах. Принципиально новое — это лишь то, что ссылки представляют собой адреса па диске, а не адреса оперативной Рие. 4.44. Бинарное дерево, разделенное на «страницы», памяти. Если множество данных, состоящее, например, пз миллиона элементов, хранится в виде бннарнога дереза, го для поиска элемента потребуется в среднем около 1опа!О'ы ж 20 шагов поиска. Поскольку теперь каждый шаг включает обращение к диску (с собственным латентным временем), будет весьма желательна организация памяти, требуницая меньше обращений.
Сильно ветвянтееся дерево является идеальным решением этой проблемы. Если происходит обращение к некоторому одиночному элементу, расположенному на внешнем устройстве, то без больших дополнительных затрат можно обращаться также к целой группе элементов. Отсюда следует, что дерево нужно разделить иа поддсрсвья, считая, что все эти поддеревья одновременно полностью доступны. Мы будем называть такие поддерсвья странис4алссс. На рис.
4.44 показано бинарное дерево, разделенное на страницы, состоящие нз 7 узлов каждая. Уменьшение количества обращений к диску — а теперь обращение к каждой странице предполагает обращение к диску — -может быть значительным. Предположим, что мы решили помещать па странице 100 узлов (это разумная цифра), тогда дерево поиска, содержащее миллион элементов, 282 4. Пинамиаескае информаяионные структуры потребует в среднем только !оома!Ос = 3 обращеиий к страипцам вместо 20.
Но конечно, если дерево растет аслучайиым образом», то наихудший случай может потребовать даже 10' обращений! Понятно, что в случае сильио ветвящихся деревьев почти обязательна схема управлеиия их ростом. 4.$.4. Б-деревья При поиске критерия управляемого роста нужно сразу отвергнуть идеальную сбалансированность, так как оиа требует слишком больших затрат иа балаисировку. Очевидно, что правила необходимо несколько смягчить, Очень разумный критерий был сформулирован Р. Бэйером 14.21: каждан страница (кроме одной) содержит от л до 2л узлов при заданном постоянном и, Следовательно, в дереве с й! элемеитами и максимальным размером страницы 2л узлов наихудший случай потребует !оК„У обращений к страницам, а обращения к страницам составляют, как известно, основную часть затрат иа поиск. Кроме того, важный коэффициент использоваиия памяти составляет ие менее 50 о)а, так как страиицы заполнены хотя бы наполовину.
При всех этих преимуществах данная схема требует сравнительно простых алгоритмов поиска, включения и удалеиия. В дальнейшем мы подробио пх изучим. Рассматриваемые структуры данных называются Б-деревьями и им:ют следующие свойства (л называется порядком Б-дерева): 1. Каждая страница содержит ие более 2л элемеитов (ключей).
2, Каждая страница, кроме кориевой, содержит ие менее и элементов. 3. Каждая стравпца является либо листом, т. е. ие имеет потомков, либо имеет т+ 1 потомков, где ьч — число иаходящихся иа ией ключей. 4. Все листья иаходятся иа одиом и том же уровне. На рис. 4.45 показано Б-дерево порядка 2 с 3 уровиями, Все страницы содержат 2, 3 или 4 элемевта. Исключением является корень, которому разрешается содержать только одни элемент. Все листья находятся иа уровне 3. Ключи расположеиы в возрастающем порядке слева направо, если спроектировать дерево иа один уровень, вставляя потомков между ключами, иаходящимися иа странице-предке.
Такое расположение представляет естественное развитие принципа оргаийзации бинарных деревьев поиска и определяет метод поиска элемента с задаииым клюям. Рассмотрим страницу, имеющую вид, как показано иа рис. 4.4б, и пусть задав аргумент в'.а, Сально ветвящиеся деревья поиска л. Предполагая, что страшша считана в оперативную вамять, мы можем использовать известные методы поиска среди ключей яь ..., й .
Если лт достаточно велико, можно применить бинарный поиск, если оно сравнительно небольшое, подойдет простой последгвательный поиск. (Заметим, что Ряс. 4ЛЬ. Б-дерево яорядяа время, требующееся для поиска в оперативной памяти, вероятно, пренебрежимо мало по сравнению со временем, которое занимает сштыванпе страницы с внешнего устройства Ра "~ Р~ "я Ря .. Р, 1 Ь„,Р,„ Рис, 4.46, Страница Б-дерева, одертвашая и ял~ояетс в оперативную память!. Если поиск неудачен, мы имеем одну из следующих ситуаций: !. Фа < х < Йсы для ! <1( гп.
Мы продолжаем поиск на странице р,у. 2. Ф„( х. Поиск продолжается на странице р„у. 3. г Аь Поиск продолжается на странице ря1. Если в каком-то случае ссылка равна и!1, т, е. нет соответствующего потомка, то элемента с ключом х нет во всем дереве н поиск заканчивается. К уднвленшо, включение в Б-дерево также выполняется сравнительно просто. Если элемент вставляется в страницу, содержащую ьч < 2н элементов, то процесс включения ограничивается этой страницей. Лишь включение в уже заполненную страницу влияет на структуру дерева н может вызвать появленне новых страниц. Чтобы понять, что происходит в этом случае, рассмотрим рнс.
4.47, на котором показано 4. Динамические ин4гормационние етрукгури включение ключа 22 в Б-дерево порядка 2. Оно состоит из следующих этапов: 1. Выясняется, что ключ 22 отсутствует. Включение в стра- ницу С невозможно„так как С' уже заполнена. 2. Страница С расщепляется па две страницы, т. е. разме- н;ается новая страница О. 3. Колггчество из+1 ключей поровну распределяется на С и В, а средний ключ перемещается на один уровень вверх, на страницу-предка А, Эта весьма элегантная схема сохраняет все основные свойства Б-деревьев, В частности, при расщеплении получаются С В С 47 Рис.
4.47. Включение ключа 22 и В-дереио. страницы, содержащие ровно п элементов. Разумеется, включение элемента в страницу-предка может вновь вызвать переполнение этой страницы, что приведет к распространению расгг4елления. В экстремальном случае оно могкет распространиться до корня. Это и есть единственный случай увеличения высоты Б-дерева, Следовательно, Б-дерево растет странным способом: от листьев к корню. Теперь на основе этих приблизительных описаний мы разработаем детальную программу. Уже ясно, что здесь лучше всего подойдет рекурсивная формулировка, так как процесс расщепления может распространяться назад вдоль пути поиска. Общая структура программы будет сходна со структурой программы включения в сбалансированное дерево, хотя детали будут отличаться.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
