317
правок
Изменения
→Поиск следующего и предыдущего по sketch
[[Файл: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> ]]
Рассмотрим ключи. Порядок для них по <tex>sketch</tex> совпадает с их порядком. Тогда для некоторых <tex>a_i</tex> и <tex>a_{i+1}</tex>: <tex>sketch(a_i) \leqslant sketch(q) \leqslant sketch(a_{i+1})</tex>, в таком случае <tex>a_i</tex> и <tex>a{i+1}</tex> его <tex>succ</tex> и <tex>pred</tex> по <tex>sketch</tex>. В таком случае среди них есть реальный <tex>succ</tex> или <tex>pred</tex> по доказанному, а понять, чем именно он является, это мы можем просто сделав сравнение с <tex>q</tex>.
===Поиск реального следующего и предыдущего===
