Где я могу найти алгоритм в псевдокоде для удаления ключа из B-дерева?

Question

Я читаю главу Кормена, посвященную B-деревьям в разделе Введение в алгоритмы (3-е издание), и обнаружил, что процедура удаления очень запутана. Я мог понять алгоритм вставки, потому что он предоставлял псевдокод вместе с несколькими примерами, такими как:

Но для удаления просто говорится ... «Мы рисуем, как работает удаление вместо представления псевдокода», после чего следуют шаги, которые очень запутывают. Самый первый шаг говорит:

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

Но если я удалю ключ из листа, не нарушит ли он свойство B-дерева, если количество ключей меньше требуемого минимума?

Answer 1

Согласно определению Кнута, B-дерево порядка m - это дерево, которое удовлетворяет следующим свойствам:

• Каждый узел имеет не более m дочерних элементов.
• Каждый неконечный узел (кроме корневого) имеет как минимум ⌈m / 2⌉ дочерних узлов.
• Корень имеет как минимум двух дочерних элементов, если это не листовой узел.
• Неконечный узел с k дочерними элементами содержит k - 1 ключ.
• Все листья появляются на одном уровне.

Давайте посмотрим на следующее B-дерево (порядок 5)

Давайте рассмотрим различные возможные удаления.

удалить 21

Не проблема.

• Каждый узел по-прежнему имеет не более 5 дочерних элементов.
• Узел, содержащий 21, является листом, поэтому все правила, которые упоминают «неконечные узлы», не применяются.
• Все листья все еще появляются на одном уровне

удалить 16

Необходимо перебалансировать. Корень теперь содержит 1 элемент, что на 1 меньше m / 2 (округлено в меньшую сторону).

Чтобы исправить это, мы заимствуем элемент (например, 18 или 21) и переместим его из этого листа в корень. Если бы дерево было больше, мы бы повторили эту процедуру рекурсивно вниз.

общее замечание

Имейте в виду, что большинство реализаций работают с «помеченными как удаленные» узлами, а не с фактическим удалением узлов. Пометить узел как удаленный относительно легко по сравнению с фактическим выполнением удаления и потенциальной балансировкой дерева. Кроме того, удаление обычно происходит не так часто, как вставка.