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$. Легко убедиться в том, что этот "поворот" получает условия сортировкиэти повороты сортирующие, так как для всех ключей $k$ на отложенном поддереве до и после перенесения выполняется условие $x.k_2 \leqslant k \leqslant x.c_3.k_1$. Симметричная операция может производиться для перенесения ключа из предшествующего брата.</wikitex>
==== Слияние ====
<wikitex>[[Файл:BTMg.png|thumb|right|350px|Слияние узла братом]] Если выбранное для спуска поддерево $x.c_2$ и предшествующий и следующий узел-брат содержит минимальное количество ключей, то перемещение не возможно. На иллюстрации приводится слияние выбранного поддерева с предшествующим или следующим братом для такого случая. Для этого откладывается ключ из родительского узла $x$, который разделяет ключи на два сливаемых узла, в то время средний ключ перемещается в слитый узел. Ссылки на слитые дочерние узлы заменяются ссылкой на новый узел. Так как алгоритм гарантирует, что узел, в который будет совершаться спуск, содержит по меньшей мере $t$ ключей вместо требуемых условиями B-дерева $t - 1$ ключей, родительский узел $x$ содержит достаточное количество ключей, чтобы выделить ключ для слияния. Это условие может быть нарушено, только в том случае, если 2 ребенка корня сливаются, так как поиск начинается с этого узла. По условиям B-дерева у корня должен быть как минимум один ключ, если дерево не пусто. При слиянии двух последних детей корня последний ключ перемещается во вновь возникшего единственного ребёнка, что приводит к пустому корневому узлу в не пустом дереве. В этом случае пустой узел корня удаляется и заменяется на единственного ребенка.</wikitex>
