286
правок
Изменения
Нет описания правки
=== Структура узла ===
'''struct''' Node
'''bool''' leaf <span style="color:#008000"> // является ли узел листом</span> '''int''' key_num <span style="color:#008000"> // количество ключей узла</span> '''int''' key[] <span style="color:#008000"> // ключи узла</span> '''Node''' p parent <span style="color:#008000"> // указатель на отца</span> '''Node''' cchild[] <span style="color:#008000"> // указатели на детей узла</span> '''Info''' pointers[] <span style="color:#008000">// если лист {{---}} указатели на данные</span> '''Node''' next <span style="color:#008000"> // указатели на следующий элемент (для внутренних вершин = null)узел</span>
=== Структура дерева ===
'''struct''' BPlusTree
'''int''' t <span style="color:#008000"> // минимальная степень дерева</span> '''Node''' root <span style="color:#008000"> // указатель на корень дерева</span>
== Оценка высоты дерева ==
B<tex>^{+}</tex>-деревья являются сбалансированными, поэтому время выполнения стандартных операций в них пропорционально высоте.
'''Node''' findfind_leaf(T: '''BPlusTree''', k: '''int'''): Node now = T.root
'''while''' !now.leaf
'''for''' i = 0 '''to''' keynow.numkey_num
'''if''' i == now.key_num '''or''' key < now.key[i]
now = now.ch[i]
'''break'''
'''return''' now
=== Поиск ===
Находим нужный лист через <tex>find</tex>_<tex>leaf</tex> и ищем нужный ключ в нем
== Добавление ключа ==
Ищем лист, в который можно добавить ключ и добавляем его в список ключей. Если узел не заполнен, то добавление завершено. Иначе разбиваем узел на два узла, в первый добавляем первые <tex>t - 1</tex> ключей, во второй оставшиеся <tex>t</tex>. Первый ключ их второго узла копируется в родительский узел, где становится разделительной точкой для двух новых поддеревьев.
Если и родительский узел заполнен {{---}} поступаем аналогично, но не копируем, а перемещаем ключ в родительский узел, так как это просто копия. Повторяем пока не встретим незаполненный узел или не дойдем до корня. В последнем случае корень разбивается на два узла и высота дерева увеличивается. Будем считать, что в дереве не может находиться 2 одинаковых ключа, поэтому <tex>insert</tex> будет возвращать был ли добавлен ключ.
'''void''' insert(T: '''BPlusTree''', key: '''Node''', value: '''Info'''):
leaf = find_key(T, key)
'''for''' i = 0 '''to''' leaf.key_num
'''if''' key == leaf.key[i]
'''return false'''
pos = 0
'''while''' pos < leaf.key_num '''and''' leaf.key[pos] < key
++pos
'''for''' i = leaf.key_num '''downto''' pos + 1
leaf.key[i] = leaf.key[i-1]
'''for''' i = leaf.key_num + 1 '''downto''' pos + 2
leaf.pointers[i] = leaf.pointer[i-1]
leaf.key[pos] = key
leaf.pointers[x + 1] = value
++leaf.key_num
'''if''' leaf.key_num == M <span style="color:#008000"> // M - степень дерева</span>
split(T, leaf)
== Примeчания ==
<references/>
