Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 116
Текст из файла (страница 116)
18.4). Следовательно, число ключей и удовлетворяет следующему неравенству: 518 Часть Е Сеансные структуры данные 18.1.2 Для каких значений с дерево на рис. 18.1 является корректным В-деревом? 18.1.3 Изобразите все корректные В-дереаья с минимальной степенью 2, представляющие множество 11, 2, 3, 4, 5).
18.1.4 Чему равно максимальное количество ключей, которое может храниться в В-дереве высотой 6, выраженное в виде функции от минимальной степени дерева г? 18.1.5 Опишите структуру данных, которая получится, если в красно-черном дереве каждый черный узел поглотит красные дочерние узлы, а их потомки станут дочерними узлами этого черного узла. 18.2. Основные операции с В-деревьими В этом разделе мы более подробно рассмотрим операции В-Ткее-белксн, В-Ткее-Скелте и В-Ткее-1нзект, приняв при этом следующие соглашения.
Корень В-дерева всегда находится в оперативной памяти, так что операция Ошк-Кело для чтения корневого узла не нужна; однако при изменении корневого узла требуется выполнение операции Р1ЗК-%К~тЕ, сохраняющей внесенные изменения на диске. Все узлы, передаваемые в качестве параметров, уже считаны с диска операцией Ршк-Кело. Все представленные здесь процедуры выполняются за один нисходящий проход по дереву Поиск в В-дереве Поиск в В-дереве очень похож на поиск в бинарном дереве поиска, но с тем отличием, что если а бинарном дереве поиска мы выбирали один из двух путей, то здесь предстоит сделать выбор из большего количества альтернатив, зависящего от того, околыш дочерних узлов имеется у текущего узла. Точнее, в каждом внутреннем узле х нам предстоит выбрать одну из (х.
и + 1) ветвей. Операция В-Ткее-белксн представляет собой естественное обобщение процедуры Ткее-Белксн, определенной для бинарных деревьев поиска. В качестве параметров процедура В-Ткее-8елксн получает указатель на корневой узел х поддерева и ключ Е, который следует найти в этом поддереве. Таким образом„вызов верхнего уровня для поиска во всем дереве имеет вид В-Ткее-8елксн (Т. гоо1, Е).
Если ключ?с имеется в В-дереве, процедура В-Ткее- Глава 1д В-деревья 5л9 беАксн вернет упорядоченную пару (у,!), состоящую из узла у и индекса ь', такого, что у.)сеу; = к. В противном случае процедура вернет значение ин.. В-Ткее-БеАксн (х, к) 1 1=1 2 иййе ! < х.п и lс > х.)сеу, 3 1=!+1 4 !1! < х.п и)с== х.)сеу; 5 ге!игл (х,ь) б е!зеИ х. 1еа5 7 гетпгп ни. 8 е1зе 13!як-КеАО(х.с,) 9 гетпгп В-Ткее-БеАксн(х.с,, lс) В строках 1-3 выполняется линейный поиск наименьшего индекса ь', такого, что )с < х.)сеу, (иначе ! присваивается значение х.п + 1).
В строках 4 н 5 проверяется, не найден ли ключ в текущем узле, и если найден, то выполняется его возврат. В противном случае в строках 6-9 процедура либо завершает свою работу неудачей (если х является листом), либо рекурсивно вызывается для поиска в соответствующем поддереве х (после выполнения чтения с диска необходимого дочернего узла, являющегося корнем исследуемого поддерева). На рис. 18.1 показана работа процедуры В-Ткее-ЯеАксн: светлым цветом выделены узлы, просмотренные в процессе поиска ключа В.
Процедура В-Ткее-БеАКСн, как и процедура Ткее-8еАКСН при выполнении поиска в бинарном дереве, проходит в процессе рекурсии узлы дерева от корня в нисходящем порядке. Количество дисковых страниц, к которым выполняется обращение процедурой В-Ткее-БеАксн, равно 0(6) = 0(!о8, и), где 6 — высота В-дерева, а и — количество содержащихся в нем узлов. Поскольку х.п < 21, количество итераций цикла ьтЫе в строках 2 и 3 в каждом узле равно О(!), а общее время вычислений составляет 0(гй) = О(! 1окс и). Создание пустого В-дерева Для построения В-дерева Т сначала необходимо воспользоваться процедурой В-Ткее-СкеАте для создания пустого корневого узла, а затем внести в него новые ключи с помощью процедуры В-ТкЕЕ-1НЕЕкт.
В обеих этих процедурах используется вспомогательная процедура Аи.ОСАТе-!ь!ООЕ, которая выделяЕт диС- ковую страницу для нового узла за время 0(1). Мы можем считать, что эта процедура не требует вызова Р!Ек-кеАО, поскольку никакой полезной информации о новом узле на диске при этом не сохраняется. 530 Часть Е Сложные струнтуры санные В-Ткее-СкеАте(Т) 1 х = АЬЬОСАТЕ-ХООЕО 2 х. (саз = ткце 3 х.п =О 4 01зк-%к1те(х) 5 Т.тоо1 = х В-Ткее-СкеАте требует 0(1) дисковых операций, время ее выполнения также равно 0(1).
Вставка ключа в В-дерево Вставка ключа в В-дерево существенно сложнее вставки в бинарное дерево поиска. Как и в случае бинарных деревьев поиска, мы ищем позицию листа, в юторый будет вставлен новый ключ. Однако при работе с В-деревом мы не можем просто создать лист и вставить в него ключ, поскольку такое дерево не будет являться корректным В-деревом. Вместо этого мы вставляем новый ключ в существующий лист.
Поскольку вставить новый ключ в заполненный лист невозможно, мы вводим новую операцию — разбиение (зр!ййп8) заполненного (т.е. содержащего 21 — 1 ключей) узла у на два, каждый из которых содержит по 1 — 1 ключей. Медиана, или средний ключ (шейки кеу), у. Йеу, при этом перемещается в родительский по отношению к у узел, где становится разделительной точкой для двух вновь образовавшихся поддеревьев. Однако если родительский узел заполнен, перед вставкой нового ключа его также следует разбить, и такой процесс разбиения может выполняться по восходящей до самого корня. Как и в случае бинарного дерева поиска, в В-дереве мы вполне можем осуществить вставку за один нисходящий проход от корня к листу.
Для этого не нужно выяснять, требуется ли разбить узел, в который должен вставляться новый ключ. Вместо этого при проходе от корня к листьям в поисках позиции для нового ключа мы разбиваем все заполненные узлы, через которые проходим (включая сам лист). Тем самым гарантируется, что если потребуется разбить какой-то узел, то его родительский узел заполнен не будет.
Разбиение узла В-дерева Процедура В-Ткее-ЗР$лт-Снп.п получает в качестве входного параметра незаполненный внутренний узел х (находящийся в оперативной памяти) и индекс з, такой, что узел х.с; (также находящийся в оперативной памяти) является заполненным дочерним узлом х. Процедура разбивает дочерний узел на два и соответствующим образом обновляет поля х, внося в него информацию о новом дочернем узле. Для разбиения заполненного корневого узла мы сначала делаем корень дочерним узлом нового пустого корневого узла, после чего можем использовать вызов В-ТкЕЕ-БРЕ1Т-Сн1ЕО.
При этом высота дерева увеличивается на 1. Разбиение — единственный путь увеличения высоты В-дерева. На рис. 18.5 показан этот процесс. Заполненный узел у разбивается медианой Я, которая перемещается в родительский по отношению к у узел. Те ключи Г 18 В-бр л уй'" ье~'убз' ~Ф Ф Р = К.С4 а = к. сььз ),,'."~.'=;!'.",'Оь'::Ф:; '1'-!;::~ Тз Тз Тз Т4 Ть Та Т7 Та Т1 Тз Тз Т4 Тз Та Т7 Та Рнс. 1В.б. Разбиение узла с 1 = 4. Узел р = к.с, разбиааетса на даа узла, р и л, и средний клккь Я узла р перенепиетсл а родительский по отногленню к р узел.
из у, которые больше медианы, помещаются в новый узел л, который становится новым дочерним узлом х. В-ТКЕЕ-Брс1Т-СН1сп (х, з) 1 л = АЫ.ОСАТЕ-)ь1ООЕО 2 у=ха; 3 л.1еау = у.1еау 4 л.п =1 — 1 5 Рогу' = 11о1 — 1 6 л.йеуу = у.йеу .+, 7 Ы пот у. 1еау 8 Гогу' = 11о1 9 л.сз = у.ау+4 1О у.п =1 — 1 11 Гогу' = х.п+1бозкито2'+1 !2 х.с +1 = х.с. 13 х.аз+1 = л 14 Рагу = .
йо итоз 15 х.)сеу +1 = х.неуу 16 х.неуз = у.(сеуз 17 х.п = х.п+1 18 131 як-1ук1те (у) 19 131зк-%к1те(л) 20 01$К-%К1ТЕ(х) Процедура В-ТКЕЕ-Крыт-Снп. О использует простой способ "вырезать и вставить'*. Здесь х является разбиваемым узлом, а у представляет собой з'-й дочерний узел узла х (устанавливается в строке 2).
Изначально узел у имеет 21 дочерних узла (содержит 21 — 1 ключей).„после разбиения количество его дочерних узлов уменьшится до 1 (1 — 1 клкзчей). Узел л получает 1 ббльзпих дочерних узлов (1 — 1 ключей) у и становится новым дочерним узлом х, располагаясь непосредственно Часть Е С»аисиые структуры даииы» 532 после у в таблице дочерних узлов х. Медиана у перемешается в узел х и разделяетвнемуиж В строках 1 — 9 создается узел г и в него переносятся ббльшие ! — 1 ключей и соответствующие ! дочерних узлов у.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
