Декартово дерево по неявному ключу

Материал из Викиконспекты
Перейти к: навигация, поиск
«

Декартово дерево правит миром. За логарифм.

»
— Неизвестный автор

Постановка задачи

Возьмем структуру данных вектор. В её стандартной реализации мы умеем добавить элемент в конец, узнать значение элемента и изменить элемент по номеру, и удалить последний элемент. Расширим круг задач: теперь мы хотим добавлять элемент в любое место (с соответствующим изменением нумерации элементов) и удалять любой элемент (с тем же самым уточнением). Теперь нам нужно придумать структуру, называемую Декартово дерево по неявному ключу, или же rope(англ.веревка).

Основная идея

Напомним, Декартово дерево — это структура данных, объединяющая в себе бинарное дерево поиска и бинарную кучу. Для решения задачи, поставленной в предыдущей главе, попробуем слегка модифицировать эту структуру. Если конкретнее, то оставим в нем только один ключ - ключ [math]Y[/math]. Вместо второго ключа будем использовать следующую величину: количество элементов в нашей структуре, находящихся левее нашего элемента. Если проще, то будем считать ключом порядковый номер нашего элемента в дереве, уменьшенный на единицу.

Заметим, что при этом сохранится структура двоичного дерева поиска по этому ключу(т.е. наше модифицированное декартово дерево так и останется декартовым деревом). Однако, с этим подходом появляется проблема: наши операции добавления и удаления элемента могут поменять нумерацию, и при наивной реализации на изменение всех ключей потребуется [math]O(n)[/math] времени, где [math]n[/math] — количество элементов в дереве.

Как же нам быть? Основная идея заключается в том, что такой ключ [math]X[/math] сам по себе нигде не хранится. Вместо него будем хранить вспомогательную величину: количество вершин в поддереве нашей вершины(включая и саму нашу вершину). Обратим внимание, что все операции с обычным декартовым деревом делались сверху. Также заметим, что если по пути до некой вершины просуммируем все такие величины в левых поддеревьях, в которые мы не пошли, увеличенные на единицу, то придя в саму вершину, мы получим как раз ее ключ [math]X[/math].