285
правок
Изменения
→Перемещение ключа
<wikitex>Рассмотрим удаление из внутреннего узла. Имеется внутренний узел $x$ и ключ, который нужно удалить, $k$. Если дочерний узел, предшествующий ключу $k$, содержит больше $t - 1$ ключа, то находим $k_1$ – предшественника $k$ в поддереве этого узла. Удаляем его. Заменяем $k$ в исходном узле на $k_1$. Проделываем аналогичную работу, если дочерний узел, следующий за ключом $k$, имеет больше $t - 1$ ключа. Если оба (следующий и предшествующий дочерние узлы) имеют по $t - 1$ ключу, то [[B-дерево#.D0.A1.D0.BB.D0.B8.D1.8F.D0.BD.D0.B8.D0.B5|объединяем]] этих детей, [[B-дерево#.D0.9F.D0.B5.D1.80.D0.B5.D0.BC.D0.B5.D1.89.D0.B5.D0.BD.D0.B8.D0.B5_.D0.BA.D0.BB.D1.8E.D1.87.D0.B0|переносим]] в них $k$, а далее удаляем $k$ из нового узла. Если [[B-дерево#.D0.A1.D0.BB.D0.B8.D1.8F.D0.BD.D0.B8.D0.B5|сливаются]] 2 последних потомка корня – то они становятся корнем, а предыдущий корень освобождается.</wikitex>
==== Перемещение ключа ====
<wikitex>[[Файл:BTMv.png|thumb|right|350px|Перемещение ключа в B-дереве]]Если выбранное для нисходящего прохода поддерево содержит минимальное количеcтво ключей $t-1$, и предшествующие и следующие узлы-братья имеют по меньшей мере $t$ ключей, то ключ перемещается в выбранный узел. Поиск выбрал для спуска $x.c_2$ ($x.k_1<k_{delete}<x.k_2$). Этот узел имеет лишь $t-1$ ключ (красная стрелка). Так как следующий брат $x.c_3$ содержит достаточное количество ключей, самый маленький ключ $x.c_3.k_1$ может перемещаться оттуда в родительский узел, чтобы перемещать, в свою очередь, ключ $x.k_2$ как дополнительный ключ в выбранный для спуска узел. Левое поддерево $x.c_3.k_1$ — новое правое поддерево перемещённого ключа $x.k_2$. Легко убедиться в том, что эти повороты сортирующие, так как поддерживают структуру B-дерева: для всех ключей $k$ на отложенном поддереве до и после перенесения выполняется условие $x.k_2 \leqslant k \leqslant x.c_3.k_1$. Симметричная операция может производиться для перенесения ключа из предшествующего брата.</wikitex>
==== Слияние ====
