Изменения

'''Fusion tree''' {{---}} дерево поиска, позволяющее хранить <tex>n</tex> <tex>w</tex>-битных чисел, используя <tex>O(n)</tex> памяти, и выполнять операции поиска за время <tex>O(\log_{w} n)</tex>. Эта структура данных была впервые предложенна предложена в 1990 году М. Фредманом (M. Fredman) и Д. Уиллардом (D. Willard).

Найдем <tex>succ(sketch(q))</tex> и <tex>pred(sketch(q))</tex>. Определим <tex>sketch(node)</tex> как число, составленное из едениц единиц и <tex>sketch(a_i)</tex>, то есть <tex>sketch(node) = 1sketch(a_1)1sketch(a_2)\ldots 1scetch(a_k)</tex>. Вычтем из <tex>sketch(node)</tex> число <tex>shetch(q) \times \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)</tex>. В начале каждого блока, где <tex>sketch(a_i) \geqslant sketch(q)</tex>, сохранятся еденицыединицы. Применим к получившемуся побитовое ''AND'' c <tex>\displaystyle \sum_{i=0}^{k-1}2^{i(l+1)+l}</tex>, чтобы убрать лишние биты.

Теперь надо найти количество едениц единиц в ''L''. Умножим ''L'' на <tex>\underbrace{0\ldots 01}_{l + 1 bits}\ldots \underbrace{0\ldots 01}_{l+1 bits}</tex>, тогда все еденицы единицы сложатся в первом блоке результата, и, чтобы получить количество еденицединиц, сдвинем его вправо.

ПедположимПредположим, что <tex>y</tex> имеет наибольший общий префикс с <tex>q</tex>. Тогда <tex>sketch(q)</tex> будет иметь больше общих битов со <tex>sketch(y)</tex>. Значит, <tex>sketch(y)</tex> ближе по значению к <tex>sketch(q)</tex>, чем <tex>sketch(a_i)</tex> или <tex>sketch(a_{i+1})</tex>, что приводит к противоречию.

Сравнивая <tex>a</tex> ''XOR'' <tex>\oplus q</tex> и <tex>b</tex> ''XOR'' <tex>\oplus q</tex>, найдем какой из ключей имеет наибольший общий префикс с <tex>q</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>;

Чтобы найти в w-битном числе <tex>x</tex> индекс самого старшего бита, содержащего еденицуединицу, разделим <tex>x</tex> на <tex>\sqrt{w}</tex> блоков по <tex>\sqrt{w}</tex> бит. <tex>x = \underbrace{0101}_{\sqrt{w}}\; \underbrace{0000}_{\sqrt{w}}\; \underbrace{1000}_{\sqrt{w}}\; \underbrace{1101}_{\sqrt{w}}</tex>. Далее найдем первый непустой блок и индекс первого еденичного единичного бита в нем.

'''a.''' Определим, какие блоки имеют еденицу единицу в первом бите. Применим побитовое ''AND'' к <tex>x</tex> и константе <tex>F</tex>.

'''b.''' Определим, содержат ли остальные биты еденицыединицы.

Вычислим <tex>x</tex> ''XOR'' <tex>\oplus t_1</tex>.

Вычтем от из <tex>F\; t_2</tex>. Если какой-нибудь бит <tex>F</tex> обнулится, значит, соответствующий блок содержит еденицыединицы.

Чтобы найти блоки, содержащие еденицыединицы, вычислим <tex>t_3</tex> ''XOR'' <tex>\oplus F</tex>.

'''c.''' Первый бит в каждом блоке <tex>y = t_1</tex> ''OR'' <tex>t_4</tex> содержит еденицуединицу, если соответствующий блок <tex>x</tex> ненулевой.

'''3)''' Найдем первый ненулевой блок. Для этого надо найти первую еденицу единицу в <tex>sketch(y)</tex>. Как и при поиске <tex>succ(sketch(q))</tex> и <tex>pred(sketch(q))</tex> используем параллельное сравнение <tex>sketch(y)</tex> с <tex>2^0, 2^1 \ldots 2^{\sqrt{w} - 1}</tex>. В результате сравнения получим номер первого ненулевого блока <tex>c</tex>.

'''4)''' Найдем номер <tex>d</tex> первого еденичного единичного бита в найденном блоке так же как и в предыдущем пункте.