Fusion tree

Fusion tree — дерево поиска, позволяющее хранить [math]n[/math] [math]w[/math]-битных положительных чисел, используя [math]O(n)[/math] памяти, и выполнять операции поиска за время [math]O(\log_{w} n)[/math].

Структура

Fusion tree — это B-дерево, такое что:

• у всех вершин, кроме листьев, [math]B = w^{1/5}[/math] детей;
• время, за которое определяется в каком поддереве находится вершина, равно [math]O(1)[/math].

Такое время работы достигается за счет хранения дополнительной информации в вершинах. Рассмотрим цифровой бор из ключей узла дерева. Всего [math]B - 1[/math] ветвящихся вершин. Биты, соответствующие уровням дерева, в которых происходит ветвление, назовем существенными и обозначим их номера [math]b_1, b_2\ldots b_r[/math]. Количество существенных битов [math]r[/math] не больше чем [math]B - 1[/math].

В Fusion tree вместо ключа [math]x[/math] хранится [math]Sketch(x)[/math] - последовательность битов [math]x_{b_r}\ldots x_{b_1}[/math]. [math]Sketch[/math] сохраняет порядок, то есть [math]sketch(x) \lt sketch(y)[/math], если [math]x \lt y[/math].

Обозначим [math]rank_s u = |\{ t | t\in S, t\leqslant u\}|[/math], [math]sketch(x) = \hat x[/math], [math]S[/math] - множество ключей вершины.

Поиск вершины

Пусть [math]\left \{ a_1,a_2\ldots a_k\right \}[/math] - множество ключей узла, [math]q[/math] - ключ искомой вершины, [math]l[/math] - количество бит в [math]sketch(q)[/math]. Определим [math]sketch(node)[/math] как число, составленное из едениц и [math]sketch(a_i)[/math], то есть [math]sketch(node) = 1sketch(a_1)1sketch(a_2)\ldots 1scetch(a_k)[/math]. Вычтем из [math]sketch(node)[/math] число [math]shetch(q) * \underbrace{\overbrace{00\ldots 1}^{l + 1 bits}\overbrace{00\ldots 1}^{l + 1 bits}\ldots \overbrace{00\ldots 1}^{l + 1 bits}}_{k(l + 1) bits} = 0sketch(q)\ldots 0sketch(q)[/math]. Применим к получившемуся побитовое AND c [math]\displaystyle \sum_{i=0}^{k-1}2^{i(l+1)+l}[/math], чтобы убрать лишние биты.

[math](1sketch(a_1)\ldots 1scetch(a_k) - 0sketch(q)\ldots 0sketch(q))[/math] AND [math]\displaystyle \sum_{i=0}^{k-1}2^{i(l+1)+l}=\overbrace{c_10\ldots0}^{l+1 bits} \ldots \overbrace{c_k0\ldots0}^{l+1 bits}[/math]

Если [math]sketch(a_i)\lt sketch(q)[/math], то [math]c_i = 0[/math], в противном случае [math]c_i = 1[/math].