317
правок
Изменения
Пояснения к картинке
==Поиск вершины==
Пусть <tex>\left \{ a_1,a_2\ldots a_k\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>.
}}
Сравнивая <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 = 0, a_{i+1} = 1, q = 5</tex> ]]
Предположим, что <tex>p</tex> {{---}} наибольший общий префикс, а <tex>y</tex> его длина, <tex>a_j</tex> {{---}} ключ, имеющий наибольший общий префикс с <tex>q</tex> (<tex>j = i</tex> или <tex>i+1</tex>).
