317
правок
Изменения
→Поиск следующего и предыдущего
|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=
[[Файл:Fusion01.png|350x230px|thumb|right|Пример случая, когда наибольший общий префикс у <tex>q</tex> и <tex>a_i</tex>, а <tex>a_{i+1}</tex> не является ни <tex>succ</tex>, ни <tex>pred</tex>]]
Предположим, что <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>, что приводит к противоречию.
