Как удалить элемент из b-дерева?

Question

Я пытаюсь узнать о b-дереве, и каждый источник, который я могу найти, кажется, пропускает обсуждение о том, как удалить элемент из дерева при сохранении свойств b-дерева.

Может кто-нибудь объяснитьалгоритм или указать мне ресурс, который объясняет, как это делается?

Answer 1

На странице Википедии есть объяснение этому. B-дерево - Удаление

Answer 2

Если у вас его еще нет, я настоятельно рекомендую Кармен и др. Введение в алгоритмы, 3-е издание .

Это не описано, поскольку операции естественным образом происходят из B-дерева.properties.

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

Если вы объединяетесь с соседом, то вам нужно удалить элемент в родительском узле, который запускает тот же алгоритм.И вы применяете рекурсивно, пока не достигнете вершины.

У B-Tree нет перебалансировки (по крайней мере, не тех, которые я видел), поэтому гораздо проще, чем поддерживать красно-черное дерево или дерево AVL, котороеВероятно, поэтому люди не чувствовали себя обязанными писать об удалении.

Answer 3

Пример удаления из CLRS (2-е издание) доступен здесь: http://ysangkok.github.io/js-clrs-btree/btree.html

Нажмите «Начальная книга», а затем нажмите кнопки удаления по порядку.Это будет охватывать все случаи.Попробуйте предсказать новое состояние дерева, прежде чем нажимать каждую кнопку, и попытайтесь распознать, как уникальны все случаи.

Answer 4

О каких би-деревьях ты говоришь? Со связанными листьями или нет? Также есть разные способы удаления предмета (сверху вниз, снизу вверх и т. Д.). Эта статья может помочь: B-деревья, теневое копирование и клоны (даже при том, что есть много связанных с файловой системой вещей).