Удаление ключа из Б-дерева

Удаление ключа из Б-дерева, хотя и аналогично вставке, представляет собой более сложную задачу. Это связано с тем, что ключ может быть удален из любого узла, а не только из листа, а удаление из внутреннего узла требует определенной перестройки дочерних узлов. Как и в случае вставки, нам необходимо обеспечить, чтобы при выполнении операции удаления не были нарушены свойства Б-дерева. Аналогично тому, как мы имели возможность убедиться, что узлы не слишком сильно заполнены для вставки нового ключа, нам предстоит убедиться, что узел не становится слишком мало заполнен в процессе удаления ключа (за исключением корневого узла, который может иметь не менее t-1 ключей, хотя и не может иметь более 2t-1 ключей).

Итак, пусть процедура B_Tree_Delete должна удалить ключ k из поддерева, корнем которого является узел x. Эта процедура разработана таким образом, что при ее рекурсивном вызове для узла x гарантировано наличие в этом узле по крайней мере t ключей. Это условие требует наличия в узле большего количества ключей, чем минимальное в обычном Б-дереве, так что иногда ключ может быть перемещен в дочерний узел перед тем, как рекурсия обратится к этому дочернему узлу. Такое “ужесточение” свойства Б-дерева (наличие “запасного” ключа) дает нам возможность выполнить удаление ключа за один нисходящий проход по дереву. Следует также учесть, что если корень дерева x становится внутренним узлом, не содержащим ни одного ключа, то узел x удаляется, а его единственный дочерний узел c₁[x] становится новым корнем дерева (при этом уменьшается высота Б-дерева и сохраняется его свойство, требующее, чтобы корневой узел непустого дерева содержал как минимум один ключ).

Последовательность выполняемых действий при удалении:

1. Если узел k находится в узле x и x является листом – удаляем k из x.

2. Если узел k находится в узле x и x является внутренним узлом, выполняем следующие действия:

а) Если дочерний по отношению к x узел y, предшествующий ключу k в узле x, содержит не менее t ключей, то находим k’ – предшественника k в поддереве, корнем которого является y. Рекурсивно удаляем k’ и заменяем k в х ключом k’.

б) Ситуация, симметричная ситуации а: если дочерний по отношению к х узел z, следующий за ключом k в узле х, содержит не менее t ключей, то находим k’ – следующий за k ключ в поддереве, корнем которого является z. Рекурсивно удаляем k’ и заменяем k в х ключом k’.

в) В противном случае, если и y, и z содержат по t-1 ключей, вносим в k и все ключи z в y (при этом из x удаляется k и указатель на z, а узел y после этого содержит 2t-1 ключей), а затем освобождаем z и рекурсивно удаляем k из y.

3. Если ключ k отсутствует во внутреннем узле x, находим корень c_i[x] поддерева, которое должно содержать k (если таковой ключ имеется в данном Б-дереве). Если c_i[x] содержит только t-1 ключей, выполняем шаг 3а или 3б для того, чтобы гарантировать, что далее мы переходим в узел, содержащий как минимум t ключей. Затем рекурсивно удаляем k из поддерева с корнем c_i[x].

а) Если c_i[x] содержит только t-1 ключей, но при этом один из ее непосредственных соседей (под которым мы понимаем дочерний по отношению к х узел, отделенный от рассматриваемого ровно одним ключом-разделителем) содержит как минимум t ключей, передадим в c_i[x] ключ-разделитель между данным узлом и его непосредственным соседом из х, на его место поместим крайний ключ из соседнего узла и перенесем соответствующий указатель из соседнего узла в c_i[x].

б) Если и c_i[x] и оба его непосредственных соседа содержат по t-1 ключей, объединим c_i[x] с одним из его соседей (при этом бывший ключ-разделитель из х станет медианой нового узла).

Рассмотрим работу алгоритма на примере. Для примера возьмем данное дерево(получившееся в предыдущем примере после добавления элемента).

Будем удалять из этого дерева элемент 10. Сначала надо, двигаясь от корня, найти узел дерева, содержащий этот элемент. Он находится в корне. Теперь поскольку элемент находится не в листовом узле, надо заменить его, например, на самый левый элемент правого поддерева. Делаем один шаг вправо и попадаем в корень правого поддерева. Теперь пока не достигнем листового узла, переходим на самого левого сына.

Таким образом мы найдем узел, из которого позаимствуем элемент для замены удаленного элемента 10. В найденном узле возьмем самый левый элемент. Таковым оказывается 11. Произведем замену элемента 10 на 11 и удалим элемент 11.

Теперь проверим узел, из которого был удален элемент на предмет антипереполнения. Число элементов в узле равно нулю. Это меньше половины размера узла. Следовательно, возникло антипереполнение. Выберем два соседних узла: один - из которого было удалено 11, второй - соседний узел с числом 13. Суммарное число элементов в этих узлах не превышает максимального размера узла, значит, нам следует произвести слияние узлов. При слиянии элемент 12 родителя попадает в результирующий узел и удаляется из родителя.

Теперь переходим к родителю, из которого был удален элемент, и проверяем на предмет антипереполнения. Антипереполнение есть и опять, мы должны выбрать два соседних узла (в данном случае: узел, из которого был удален элемент 12 и узел с элементом 17) и произвести слияние двух узлов. При слиянии получается узел с элементами 14 и 17, где 14 позаимствовано у родителя. Естественно, элемент 14 из родителя удаляется.

Поскольку опять был удален элемент родителя, то переходим к родителю, и проверяем на наличие антипереполнения. Снова, обнаружив антипереполнение, выбираем два соседних узла (на этот раз узел, из которого был удален элемент 14 и узел с элементом 5). Поскольку суммарный размер меньше максимального размера узла, произведем слияние этих узлов. Получаем узел с элементами 5 и 11, где 5 позаимствовано у родителя и удалено из него.

Опять переходим к родителю. Поскольку родитель оказывается корнем, то цикл обработки “антипереполнений” заканчивается. Осталось проверить, не пуст ли корень дерева. Корень дерева пуст, поэтому его можно удалить. Новым корнем дерева будет тот единственный узел, на который есть ссылка в старом корне. Это узел с элементами 5 и 11.

Список используемых источников

· Томас Х. Кормен, Чарльз И. Лейзерсон, Рональд Л. Ривест, Клиффорд Штайн. Глава 18. B-деревья // Алгоритмы: построение и анализ — 2-е изд. — М.: Вильямс, 2006. — С. 515­—536.

· А. В. Ахо, Д. Э. Хопкрофт, Д. Д. Ульман, Джеффри. Глава 11.4 В-деревья // Структура данных и алгоритмы – Вильямс, 2000. – с. 330- 334.

· http://habrahabr.ru/post/114154/

· http://altim.narod.ru/Docs/Russian/Manuals/Lab/Chapter5/B_Tree.htm

· http://gubsky.ru/study/5/soad/sh/26.htm

·