170
правок
Изменения
м
→Визуализация работы с гипотетически оптимальным динамическим двоичным деревом поиска
Докажем, что можно построить такое дерево, для которого наши точки будут соответствовать запросам.
Рассмотрим наше множество точек.
Построим из них [http://neerc.ifmo.ru/wiki/index.php?title=Декартово_дерево декартово(!) дерево], где ключом будет ключ, а вспомогательным ключом {{---}} время, когда мы следующий раз обратимся к вершине, то есть для каждого <tex>x</tex> найдем минимальный <tex>y</tex> такой, что существует точка <tex>(x, y)</tex>
[[Файл:DariaPicture3.png|thumb|300px| Построение декартова дерева
