Исключение элемента из B-дерева

При исключении элемента из 5-дерева возможны два варианта.

  • 1. Исключаемый элемент находится на листовой странице. В этом случае алгоритм удаления достаточно прост.
  • 2. Элемент не находится на листовой странице. В этом случае его нужно заменить одним из двух лексикографически смежных элементов. Так как смежный элемент находится на листовой странице, то его исключить просто.

В случае 2 поиск смежного ключа похож на поиск ключа при исключении из двоичного дерева. Необходимо спуститься вниз вдоль самых правых ссылок до листовой страницы Т и заменить исключаемый элемент на самый правый элемент из Т. При этом размер страницы Т должен уменьшиться на единицу.

В любом случае, после уменьшения размера страницы необходимо проверить количество элементов, оставшихся на этой странице. Если это количество стало меньше п, то нарушится одно из свойств 5-дерева.

В этом случае необходимо выполнить некоторые дополнительные действия. Один из возможных вариантов решения этой проблемы - позаимствовать элементы с одной из соседних страниц, назовем ее Q. В этом случае элементы исходной страницы Т и страницы Q поровну распределяются на обе страницы. Этот процесс называется балансировкой страниц.

Однако может случиться так, что в странице Q нечего занимать, так как ее размер уже равен минимальному - п. В этом случае общее число элементов на страницах Т и Q равно 2'п-1, и мы можем слить две страницы в одну, добавив сюда средний элемент из родительской для Т и Q страницы, а затем уничтожить страницу Q. Эти действия в точности обратны процессу разделения страниц при добавлении новых элементов.

Удаление среднего ключа на родительской странице вновь может привести к тому, что ее размер станет меньше критического и потребуется проведение описанный выше действий уже на более высоком уровне. В худшем случае слияние страниц может распространиться вплоть до корневой страницы. Если корень сократиться до нулевого размера, то он удаляется, и высота В- дерева уменьшается.

Пусть дано 5-дерево второй степени (рис. 52). Рассмотрим процесс удаления элементов из этого дерева в следующем порядке: 25, 45, 24; 38, 32; 8, 27, 46, 13, 42; 5, 22, 18, 26; 7, 35, 15.

Удаляемый ключ 25 не находится на листовой странице и должна быть заменен на самый правый элемент своего левого поддерева. В данном случае - на элемент 24. Сам элемент 24 из листовой вершины удаляется. В результате на странице остается менее двух элементов. Так как соседняя страница содержит более двух элементов, выполняется балансировка страниц (рис. 53).

Результат удаления ключа 25

Рис. 53. Результат удаления ключа 25

Удаление ключа 45 не вызывает проблем. Удаление ключа 24 в начале требует его замены на ключ 22. Страница, где ранее располагался ключ 22, стала содержать менее двух ключей. На соседней странице «занять» тоже нельзя, то есть балансировка страниц невозможна. Слияние страниц приводит к уменьшению уровня дерева (рис. 54).

Результат удаления ключа 24

Рис. 54. Результат удаления ключа 24

Удаление ключа 38 не приводит к нарушению свойств дерева. Удаление ключа 32 приведет к тому, что вершина будет содержать менее двух ключей. Соседние вершины также содержат только два ключа. Необходимо объединение вершин. Объединим текущую вершину с вершиной, расположенной слева от нее (рис. 55).

Результат удаления ключа 32

Рис. 55. Результат удаления ключа 32

Удаление ключей 8, 27 не приводит к нарушению свойств дерева. После удаления ключа 46 выполняем балансировку страниц (рис. 56).

Результат удаления ключа 46

Рис. 56. Результат удаления ключа 46

Продолжая процесс удаления ключей получим результирующее дерево (рис. 57).

Результирующее дерево

Рис. 57. Результирующее дерево

Еще раз необходимо отметить, что в процессе выполнения операций добавления и исключения элементов все свойства В-дерева сохраняются.

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ   ОРИГИНАЛ   След >