Доброго времени суток!
История данного текста такова. Ребёнку задали задание запрограммировать btree. Я иногда ему помогаю. Решил, что это тривиально. Но попытки наскоком решить задачу успехом не увенчались. Поиски сколько-нибудь разумного описания и/или кода также были тщетны. Зачёт сын давно сдал, но мой параноидальный характер заставил меня решить задачу. Может кому-нибудь пригодится.
Сбалансированное дерево поиска btree (Б дерево)
Определение не привожу. Найти его не составляет труда. Поиск, вставка ключа тривиальны.
Удаление ключа из btree
Узел будем называть пустым, если он содержит t-1 ключей, т.е. из него нельзя удалить ни одного ключа. Корень по определению никогда не пуст. Также поддерево будет называть пустым, если все его узлы пустые. Пустое дерево устроено однозначно. Соответственно полным узлом будем называть узел с количеством ключей 2t-1. Количество ключей в пустом дереве очевидно
(t-1)*(1+t+t^2+…+t^h) =t^(h+1)-1, где h-высота дерева(высота корня =0).
Если вставка ключа в btree однозначна, то удаление неоднозначно.
Если узел, в котором находится найденный ключ, листовой, тогда если узел не пуст — ключи сдвигаются, замещая удаляемый:
Если же узел пустой нужно преобразовать дерево так, чтоб он стал не пуст.
Назовем для данного ключа правым листом слева листовой узел, в который упремся двигаясь сначала к левому потомку данного ключа, а затем до листового узла по последним потомкам. Аналогично определяется левый лист справа. Сначала к правому потоку, затем по нулевым потомкам.
Если узел не листовой, данный ключ имеет правого и левого потомка и родителя (если не корень), в котором наш узел находится на позиции i. По определению btree все ключи левого потомка меньше, а все ключи правого потомка больше данного ключа. Не нарушая определения btree, каким ключом можно заменить удаляемый?
На рисунке синим помечены ключи меньше данного, желтым больше данного. Удаляемый ключ можно заменить только на самый большой из меньших или самый маленький из больших. На рисунке они обведены красным и синим цветом соответственно. Первый — это последний ключ правого листа слева, второй – первый ключ левого листа справа. Если один из них не пуст, просто меняем удаляемый ключ на один из них и удаляем заменяющий ключ из исходного листа, если нет, возвращаемся к задаче, как сделать листовой узел непустым.
Для решения задачи сделать данный листовой узел непустым рассмотрим два преобразования btree: слияние и перевес. Если данный узел не пуст, а оба потомка данного ключа пусты, можно сделать преобразование слияния. Данный ключ удаляется из своего узла, из него и его потомков делается один узел. Поскольку корень никогда не пуст, если все узлы пустые, а в корне один ключ, делается слияние, а старый корень удаляется.
Второе преобразование Btree – перевес. Если у данного ключа правый лист слева не пуст, левый лист справа не полон, можно сделать правый перевес. Если левый лист справа полон, выполняем разделение. Данный ключ вставляем в нулевую позицию левого листа справа, увеличивая на единицы число ключей в нём. Последним ключом правого листа слева замещаем данный ключ, и удаляем его.
Аналогично действует перевес вправо. Высота перевеса от одного до высоты дерева.
Теперь, собственно, алгоритм как сделать данный лист непустым. Процесс назовем обжиманием дерева. Рассмотрим обжимание вправо.
Левый брат – узел на том же уровне левее текущего. У братьев есть общий предок и ключ общего предка. Через ключ общего предка и происходит перевешивание ключей.
Если у левый брат не пуст, перевешиваем ключ. Задача решена. Если левый родной брат пуст, но родитель не пуст, выполняем слияние. Задача решена. Если и родитель пуст и левый брат, рекурсивно запрашиваем отжим у родителя затем у левого (любого) брата.
Аналогично делается обжимание влево. Неоднозначность удаления заключается в том, можно сначала обжимать или вправо, или влево. Также можно сначала запросить перевес, а потом слияние, а можно наоборот.
Доказывать неохота, но интуиция показывает, что обжимается всегда.
Надо помнить, что при перестройке дерева найденный для удаления ключ может оказаться в результате слияний в других узлах дерева. Но потерять связь с ключами на замену не может.
В качестве одного из выводов можно утверждать, что для ускорения удаления ключей желательно держать листовые узлы непустыми. Т.е. в свободное от важных дел время делать обжимание дерева вниз слияниями. Перевешивать нет смысла.
Можно также предложить некоторую оптимизацию.
Btree — дерево низенькое, но широкое. Гуляние по веткам может быть накладным. Для оптимизации можно предложить параметр вес ветки – количество ключей в ней. Поскольку вес пустого дерева – константа для одной высоты, можно гуляя по ветвям проверять вес. Если он равен весу пустого дерева, там нечего делать, если нет, на нём и остановимся, с него точно отожмём один ключ. Управление весом простое. При вставке ключа, вес всех узлов по пути вставки инкрементируется, при удалении у текущего узла и всех родителей до корня декрементируется.
Терминология собственная.
На этом прощаюсь, надеюсь, не утомил. Листинг с++ прилагается (без оптимизации и не слишком причёсанный).
P.S. Созрело и доказательство.
Если есть хоть один не пустой лист, всегда можно перевесить его к нужному. Если нет и над листами есть хоть один не пустой, делаем слияние. Далее по индукции. С учётом, что корень никогда не пуст.
Также всплыл вариант оптимизации. Если узел, в котором нужно удалить ключ не пуст, а все левые и правые потомки пусты, ключ просто удаляется, а потомки склеиваются. Т.е. если узел не пустой, никуда дальше ближайших потомков слева и справа ходить не надо.
Автор: kompotnenado
