39
правок
Изменения
Нет описания правки
Ищем лист, в который можно добавить ключ, совершая проход от корня к листьям. Если найденный узел не заполнен, добавляем в него ключ. Иначе разбиваем узел на два узла, в первый добавляем первые <tex>t - 1</tex> ключей, во второй — последние <tex>t - 1</tex> ключей. Добавляем ключ в один из этих узлов. Оставшийся средний элемент добавляем в узел родителя, если он заполнен — повторяем пока не встретим не заполненный узел или не дойдем до корня. В последнем случае корень разбивается на два узла и высота дерева увеличивается.
== Удаление ключа ==
# Находим узел, содержащий ключ, который необходимо удалить.
# Если узел является листом и корнем одновременно, удаляем из него ключ.
# Если узел является листом, удаляем из него ключ.
## Если в узле осталось меньше <tex>t - 1</tex> ключей.
### Если у узла есть следующий брат и в нем не менее <tex>t</tex> ключей, добавляем в узел ключ из родителя, находящийся между ним и следующим сыном, а на его место ставим первый ключ брата.
### Если у узла есть предыдущий брат и в нем не менее <tex>t</tex> ключей, добавляем в узел ключ из родителя, находящийся между ним и предыдущим сыном, а на его место ставим последний ключ брата.
### Если у братьев меньше <tex>t</tex> ключей, объединяем узел с предыдущим или следующим братом и добавляем в получившийся узел ключ из родителя, разделявший узлы. Если у родителя осталось менее <tex>t - 1</tex> ключей и родитель не является корнем, переходим к пункту 3.1.
# Если узел не является листом, удаляем из него ключ, а на его место ставим
