Изменения
Нет описания правки
==Структура==
Fusion tree {{---}} это [[B-дерево|B-дерево]], такое что:
* у всех вершин, кроме листьев, <tex>B = w^{1/5}</tex> детей;,
* время, за которое определяется, в каком поддереве находится вершина, равно <tex>O(1)</tex>.
Такое время работы достигается за счет хранения дополнительной информации в вершинах. Построим цифровой бор из ключей узла дерева. Всего <tex>B - 1</tex> ветвящихся вершин. Биты, соответствующие уровням дерева, в которых происходит ветвление, назовем существенными и обозначим их номера <tex>b_0, b_2\ldots b_{r-1}</tex>. Количество существенных битов <tex>r</tex> не больше чем <tex>B - 1</tex>.
Предположим, что <tex>p</tex> {{---}} наибольший общий префикс, а <tex>y</tex> его длина, <tex>a_j</tex> {{---}} ключ, имеющий наибольший общий префикс с <tex>q</tex> (<tex>j = i</tex> или <tex>i+1</tex>).
* если <tex>q>a_j</tex>, то <tex>y + 1</tex> бит <tex>q</tex> равен единице, а <tex>y + 1</tex> бит <tex>a_j</tex> равен нулю. Так как общий префикс <tex>a_j</tex> и <tex>q</tex> является наибольшим, то не существует ключа с префиксом <tex>p1</tex>. Значит, <tex>q</tex> больше всех ключей с префиксом меньшим либо равным <tex>p</tex>. Найдем <tex>pred(e)</tex>, <tex>e = p01\ldots 11</tex>, который одновременно будет <tex>равен pred(q)</tex>;,
* если <tex>q<a_j</tex> {{---}} найдем <tex>succ(e)</tex>, <tex>e = p10\ldots 00</tex>. Это будет <tex>succ(q)</tex>.
Чтобы найти sketch за константное время, будем вычислять <tex>sketch(x)</tex>, имеющий все существенные биты в нужном порядке, но содержащий лишние нули.
1) уберем все несущественные биты <tex>x' = x \land \displaystyle \sum_{i=0}^{r-1}2^{b_i}</tex>;,
2) умножением на некоторое заранее вычисленное число <tex>M = \displaystyle\sum_{i=0}^{r-1}2^{m_i}</tex> сместим все существенные биты в блок меньшего размера.
<tex>x'\times M = \displaystyle(\sum_{i=0}^{r-1}x_{b_i}2^{b_i})(\sum_{i=0}^{r-1}2^{m_i}) = \sum_{i=0}^{r-1}\sum_{j=0}^{r-1}x_{b_i}2^{b_i+m_j}</tex>;,
3) применив побитовое <tex>\land</tex>, уберем лишние биты, появившиеся в результате умножения;,
<tex>\displaystyle\sum_{i=0}^{r-1}\sum_{j=0}^{r-1}x_{b_i}2^{b_i+m_j} \land \displaystyle\sum_{i=0}^{r-1}2^{b_i+m_i} = \sum_{i=0}^{r-1}x_{b_i}2^{b_i+m_i}</tex>;,
4) сделаем сдвиг вправо на <tex>m_0 + b_0</tex> бит.
