286
правок
Изменения
Нет описания правки
B<tex>^{+}</tex>-деревья являются сбалансированными, поэтому время выполнения стандартных операций в них пропорционально высоте.
=== Поиск листа ===
Напишем вспомогательную функцию, которая будет возвращать лист, в котором должен находится переданный ей ключ. Определяем интервал и переходим к соответствующему сыну. Повторяем пока не дошли до листа.
=== Добавление ключа ===
Ищем лист, в который можно добавить ключ и добавляем его в список ключей. Если узел не заполнен, то добавление завершено. Иначе разбиваем узел на два узла. Будем считать, что в дереве не может находиться 2 одинаковых ключа, поэтому <tex>insert</tex> будет возвращать был ли добавлен ключ.
'''bool''' insert(T: '''BPlusTree''', key: '''int''', value: '''Info'''):
Разбиение на два узла происходит следующим образом: в первый добавляем первые <tex>t - 1</tex> ключей, во второй оставшиеся <tex>t</tex>. Первый ключ из второго узла копируется в родительский узел, где становится разделительной точкой для двух новых поддеревьев.
Если и родительский узел заполнен {{---}} поступаем аналогично, но не копируем, а перемещаем ключ в родительский узел, так как это просто копия. Повторяем пока не встретим незаполненный узел или не дойдем до корня. В последнем случае корень разбивается на два узла и высота дерева увеличивается. Будем считать, что в дереве не может находиться 2 одинаковых ключа, поэтому <tex>insert</tex> будет возвращать был ли добавлен ключ.
'''void''' split(T: '''BPlusTree''', node: '''Node'''):
