Изменения

Перейти к: навигация, поиск

B-дерево

5 байт добавлено, 20:50, 11 июня 2012
м
Операции
==== Удаление ключа из листа ====
<wikitex>[[Файл:B3dell.PNG|thumb|left|380px|Удаление из листа]]Если удаление происходит из листа, смотрим на количество ключей в нем. Если ключей больше $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>
 
 
 
 
 
==== Удаление ключа из внутреннего узла ====
285
правок

Навигация