234
правки
Изменения
Нет описания правки
'''Fusion tree''' {{---}} дерево поиска, позволяющее хранить <tex>n</tex> <tex>w</tex>-битных положительных чисел, используя <tex>O(n)</tex> памяти, и выполнять операции поиска за время <tex>O(\log_{w} n)</tex>. Эта структура данных была впервые предложенна в 1990 году М. Фредманом (M. Fredman) и Д. Уиллардом (D. Willard).
==Структура==
Fusion tree {{---}} это [[B-дерево|B-дерево]], такое что:
3) <tex>(b_{r-1} + m_{r-1}) - (b_0 + m_0) \leqslant r^4</tex>.
|proof=
Выберем некоторые<tex>m_i'</tex>, таким образом, чтобы<tex>m_i' + b_k not\equiv m_j' + b_p</tex>. Предположим, что мы выбрали<tex>m_1' \ldots m_{t-1}'</tex>. mtТогда <tex>m_t' != mi\ne m_i' + bj b_j - bk A b_k \; \forall i,j,k. В противном случае </tex>. Всего <tex>t*\times r*\times r <= r^3 </tex> недопустимых значений для mt<tex>m_t'</tex>, поэтому всегда можно найти хотя бы одно значение.
Чтобы получить mi<tex>m_i</tex>, выбираем каждый раз наименьшие miнаименьшее <tex>m_i' </tex> и прибавляем подходящее число кратное <tex>r^3</tex>, такое что mi<tex>m_i+cic_i <mim_{i+l1}+Cic_{i+l<=mi1} \leqslant m_i+cic_i+r3r^3</tex>.
}}
Первые два условия необходимы для того, чтобы сохранить все существенные биты в нужном порядке. Третье условие позволит поместить sketch узла в w-битный тип. Так как r<=B-1, то sketch(node) будет занимать B*(r*4 + 1) <= B*((B-1)^4 + 1) <= B^5 = (w^{1/5})^5 = w бит.
