Изменения

Перейти к: навигация, поиск

Fusion tree

571 байт убрано, 23:10, 6 июня 2015
Поиск следующего и предыдущего
}}
[[Файл:Fusion01.png|350x230px|thumb|right|Пример случая, когда <tex>succ(y)</tex> и <tex>pred(y)</tex> по <tex>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> ).
[[Файл: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 = 0000, a_{i+1} = 0010, q = 0101</tex> ]]
317
правок

Навигация