Изменения

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

B-дерево

38 байт добавлено, 21:56, 2 апреля 2012
Операции
}
</wikitex>
 
=== Разбиение узла ===
=== Слияние ===
# Если удаление происходит из листа, смотрим на количество ключей в нем. Если ключей больше <tex>t - 1</tex>, то просто удаляем ключ. В противном случае, если существует соседний лист, который содержит больше <tex>t - 1</tex> ключа, удалим ключ из исходного узла, на его место поставим ключ-разделитель между исходным узлом и его соседом, а на его место поставим первый, если сосед правый, или последний, если сосед левый, ключ соседа. Если все соседи содержат по <tex>t - 1</tex> ключу, то объединяем узел с каким-либо из соседей, удаляем ключ и добавляем ключ-разделитель между узлами в объединенный узел. Если в родительском узле осталось меньше <tex>t - 1</tex> ключа, аналогичным образом добавляем в него ключи из соседей или объединяем узел в ними.
# Если удаление происходит не из листа, удаляем самый левый ключ из поддерева следующего дочернего узла или самый правый из поддерева предыдущего дочернего узла и ставим удаленный ключ на место удаляемого ключа в исходном узле.
 
== Вариации B-дерева ==
=== B+-дерево ===
285
правок

Навигация