285
правок
Изменения
→Удаление ключа
=== Удаление ключа ===
<wikitex>Находим ключОперация удаления ключа несколько сложнее, нежели добавление оного, который так как необходимо удалить# Если удаление происходит из листаубедиться, смотрим на количество ключей в нем. Если ключей больше $t - 1$, то просто удаляем что удаляемый ключнаходится во внутреннем узле. В противном случаеПроцесс похож на поиск подходящего места для вставки ключа, если существует соседний лист с тем же родителемтой разницей, который содержит больше $t - 1$ ключачто перед спуском в поддерево проверяется, выберем ключ-разделитель из соседа разделяющий оставшиеся ключи соседа и ключи исходного узла достаточность количества ключей (то есть не больше всех из одной группы и не меньше всех из другой)т. Обозначим этот ключ как $k_1$е. Выберем другой ключ из родительского узла, разделяющий исходный узел и его соседа, который был выбран ранее. Этот ключ обозначим $k_2\geqslant t$. Удалим из исходного узла лист, который нужно было удалить, спустим ) в этот узел $k_2$нем, а вместо $k_2$ в родительском узле поставим $k_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|переместим]] в новый узел.# Рассмотрим удаление из внутреннего узла. Имеется внутренний узел $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 последних потомка корня – то они становятся корнемрассмотрено, а предыдущий корень освобождается. Операции также операции слияния поддеревьев и перемещения ключей при удалении ключа рассмотрены ниже.
Для удаления требуется время $O(t \log_t n)$ и $O(h)$ дисковых операций.</wikitex>
==== Удаление ключа из листа ====<wikitex>Если удаление происходит из листа, смотрим на количество ключей в нем. Если ключей больше $t - 1$, то просто удаляем ключ. В противном случае, если существует соседний лист с тем же родителем, который содержит больше $t - 1$ ключа, выберем ключ-разделитель из соседа разделяющий оставшиеся ключи соседа и ключи исходного узла (то есть не больше всех из одной группы и не меньше всех из другой). Обозначим этот ключ как $k_1$. Выберем другой ключ из родительского узла, разделяющий исходный узел и его соседа, который был выбран ранее. Этот ключ обозначим $k_2$. Удалим из исходного узла лист, который нужно было удалить, спустим в этот узел $k_2$, а вместо $k_2$ в родительском узле поставим $k_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|переместим]] в новый узел.</wikitex>==== Удаление ключа из внутреннего узла ====<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>
