B-tree: удалить нелистовой узел?

Question

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

1. Если ключ к находится в узле х и х представляет собой лист, удалить ключ к от х.

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

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

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

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

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

С уважением.

Answer 1

Предположим, у вас есть б дерево со степенью т = 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, который находится в поддереве y крайнюю правую клавишу k' (который может содержать целые числа от 37 до 48 в этом примере, скажем k' = 40). Установите k = K = 49 и K = k' = 40 и удалите k' рекурсивно (что на самом деле является первым случаем процедуры удаления, когда узел является листом). Полученное дерево b выглядит как

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