Изменения

|statement=Пусть <tex>sketch(a_i) \leqslant sketch(q) \leqslant sketch(a_{i+1})</tex>. Тогда среди всех ключей наибольший общий префикс с <tex>q</tex> будет иметь или <tex>a_i</tex> или <tex>a_{i+1}</tex>.

|proof=

Предположим, что <tex>y</tex> имеет наибольший общий префикс с <tex>q</tex>. Тогда <tex>sketch(q)</tex> будет иметь больше общих битов со <tex>sketch(y)</tex>. Значит, <tex>sketch(y)</tex> ближе по значению к <tex>sketch(q)</tex>, чем <tex>sketch(a_i)</tex> или <tex>sketch(a_{i+1})</tex>, что приводит к противоречию.

Рассмотрим <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>, наименьший среди больших.

}}

Сравнивая <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> ).