Virt N. Algoritmy struktury dannyh = programmy (ru)(T)(410s) (522393), страница 49
Текст из файла (страница 49)
Динамические информацииннме струнгурм епй (й!е!е) ! уеееейпгерг!л7ггее(р: ге!! 1: !л7ейег); твг П !л7ейег! Ъей1п 11 р Ф ей1 ЕЬеп МЬ р! йо Ъей1п Йв 1:= 1 1о ! йо ггг!ге(' '); Йв ! '.= 1 ео ле йе юг!ге(е1!).!сеу'. 4); мейе!л; рг!а!!тес(рО,!+ 1); аог ! .'= 1 1о тл йорг!л!!гее(еД .р, !+1) епй епй; Ьей(п гоо1:= ей1; геас!(х)' чеЫ1е х М О йо Ьей1п тг7е!л(еедлсн ееч; х); ееагсй(х,гоог,7г,и); 1е Ь ЕЬеп Ъей!п !включение новой корневой евранлцъ7) й:= гоо1;иегр(гоо!) чг11Ь гоот) йо Ьеп1п тл г=н 1; рО:= а; еЩ;= и епй епй; рт!л!7гее(гоо1,1); геос!(х) епй; таам(х); чеЬ11е х -,— О йо Ьей1п м'г!ге!л('оееете аеч', х),' с!е!еге(х,гоо!,л); 1а л ЕЬеп Ьей1п (удгельшен раздеер корневой етлраиицвг) 11гоог1ат! = О 1Ьеп Ьеп1п а;= тоог; тоо1:= й!.рО; (с7!грозе(г!)) епй епй; рг!л!!гее(гоо$,1) ! геай(х) епй епй Программа 4.7, Паиса, аааючеиае и удаасние а Б-дереае.
4Х Сильно ветвящиеся деревья сматрнвается вопрос об оптимальном размере страницы и, который сильно зависит от характеристик памяти и вычислительной системы. Вариации схемы Б-дерева обсуждаются в книге Кнута (12.7], т. 3, с. 867 — 570). Одно важное замечание заключается и том, что расщепление страницы следует задерживать тем >ке способом, каким задерживается слияние страниц: балансировкой соседних страниц. Остальные предлагаемые улучшения, по-видимому, не дают ничего существенного.
4.5.2. Ьинвриыв В-деревьв Разновидность Б-деревьев, которая кажется наименее интересной, — Б-деревья первого порядка (и = 1). Но иногда с>онт обратить внимание и на этот случай. Ясно, однако, что Б-деревья первого порядка бесполезны для представления больших, упорядоченных, индексированных множеств данных, требующих внешней памяти; примерно 50 е1> всех страниц будут содер>кать только один элемент. Поэтому мы забудем о внешней памяти и вновь рассмотрим деревья поиска, расположенные в оперативной памяти. Бинарное Б-дерево (ББ-дерево) состоит из узлов (страниц) с одним или двумя элементами. Следовательно, страница содержит две или три ссылки на потомков, отсюда термин 2 — 3 дерево.
Согласно определению Б-деревьев, все листья находятся на одном уровне, а все нетерминальные страницы, в том числе корень, имеют двух или трех потомков. Поскольку теперь мы имеем дело только с оперативной памятью, то обязательно оптимальное использование памяти, н поэтому представление элементов узла в виде массива здесь не подходит. Альтернатива этому — динамическое, связанное размещение, т. е. внутри каждого узла имеется связанный список элементов длиной 1 или 2. Поскольку каждый узел имеет не более трех потомков н поэтому должен содержать самое большее три ссылки, мы попытаемся комбинировать ссылки на потомков и ссылки в списке элементов, как показано на рис.
4.50. Тем самым узел Б-дерева теряет свою целостность, и элементы выполняют роль узлов в обычном бинарном дереве. Но необходимо различать ссылки на потомков (вертикальные) и ссылки на «братье⻠— элементы той же страницы (горнзонтальные). Поскольку лишь ссылки направо мокнут быть горизонтальными, для указания этого различия достаточно одного разряда. Поэтому мы вводим булевское поле й, фиксирующее «горизонталь». Описание узла дерева, основанное на таком представлении, дано в (4.84). Оно было предложено Р.
Бэйером 14.31 в 1971 г. Деревья поиска, по- Е. динамические инзрормаяионные структуры строенные из таких узлов, гарантируют максимальную длину пути р = 2 (!ода]. Фуре нозуе = гееогз) йеу; Фнгеяег) (4.84) ЗеЯ,г(айг: ген Ь: ЬооФеап езкт Рассматривая проблему включения, следует различать четыре возможные ситуации, которые возникают при увеличеф в Ь с Рис. 4.50. Предстввлввве узлов ББ-дереве.
нии левого или правого поддерева. Эти четыре случая показаны на рис. 4.51. Вспомним, что Б-деревья обладают свойством расти от листьев к корню и что нужно следить, чтобы все листья оставались на одном уровне. Самый простой случай — это (1), когда растет правое поддерево узла А и когда А — единственный кл1оч на (гипотетической) странице, Тогда потомок В просто становится братом Л, т. е.
вертикальная ссылка становится горизонтальной. Такой простой «подъем» правой ветви невозможещ если Л уже имеет брата. Тогда мы получаем страницу с тремя узлами и должны расщепить ее (случай 2). Ее средний узел В передается на ближайший более высокий уровень. Тепсрь предположим, что увеличилась высота левого поддерева узла В. Если узел В снова один на странице (случай 3), т, е, его правая ссылка указывает па потомка, то левое поддерево (А) может стать братом В. 11ужеп простой поворот ссылок, так как левая ссылка не может быть горизонтальной. Но если В уже имеет брата, подъем Л дает страницу с тремя узлами, что требует расщепления.
Это расщепление выполняется очень просто: С становится потомком В, который поднимается иа ближайший более высокий уровень (случай 4). 4.5. Сильно ветвящиеся деревья Следует заметить, что при поиске ключей нет особой разинцы, двигаемся мы по горизонтальной или вертикальной а Ь о с и а Ьа и з Ь (41 Е а Ь с и а Ь с д Рис.
4.Б1. Вкльзчеаае узлов в ББ.дерево. ссылке. Поэтому забота о том, чтобы левая ссылка в случае 3 становилась горизонтальной, хотя страница по-прежнему содержит не более двух узлов, кажется надуманной. Действительно, алгоритм включения проявляет странную асимметрию 4. Динамические информационные структуры при увеличении роста левого и правого поддеревьев, поэтому организация ББ-дерева кажется несколько искусственной.
У нас иет «доказательств» необычности такой организации, и лишь интуиция говорит нам, что здесь «что-то ие то», и нам следует избавиться от такой асимметрии. Это ведет к понятию силгмегрианого бинарного Б-дерева (СББ-дерева), которое также было предложено Бэйером 14.4) в 1972 г, Такое по- в "- Я',Й-,, *Й Щ л "' В с А ФРЙ ЙЙ '"" Р Й Рнс. ЕД2, Включение и СВБ-дереиьи. строение дает в среднем несколько более эффективные деревья поиска, но алгоритмы включения и удаления прн этом несколько сложнее. Кроме того, теперь каждый узел требует двух разрядов (булевские переменные И и г!г) для обозначения природы его ссылок. Поскольку мы собираемся детально остановиться иа проблеме включения, то нам надо еще раз определить различия в четырех случаях роста поддеревьев.
Они показаны иа рис, 4.52, на котором наглядно видна полученная симметрия. Заметим, что всегда, когда растет поддерево узла А, не имеющего братьев, корень этого поддерева становится братом А, Этот случай ие нуждается в дальнейшем обсуждении. 4Д.
Сильно веевви!ивен деревьв Четыре случая, приведенные на рис. 4.52, иллюстрируют и реполнение страницы и последующее ее расщепление. Они отмечены в соответствии с направлениями горизонтальных ссылок, связывающих трех братьев на рисунках в среднем с|олбце. Исходная ситуация показана в левом столбце, в сред- неи столбце показано, что узел, находящийся внизу, подни- мается с ростом поддерева; на рисунках правого столбца по- казан результат перестановки узлов при расщеплении стра- ницы.
Желательно больше не возвращаться к понятию страниц, па основе которого разработана эта организация, так как все, ь ~ему мы стремимся, — это ограничить максимальную длину пути поиска значением 2 1оп М. Для этого нужно только, ч)обы нигде иа пути поиска не встречались две последова- тельные горизонтальные ссылки. Но нет причины запрещать л;обыс узлы с горизонтальными ссылками налево и направо. Поэтому мы определяем СББ-дерево как дерево со следую- щими свойствами; 1.
Каждый узел содержит один ключ и не более двух поддеревьев (ссылок), 2 Каждая ссылка либо горизонтальная, либо вертикальная. Ни на каком пути поиска нет двух последовательных гори. зонтальных ссылок. 3. Все терминальные узлы (узлы, не имеющие потомков) находятся на одном (терминальном) уровне. Из этого определения следует, что самый длинный путь по- иска не более чем в два раза превосходит высоту дерева.
Так как никакое СББ-дерево с )У узлами не может иметь высоту, ббльшую [!опЛ'(, то 2 (1оцМ) является верхним пределом длины пути поиска. Чтобы читатель наглядно представил себе, как растут эти деревья, мы отсылаем его к рис. 4.53. На нем показаны изме- нения четырех деревьев при последовательных включениях элементов с ключами, перечисленными в строках (4.85), где точки с запятой отмечают моменты увеличения высоты де- рева: (1) 1 2; 3; 4 5 6; 7; (2) 5 4; 3; 1 2 7 6; (4.85) (3) 6 2; 4; 1 7 3 5; (4) 4 2 6; ! 7; 3 5; Эти рисунки особенно наглядно иллюстрируют третье свойство Б-деревьев: все терминальные узлы находятся на одном уровне.
Поэтому хочется сравнить эти структуры с только что подстриженными садовыми кустарниками. Мы будем называть такие структуры кустарниками, зоо Е. динамические информационные стрдктцры Алгоритм построения кустарников сформулирован в (4.87). Оц основан на определении типа узла (4.86) с двумя компонентами Рл и тЬ, обозначающими горизонтальность левой и правой ссылок. Фуре поде = теевгй 1геу: !агент; соиш: 1нгеяег: 1е~Я,г18ЬВ геу; 1Ь,»Ь: Боо)еап евв (4. 86) Рекурсивная процедура зеатсй вновь строится по основной схеме алгоритма включения в бинарное дерево (см. (4.87) ).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
