317
правок
Изменения
м
→Понятия succ(q) и pred(q)
Сравнивая <tex>a \oplus q</tex> и <tex>b \oplus q</tex>, найдем какой из ключей имеет наибольший общий префикс с <tex>q</tex> (наименьшее значение соответствует наибольшей длине).
[[Файл:FusionTree.png|400x400px|thumb|right|Пример случая, когда <tex>sketch(a_i) \leqslant sketch(q) \leqslant sketch(a_{i+1})</tex>, но <tex>a_{i+1}\leqslant q</tex> <tex>sketch(a_i) = 00, sketch(q) = 00, sketch(a_{i+1}) = 01, \\ a_i = 00000, a_{i+1} = 10010, q = 50101</tex> ]]
Предположим, что <tex>p</tex> {{---}} наибольший общий префикс, а <tex>y</tex> его длина, <tex>a_j</tex> {{---}} ключ, имеющий наибольший общий префикс с <tex>q</tex> (<tex>j = i</tex> или <tex>i+1</tex>).
