Изменения
→Основная идея
==Основная идея==
Возьмем структуру данных [[Саморасширяющийся массив|вектор]]. В её стандартной реализации мы умеем добавлять элемент в конец вектора, узнавать значение элемента, стоящего на определенной позиции, изменять элемент по номеру и удалять последний элемент. Предположим, что нам необходима структура данных с вышеуказанными свойствами, а также с операциями: добавить элемент в любое место (с соответствующим изменением нумерации элементов) и удалить любой элемент (также с соответствующим изменением нумерации). Такая структура существует и называется Такую структуру можно реализовать на базе декартового дерева, результат часто называют ''декартово дерево по неявному ключу''.
===Ключ X===
Как известно, [[декартово дерево]] {{---}} это структура данных, объединяющая в себе бинарное дерево поиска и бинарную кучу. При реализации же декартова дерева по неявному ключу модифицируем эту структуру. А именно, оставим в нем только приоритет <tex>Y</tex>, а вместо ключа <tex>X</tex> будем использовать следующую величину: '''количество элементов в нашей структуре, находящихся левее нашего элемента'''. Иначе говоря, будем считать ключом порядковый номер нашего элемента в дереве, уменьшенный на единицу.
[[Файл:DDpoNK.png|Пример описанного дерева с демонстрацией определения ключа <tex>X</tex>]]
==Операции, поддерживающие структуру декартова дерева==
