234
правки
Изменения
Нет описания правки
Такое время работы достигается за счет хранения дополнительной информации в вершинах. Рассмотрим цифровой бор из ключей узла дерева. Всего <tex>B - 1</tex> ветвящихся вершин. Биты, соответствующие уровням дерева, в которых происходит ветвление, назовем существенными и обозначим их номера <tex>b_1, b_2\ldots b_r</tex>. Количество существенных битов <tex>r</tex> не больше чем <tex>B - 1</tex>.
В Fusion tree вместо ключа вместе с ключом <tex>x</tex> хранится <tex>Sketch(x)</tex> - последовательность битов <tex>x_{b_r}\ldots x_{b_1}</tex>. <tex>Sketch</tex> сохраняет порядок, то есть <tex>sketch(x) < sketch(y)</tex>, если <tex>x < y</tex>.
==Поиск вершины==
