234
правки
Изменения
Новая страница: «'''Fusion tree''' {{---}} дерево поиска, позволяющее хранить <tex>n</tex> <tex>w</tex>-битных положительных чи...»
'''Fusion tree''' {{---}} дерево поиска, позволяющее хранить <tex>n</tex> <tex>w</tex>-битных положительных чисел, используя <tex>O(n)</tex> памяти, и выполнять операции поиска за время <tex>O(\log_{w} n)</tex>.
==Структура==
Fusion tree {{---}} это [[B-дерево|B-дерево]], такое что:
* у всех вершин, кроме листьев, <tex>B = w^{1/5}</tex> детей;
* время, за которое определяется в каком поддереве находится вершина, равно <tex>O(1)</tex>.
Такое время работы достигается за счет хранения дополнительной информации в вершинах. Рассмотрим цифровой бор из ключей узла дерева. Всего <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>.
Обозначим <tex>rank_s u = |\{ t | t\in S, t\leqslant u\}|</tex>, <tex>sketch(x) = \hat x</tex>, <tex>S</tex> - множество ключей вершины.
==Поиск вершины==
Пусть <tex>\left \{ a_1,a_2\ldots a_k\right \}</tex> - множество ключей узла, <tex>q</tex> - ключ искомой вершины, <tex>l</tex> - количество бит в <tex>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) * \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>. Применим к получившемуся побитовое ''AND'' c <tex>\displaystyle \sum_{i=0}^{k-1}2^{i(l+1)+l}</tex>, чтобы убрать лишние биты.
<tex>(1sketch(a_1)\ldots 1scetch(a_k) - 0sketch(q)\ldots 0sketch(q))</tex> ''AND'' <tex>\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}</tex>
Если <tex>sketch(a_i)< sketch(q)</tex>, то <tex>c_i = 0</tex>, в противном случае <tex>c_i = 1</tex>.
==Структура==
Fusion tree {{---}} это [[B-дерево|B-дерево]], такое что:
* у всех вершин, кроме листьев, <tex>B = w^{1/5}</tex> детей;
* время, за которое определяется в каком поддереве находится вершина, равно <tex>O(1)</tex>.
Такое время работы достигается за счет хранения дополнительной информации в вершинах. Рассмотрим цифровой бор из ключей узла дерева. Всего <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>.
Обозначим <tex>rank_s u = |\{ t | t\in S, t\leqslant u\}|</tex>, <tex>sketch(x) = \hat x</tex>, <tex>S</tex> - множество ключей вершины.
==Поиск вершины==
Пусть <tex>\left \{ a_1,a_2\ldots a_k\right \}</tex> - множество ключей узла, <tex>q</tex> - ключ искомой вершины, <tex>l</tex> - количество бит в <tex>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) * \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>. Применим к получившемуся побитовое ''AND'' c <tex>\displaystyle \sum_{i=0}^{k-1}2^{i(l+1)+l}</tex>, чтобы убрать лишние биты.
<tex>(1sketch(a_1)\ldots 1scetch(a_k) - 0sketch(q)\ldots 0sketch(q))</tex> ''AND'' <tex>\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}</tex>
Если <tex>sketch(a_i)< sketch(q)</tex>, то <tex>c_i = 0</tex>, в противном случае <tex>c_i = 1</tex>.
