Изменения

Пусть <tex>\left \{ a_1,a_2\ldots a_ka_B\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>.

===Поиск следующего и предыдущегопо sketch===

Предположим, что Рассмотрим ключи. Порядок для них по <tex>psketch</tex> {{---}} наибольший общий префикс, а совпадает с их порядком. Тогда для некоторых <tex>ya_i</tex> его длина, и <tex>a_ja_{i+1}</tex> {{---}} ключ, имеющий наибольший общий префикс с : <tex>sketch(a_i) \leqslant sketch(q</tex> ) \leqslant sketch(<tex>j = i</tex> или <tex>a_{i+1</tex>}). * если <tex>q>a_j</tex>, то в таком случае <tex>y + 1a_i</tex> бит и <tex>q</tex> равен единице, а <tex>y a_{i+ 1}</tex> бит его <tex>a_j</tex> равен нулю. Так как общий префикс <tex>a_jsucc</tex> и <tex>qpred</tex> является наибольшим, то не существует ключа с префиксом по <tex>p1sketch</tex>. Значит, Тогда среди них есть настоящий (не по <tex>qsketch</tex> больше всех ключей с префиксом меньшим либо равным <tex>p</tex>. Найдем <tex>pred(e)</tex>, <tex>e = p01\ldots 11succ</tex>, который одновременно будет или <tex>равен pred(q)</tex>по доказанному,* если а понять это мы можем просто сделав сравнение с <tex>q<a_j</tex> {{---}} найдем <tex>succ(e)</tex>, <tex>e = p10\ldots 00</tex>. Это будет <tex>succ(q)</tex>.

Длина наибольшего общего префикса двух ===Поиск реального следующего и предыдущего===Мы умеем находить реальный <tex>wsucc</tex>-битных чисел и <tex>apred</tex> по <tex>succ</tex> и <tex>bpred</tex> от <tex>sketch(y)</tex> может быть вычислена с помощью нахождения индекса наиболее значащего бита в побитовом , теперь покажем, как искать <tex>\oplus asucc</tex> и <tex>bpred</tex> от <tex>sketch(y)</tex> за <tex> O(1)</tex>. ===Сравнение значений sketch двух чисел===Определим <tex>sketch(node)</tex> как число, составленное из единиц и <tex>sketch(a_i)</tex>, то есть <tex>sketch(node) = 1sketch(a_1)1sketch(a_2)\ldots 1sketch(a_k)</tex>. Вычтем из <tex>sketch(node)</tex> число <tex>sketch(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>\&</tex> c <tex>\displaystyle \sum_{i=0}^{k-1}2^{i(l+1)+l}</tex>, чтобы убрать лишние биты.

=== Индекс наиболее старшего бита с помощью цикла де Брёйна ===

==== Примеры ====

Примеры циклов де Брёйна для <math>k=2</math> с периодом <tex>2, 4, 8, 16</tex>:* <tex>01 </tex> (содержит подпоследовательности <tex>0 </tex> и <tex>1</tex>)* <tex>0011 </tex> (содержит подпоследовательности <tex>00, 01, 11, 10</tex>)* <tex>00010111 (000, 001, 010, 101, 011, 111, 110, 100)</tex>* <tex>0000100110101111</tex>

==== Получение индекса по значению степени двойки ====

Возьмем цикл де Брёйна для <tex>n</tex> <tex>(i = 0\ldots n-1)</tex> и запишем его как число <tex>b</tex> (для <tex>8</tex> цикл де Брёна равен <tex>00010111</tex>, а значение <tex>b = 23</tex>). Умножим это число на <tex>2^i</tex>, сдвинем его влево на <tex>i</tex>, а затем обратно вправо на <tex>n-k</tex> (<tex>k</tex> такое, что <tex>n=2^k</tex>). <tex>(b \ll texttt{<<} i)\ggtexttt{>>}(n-k)</tex>), тогда получившееся число {{---}} <tex>i</tex>-ая подстрока длины <tex>k</tex> данного цикла де Брёйна. Эту перестановку опозначим за <tex>p</tex> и тогда применив ее к <tex>(2^i\cdot x) \gg texttt{>>} (n-k))</tex> получим <tex>i</tex>: <tex>p</tex> в данном случае такое, что <tex>k</tex> подряд идущих бит равны значению, на сколько мы сдвинули, на какой позиции стоит вектор длины <tex>k</tex>.