317
правок
Изменения
→Поиск следующего и предыдущего
|author=
|about=
|statement=Пусть Среди значений <tex>sketchsucc(a_iy) \leqslant sketch</tex> и <tex>pred(qy) \leqslant </tex> по <tex>sketch(a_{i+1}y)</tex>. Тогда среди всех ключей наибольший общий префикс с есть <tex>qsucc</tex> будет иметь или <tex>a_ipred</tex> или по значению <tex>a_{i+1}y</tex>.
|proof=
Рассмотрим <tex>y</tex>. У него есть существенные биты и некоторый элемент <tex>x</tex>, с которым у <tex>y</tex> наибольший общий префикс (настоящий, а не по <tex>sketch</tex>). Биты из <tex>sketch</tex>, находящиеся в префиксе совпадают, значит <tex>succ</tex> и <tex>pred</tex> <tex>y</tex> среди <tex>sketch</tex> должны быть такими же среди <tex>x</tex>, и один из них имеет дальше бит <tex>0</tex> (а другой <tex>1</tex>) и с ним может быть больше других общих бит в <tex>sketch</tex>. То есть либо <tex>succ</tex>, либо <tex>pred</tex> имеют следующий существенный бит такой же, как и у <tex>y</tex>. Поэтому если значение равно <tex>0</tex>, то <tex>x</tex> наибольший среди значений с меньшим <tex>sketch</tex>, и, аналогично для <tex>1</tex>, наименьший среди больших.
}}
[[Файл:Fusion01.png|350x230px|thumb|right|Пример случая, когда наибольший общий префикс у <tex>qsucc(y)</tex> и <tex>a_ipred(y)</tex>, а по <tex>a_{i+1}sketch(y)</tex> не является ни являются <tex>succ</tex>, ни или <tex>pred</tex> по <tex>y</tex>]]
Сравнивая <tex>a \oplus q</tex> и <tex>b \oplus q</tex>, найдем какой из ключей <tex>a</tex> и <tex>b</tex> имеет наибольший общий префикс с <tex>q</tex> (наименьшее значение соответствует наибольшей длине, так как одинаковые старшие биты обнулятся, следовательно, если <tex>a \oplus q > b \oplus q</tex>, то у <tex>a</tex> первый несовпадающий бит старше, чем у <tex>b</tex> ).
