Процедура добавляет элемент k в Б-дерево, пройдя один раз от корня к листу. На это требуется время O(th)=O(tlogtn) и O(h) обращений к диску. По ходу дела мы разделяем вершины, которые имеют неполного родителя (если полон корень, то создаем новую вершину, которую делаем корнем с одной записью на старую вершину, и разделяем старый корень), так как в родителе есть место для ключа. В конце концов, мы оказываемся в листе, куда и добавляем новый элемент. Обратите внимание, что точкой роста Б-дерева является корень (а не лист, как в двоичных деревьях поиска).
Удаление элемента происходит аналогично добавлению. Пусть необходимо удалить ключ k из поддерева с корнем в вершине x. Пусть при каждом рекурсивном вызове вершина x содержит по крайней мере t ключей. Так как по правилам в вершинах должно содержаться не менее t–1 ключей, так что в нашем случае имеется один запасной ключ. Это позволяет удалить элемент при первом проходе от корня к листьям (не делая шагов в обратном направлении). Пусть если в результате удаления корень стал пустым, то он удаляется, а единственный ребенок становится на его место. Рассмотрим варианты удаления вершины:
1. Если ключ k находится в вершине x, являющейся листом, то удаляем k из x.
2. Если ключ k находится во внутренней вершине, то
· Если ребенок y вершины x, предшествующий k, содержит не менее t элементов, то находим ключ k’, непосредственно предшествующий k. Этот ключ находится в листе поддерева с корнем в y. Рекурсивно вызываем процедуру: удаляем k’. Заменяем ключ k на k’.
· Если ребенок z, следующий за k, содержит не менее t элементов, поступаем аналогично.
· Если и y, и z содержат по t–1 элементов, соединяем вершину y, ключ k и вершину z, помещая все это в вершину y, которая теперь содержит 2t–1 ключей. Стираем z и выкидываем из x ключ k и указатель на z. Рекурсивно удаляем k из y.
3. Если x – внутренняя вершина, но ключа k в ней нет, найдем среди детей вершины x корень ci поддерева, где должен лежать ключ k (если этот ключ вообще есть). Если ci содержит не менее t ключей, можно рекурсивно удалить k из поддерева. Если же он содержит всего t–1 элементов, то предварительно сделаем шаг 3а или 3б.
· Пусть вершина ci содержит t–1 элементов, но один из ее соседей (например, правый) содержит по крайней мере t элементов (здесь соседом назовем такого ребенка вершины x, который отделен от ci ровно одним ключом-разделителем). Тогда добавим ребенку ci элемент из вершины x, разделявшей ci и его правого соседа, а в вершину x вместо него поместим самый левый элемент этого соседа. При этом самый левый ребенок соседа превращается в самого правого ребенка вершины ci.
· Пусть оба соседа вершины ci содержат t–1 элементов. Тогда объединим вершину ci с одним из соседей (как в случае 2в). При этом ключ, разделявший их в вершине x, станет ключом-медианой новой вершины.
Описанная процедура требует возврата к уже просмотренной вершине только в случаях 2а, 2б (когда она заменяет его предшественником или последователем). Заметим, что это происходит, лишь если требуется удалить элемент из внутренней вершины.
Хотя процедура выглядит запутанной, она требует всего O(h) обращений к диску. Вычисления требуют времени O(t logth).
· Несколько раз прочитайте лекцию, прежде чем приступать к домашнему заданию.
· Выпишите вопросы по данной теме.
· Реализуйте на C++ контейнерный класс (шаблонный или для заданного типа), инкапсулирующий функциональность красно-черного дерева. Реализуйте процедуры, типичные для деревьев.
· Подсчитайте сложность алгоритма поиска элемента в Б-дереве.
Т. Кормен, Ч. Лейзерсон, Р. Ривест [2001], Алгоритмы. Построение и анализ, МЦНМО, М., 92 – 100, 207 – 213, 236 – 246
А. Шень, Программирование. Теоремы и задачи, http://tower.kture/
Уважаемый посетитель!
Чтобы распечатать файл, скачайте его (в формате Word).
Ссылка на скачивание - внизу страницы.