234
правки
Изменения
→Поиск вершины
==Поиск вершины==
Пусть <tex>\left \{ a_1,a_2\ldots a_k\right \}</tex> - множество ключей узла, отсортированных по возрастанию, <tex>q</tex> - ключ искомой вершины, <tex>l</tex> - количество бит в <tex>sketch(q)</tex>. Сначала найдем такой ключ <tex>a_i</tex>, что <tex>sketch(a_i) \leqslant sketch(q) \leqslant sketch(a_{i+1})</tex>. Но положение <tex>sketch(q)</tex> среди <tex>sketch(a_j)</tex> не всегда эквивалентно положению <tex>q</tex> среди <tex>a_j</tex>, поэтому, зная соседние элементы <tex>sketch(q)</tex>, найдем <tex>succ(q)</tex> и <tex>pred(q)</tex>.
===Параллельное сравнение===
Сначала найдем <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>, сохранятся еденицы. Применим к получившемуся побитовое <tex>AND</tex> c <tex>\displaystyle \sum_{i=0}^{k-1}2^{i(l+1)+l}</tex>, чтобы убрать лишние биты.
Длина наибольшего общего префикса двух ''w''-битных чисел ''a'' и ''b'' может быть вычислена с помощью нахождения индекса наиболее значащего бита в побитовом <tex>XOR</tex> ''a'' и ''b''.
==Вычисление sketch(x)==
Чтобы найти sketch за константное время, будем вычислять <tex>sketch(x)</tex>, имеющий все существенные биты в нужном порядке, но содержащий лишние нули.
