Как удалить поддерево B-Tree

Question

Я реализую структуру данных, основанную на B-Tree. Мне нужен метод удаления части дерева.

В частности, предположим, что записи, хранящиеся в дереве, нумеруются от 0 до n-1. Учитывая 0 < = i < = j < = n-1, removeSubtree (i, j) должен оставить допустимое B-Tree, содержащее записи 0, ..., i-1, j + 1, .. n-1.

Базовый корпус - это когда i-й и j-й записи находятся в одном и том же листовом узле, что легко. Предположим, что L_i - это листовой узел, содержащий i-ю запись, L_j - листовой узел, содержащий j-ю запись, и lca (L_i, L_j) - внутренний узел, который является самым низким общим предком L_i и L_j. Как действовать дальше?

Любая помощь будет оценена по достоинству.

Answer 1

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