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>L = (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>.
Теперь надо найти количество едениц в ''L''. Умножим ''L'' на <tex>\underbrace{0\ldots 01}_{l + 1 bits}\ldots \underbrace{0\ldots 01}_{l+1 bits}</tex>, тогда все еденицы сложатся в первом блоке результата, и, чтобы получить количество едениц, сдвинем его вправо.
===Succ(q) и pred(q)===
Пусть <tex>sketch(a_i) \leqslant sketch(q) \leqslant sketch(a_{i+1})</tex>.
