Изменения

'''B<tex>^{+}</tex>-дерево''' (англ. ''B<tex>^{+}</tex>-tree'') {{---}} структура данных на основе [[B-дерево|B-дерева]], сбалансированное <tex>n</tex>-арное дерево поиска с переменным, но зачастую большим количеством потомков в узле. B<tex>^{+}</tex>-деревья имеют очень высокий коэффициент ветвления (число указателей из родительского узла на дочерние, обычно порядка <tex>100 </tex> или более), что снижает количество операций ввода-вывода, требующих поиска элемента в дереве.

{{Теорема|statement=Если <tex>n \geqslant 1</tex>, то для B<tex>^{+}</tex>-дерева c <tex>n</tex> узлами и минимальной степенью <tex>t \geqslant 2</tex>высота

Как можно заметить, высота B<tex>^{+}</tex>-дерева не более чем на <tex>1 </tex> отличается от [[B-дерево#Высота|высоты B-дерева]], то есть хранение информации только в листах почти не ухудшает эффективность дерева

'''while''' !now.leaf<tex>\neq</tex> true

Разбиение на два узла происходит следующим образом: в первый добавляем первые <tex>t - 1</tex> ключей, во второй оставшиеся последние <tex>t</tex>. Первый Если узел {{---}} лист, то оставшийся ключ из второго узла копируется также добавляется в левое поддерево, а его копия отправляется в родительский в родительский узел, где становится разделительной точкой для двух новых поддеревьев.

Если и родительский узел заполнен {{---}} поступаем аналогично, но не копируем, а просто перемещаем оставшийся перемещаем ключ в родительский узел, так как это просто копия. Повторяем пока не встретим незаполненный узел или не дойдем до корня. В последнем случае корень разбивается на два узла и высота дерева увеличивается.

new_node = new_Node() <span style="color:#008000"> //Создаем новый узел</span>

new_node.key[i] = node.key[i + t - 1] new_node.pointers[i] = node.pointers[i + t - 1] new_node.child[i] = node.child[i + t - 1] new_node.child[new_node.key_num] = node.child[2 * t - 1]

Поскольку все ключи находятся в листах, для удаления в первую очередь необходимо найти листовой узел, в котором он находится. Если узел содержит не менее <tex>t - 1</tex> ключей, где <tex>t</tex> {{---}} это степень дерева, то удаление завершено. Иначе необходимо выполнить попытку перераспределения элементов, то есть добавить в узел элемент из левого или правого брата (не забыв обновить информацию в родителе). Если это невозможно, необходимо выполнить слияние с братом и удалить ключ, который указывает на удалённый узел. Объединение может распространяться на корень, тогда происходит уменьшение высоты дерева. Так как мы считаем, что в дереве не может находиться <tex>2 </tex> одинаковых ключей, то <tex>delete</tex> будет возвращать был ли удален ключ.

'''if''' left_sibling <tex>\neq</tex> null '''and''' left_sibling.key_num <tex>\small{\geqslant}</tex> t - 1

update(tec) <span style="color:#008000"> // Обновить ключи на пути к корню</span>

'''else if''' right_sibling <tex>\neq</tex> null '''and''' right_sibling.key_num <tex>\small{\geqslant}</tex> t - 1