Изменения

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

B-дерево

44 байта добавлено, 20:54, 17 мая 2011
Удаление ключа
Находим ключ, который необходимо удалить
# Если удаление происходит из листа, смотрим на количество ключей в нем. Если ключей больше <tex>t - 1</tex>, то просто удаляем ключ. В противном случае, если существует соседний лист, который содержит больше <tex>t - 1 </tex> ключа, удалим ключ из исходного узла, на его место поставим ключ-разделитель между исходным узлом и его соседом, а на его место поставим первый, если сосед правый, или последний, если сосед левый, ключ соседа. Если все соседи содержат по <tex>t - 1 </tex> ключу, то объединяем узел с каким-либо из соседей, удаляем ключ и добавляем ключ-разделитель между узлами в объединенный узел. Если в родительском узле осталось меньше <tex>t - 1 </tex> ключа, аналогичным образом добавляем в него ключи из соседей или объединяем узел в ними.
# Если удаление происходит не из листа, удаляем самый левый ключ из поддерева следующего дочернего узла или самый правый из поддерева предыдущего дочернего узла и ставим удаленный ключ на место удаляемого ключа в исходном узле.
Анонимный участник

Навигация