286
правок
Изменения
Нет описания правки
'''struct''' Node
'''bool''' leaf <span style="color:#008000"> // является ли узел листом</span>
'''int''' n key_num <span style="color:#008000"> // количество ключей узла</span>
'''int''' key[] <span style="color:#008000"> // ключи узла</span>
'''Node''' p <span style="color:#008000"> // указатель на отца</span>
'''Node''' c[] <span style="color:#008000"> // указатели на детей узла</span>
'''Node''' next <span style="color:#008000"> // указатели на следующий элемент (для внутренних вершин = null)</span>
}}
Как можно заметить, высота B<tex>^{+}</tex>-дерева не более чем на 1 отличается от [[B-дерево#Высота|высоты B-дерева]], то есть хранение значений информации только в листах почти не ухудшает эффективность дерева == Операции ==B<tex>^{+}</tex>-деревья являются сбалансированными, поэтому время выполнения стандартных операций в них пропорционально высоте. === Поиск === Определяем интервал и переходим к соответствующему сыну. Повторяем пока не дошли до листа. '''Node''' find(T: '''BPlusTree''', k: '''int'''): Node now = T.root '''while''' !now.leaf '''for''' i = 0 '''to''' key.num '''if''' i == now.key_num '''or''' key < now.key[i] now = now.ch[i] '''break''' '''return''' now
== Примeчания ==
<references/>
