B-дерево: удалить неконечный узел?

Question

Я изучаю дерево B и в книге они сказали, что:

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

2. Если ключ k находится в узле x, а x является внутренним узлом, выполните следующие действия.

а. Если дочерний элемент y, который предшествует k в узле x, имеет по крайней мере t ключей, то найдите предшественника k 'of k в поддереве с корнем в y. Рекурсивно удалите k 'и замените k на k' в x. (Нахождение k 'и удаление его может быть выполнено за один проход вниз.)

б. Симметрично, если дочерний элемент z, следующий за k в узле x, имеет не менее t ключей, то найдите преемника k 'в k в поддереве с корнем в z. Рекурсивно удалите k 'и замените k на k' в x. (Нахождение k 'и удаление его может быть выполнено за один проход вниз.)

с. В противном случае, если у y и z есть только ключи t- 1, объедините k и все z в y, чтобы x потерял и k, и указатель на z, а y теперь содержит 2t - 1 ключей. Затем освободите z и рекурсивно удалите k из y.

Мой вопрос таков: в случае 2.a. Может ли кто-нибудь объяснить мне пример: рекурсивно удалить k 'и заменить k на k' в x.

С уважением.

Answer 1

Предположим, у вас есть дерево b со степенью t = 4:

   26,      49,      60
27,31,34,36     51,55,56,58

предполагать y = [27,31,34,36], x = [51,55,56,58] не являются конечными узлами, и вы хотите удалить ключ k = 51, Позволять K = 49 быть ключом в родительском узле, который разделяется x а также y,

Найти предшественника k который является самым правым ключом k' в поддереве y (который может содержать целые числа от 37 до 48 в этом примере, скажем, k' = 40). Задавать k = K = 49 а также K = k' = 40 и удалить k' рекурсивно (что на самом деле является первым случаем процедуры удаления, когда узел является листовым). Результирующее дерево b выглядит как

   26,      40,      60
27,31,34,36     49,55,56,58