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