Декартово дерево по неявному ключу — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
Строка 2: Строка 2:
  
 
==Постановка задачи==
 
==Постановка задачи==
Возьмем структуру данных ''[[Саморасширяющийся массив|вектор]]''. В её стандартной реализации мы умеем добавить элемент в конец, узнать значение элемента и изменить элемент по номеру, и удалить последний элемент. Расширим круг задач: теперь мы хотим добавлять элемент в любое место (с соответствующим изменением нумерации элементов) и удалять любой элемент (с тем же самым уточнением). Теперь нам нужно придумать структуру, называемую ''Декартово дерево по неявному ключу'', или же ''rope'' (''англ.веревка'').
+
Возьмем структуру данных '''[[Саморасширяющийся массив|вектор]]'''. В её стандартной реализации мы умеем добавить элемент в конец, узнать значение элемента и изменить элемент по номеру, и удалить последний элемент. Расширим круг задач: теперь мы хотим добавлять элемент в любое место (с соответствующим изменением нумерации элементов) и удалять любой элемент (с тем же самым уточнением). Теперь нам нужно придумать структуру, называемую '''Декартово дерево по неявному ключу''', или же '''rope'''(''англ.'''веревка''''').
  
 
==Основная идея==
 
==Основная идея==
 
[[Файл:Tree_1.png|right|250px|thumb|Пример описанного дерева с демонстрацией определения ключа <tex>X</tex>]]
 
[[Файл:Tree_1.png|right|250px|thumb|Пример описанного дерева с демонстрацией определения ключа <tex>X</tex>]]
Напомним, ''[[Декартово дерево]]'' {{---}} это структура данных, объединяющая в себе бинарное дерево поиска и бинарную кучу. Для решения задачи, поставленной в предыдущей главе, попробуем слегка модифицировать эту структуру. Если конкретнее, то оставим в нем только один ключ - ключ <tex>Y</tex>. Вместо второго ключа будем использовать следующую величину: ''количество элементов в нашей структуре, находящихся левее нашего элемента''. Если проще, то будем считать ключом порядковый номер нашего элемента в дереве, уменьшенный на единицу.  
+
Напомним, '''[[Декартово дерево]]''' {{---}} это структура данных, объединяющая в себе бинарное дерево поиска и бинарную кучу. Для решения задачи, поставленной в предыдущей главе, попробуем слегка модифицировать эту структуру. Если конкретнее, то оставим в нем только один ключ - ключ <tex>Y</tex>. Вместо второго ключа будем использовать следующую величину: '''количество элементов в нашей структуре, находящихся левее нашего элемента'''. Если проще, то будем считать ключом порядковый номер нашего элемента в дереве, уменьшенный на единицу.  
  
 
Заметим, что при этом сохранится структура [[Дерево_поиска,_наивная_реализация|двоичного дерева поиска]] по этому ключу(т.е. наше модифицированное декартово дерево так и останется декартовым деревом). Однако, с этим подходом появляется проблема: наши операции добавления и удаления элемента могут поменять нумерацию, и при наивной реализации на изменение всех ключей потребуется <tex>O(n)</tex> времени, где <tex>n</tex> {{---}} количество элементов в дереве.
 
Заметим, что при этом сохранится структура [[Дерево_поиска,_наивная_реализация|двоичного дерева поиска]] по этому ключу(т.е. наше модифицированное декартово дерево так и останется декартовым деревом). Однако, с этим подходом появляется проблема: наши операции добавления и удаления элемента могут поменять нумерацию, и при наивной реализации на изменение всех ключей потребуется <tex>O(n)</tex> времени, где <tex>n</tex> {{---}} количество элементов в дереве.
  
Как же нам быть? Основная идея заключается в том, что такой ключ <tex>X</tex> сам по себе нигде не хранится. Вместо него будем хранить вспомогательную величину <tex>C</tex>: ''количество вершин в поддереве нашей вершины''(в поддерево включается и сама вершину). Обратим внимание, что все операции с обычным декартовым деревом делались сверху. Также заметим, что если по пути до некой вершины просуммируем все такие величины в левых поддеревьях, в которые мы не пошли, увеличенные на единицу, то придя в саму вершину и добавив к этой величине количество элементов в её левом поддереве, мы получим как раз ее ключ <tex>X</tex>.
+
Как же нам быть? Основная идея заключается в том, что такой ключ <tex>X</tex> сам по себе нигде не хранится. Вместо него будем хранить вспомогательную величину <tex>C</tex>: '''количество вершин в поддереве нашей вершины'''(в поддерево включается и сама вершину). Обратим внимание, что все операции с обычным декартовым деревом делались сверху. Также заметим, что если по пути до некой вершины просуммируем все такие величины в левых поддеревьях, в которые мы не пошли, увеличенные на единицу, то придя в саму вершину и добавив к этой величине количество элементов в её левом поддереве, мы получим как раз ее ключ <tex>X</tex>.
  
 
==Операции, поддерживающие структуру декартова дерева==
 
==Операции, поддерживающие структуру декартова дерева==
Структура обычного декартова дерева поддерживается с помощью двух операций: ''split'' {{---}} разбиение одного декартова дерева  на два таких, что в одном ключ <tex>X</tex> меньше, чем заданное значение, а в другом {{---}} больше, и ''merge'' {{---}} слияние двух деревьев, в одном из которых все ключи <tex>X</tex> меньше, чем во втором. С учетом отличий декартова дерева по неявному ключу от обычного, операции теперь будут описываться так: разбиение дерева на два так, что в левом окажется ровно <tex>t</tex> вершин, и слияние двух любых деревьев.
+
Структура обычного декартова дерева поддерживается с помощью двух операций: '''split''' {{---}} разбиение одного декартова дерева  на два таких, что в одном ключ <tex>X</tex> меньше, чем заданное значение, а в другом {{---}} больше, и '''merge''' {{---}} слияние двух деревьев, в одном из которых все ключи <tex>X</tex> меньше, чем во втором. С учетом отличий декартова дерева по неявному ключу от обычного, операции теперь будут описываться так: разбиение дерева на два так, что в левом окажется ровно <tex>t</tex> вершин, и слияние двух любых деревьев.
  
 
===Split===
 
===Split===
Пусть процедура ''split'' запущена в корне дерева с требованием отрезать от дерева <tex>t</tex> вершин. Также известно, что в левом поддереве вершины находится <tex>l</tex> вершин, а в правом <tex>r</tex>. Рассмотрим сначала два тривиальных случая. Первый: <tex>l = t</tex>. В этом случае процедура ''split'' должна просто пометить, что у корня больше нет левого сына, и вернуть его бывшего левого сына в качестве левого ответа, а сам корень {{---}} в качестве правого. Второй крайний случай (<tex>t = l + 1</tex>) рассматривается аналогично. Следующий случай не так тривиален: <tex>t < l</tex>. В этом случае нужно рекурсивно запустить процедуру ''split'' от левого сына с тем же параметром <tex>t</tex>, и левая часть сына станет левым ответом нашей процедуры, а правая часть станет левым сыном корня, после чего корень станет правым ответом. Случай <tex>t > l + 1</tex> рассматривается аналогично, с той лишь разницей, что от правого сына отрезается <tex>t - l - 1</tex> вершин.
+
Пусть процедура '''split''' запущена в корне дерева с требованием отрезать от дерева <tex>t</tex> вершин. Также известно, что в левом поддереве вершины находится <tex>l</tex> вершин, а в правом <tex>r</tex>. Рассмотрим сначала два тривиальных случая. Первый: <tex>l = t</tex>. В этом случае процедура '''split''' должна просто пометить, что у корня больше нет левого сына, и вернуть его бывшего левого сына в качестве левого ответа, а сам корень {{---}} в качестве правого. Второй случай (<tex>t = l + 1</tex>) рассматривается аналогично. Следующий случай не так тривиален: <tex>t < l</tex>. В этом случае нужно рекурсивно запустить процедуру '''split''' от левого сына с тем же параметром <tex>t</tex>, и левая часть сына станет левым ответом нашей процедуры, а правая часть станет левым сыном корня, после чего корень станет правым ответом. Случай <tex>t > l + 1</tex> рассматривается аналогично, с той лишь разницей, что от правого сына отрезается <tex>t - l - 1</tex> вершин.
  
 
===Merge===
 
===Merge===
Посмотрим любую из реализаций процедуры ''merge''. Заметим, что в ней программа ни разу не обращается к ключу <tex>X</tex>. Поэтому реализация процедуры ''merge'' для декартова дерева по неявному ключу вообще не будет отличаться от реализации той же процедуры в обычном декартовом дереве.
+
Посмотрим любую из реализаций процедуры '''merge'''. Заметим, что в ней программа ни разу не обращается к ключу <tex>X</tex>. Поэтому реализация процедуры '''merge''' для декартова дерева по неявному ключу вообще не будет отличаться от реализации той же процедуры в обычном декартовом дереве.
  
===Поддержание корректности значений <tex>С</tex>===
+
===Поддержание корректности ключей <tex>X</tex>===
Единственное действие, обеспечивающее корректность этих значений заключается в том, что после любого действия с детьми вершины нужно записать в ее поле <tex>С</tex> сумму этих полей в ее новых детях, увеличенную на единицу.
+
Единственное действие, обеспечивающее корректность этих ключей заключается в том, что после любого действия с детьми вершины нужно записать в ее ключ <tex>X</tex> сумму этих ключей в ее новых детях, увеличенную на единицу.
  
 
==Применение описанного дерева==
 
==Применение описанного дерева==
Строка 29: Строка 29:
 
* переставить любой кусок массива куда угодно (сделаем нужные разрезы и слияния в правильном порядке)
 
* переставить любой кусок массива куда угодно (сделаем нужные разрезы и слияния в правильном порядке)
 
* совершать групповые операции с элементами. Вспомним реализацию таких операций в дереве отрезков и поймем, что ничего не помешает нам сделать то же самое с описанным деревом. В групповые операции включается, естественно, и взятие функции от отрезка.
 
* совершать групповые операции с элементами. Вспомним реализацию таких операций в дереве отрезков и поймем, что ничего не помешает нам сделать то же самое с описанным деревом. В групповые операции включается, естественно, и взятие функции от отрезка.
* сделав на одном исходном массиве два дерева из элементов разной четности, можно поизвращаться со сменой мест четных и нечетных на отрезке (одно из домашних заданий)
+
* сделав на одном исходном массиве два дерева из элементов разной четности, можно решить задачу про смену мест четных и нечетных на отрезке (одно из домашних заданий)
 
* повелевать миром
 
* повелевать миром

Версия 22:21, 7 июня 2011

«

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

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

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

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

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

Пример описанного дерева с демонстрацией определения ключа [math]X[/math]

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

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

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

Операции, поддерживающие структуру декартова дерева

Структура обычного декартова дерева поддерживается с помощью двух операций: split — разбиение одного декартова дерева на два таких, что в одном ключ [math]X[/math] меньше, чем заданное значение, а в другом — больше, и merge — слияние двух деревьев, в одном из которых все ключи [math]X[/math] меньше, чем во втором. С учетом отличий декартова дерева по неявному ключу от обычного, операции теперь будут описываться так: разбиение дерева на два так, что в левом окажется ровно [math]t[/math] вершин, и слияние двух любых деревьев.

Split

Пусть процедура split запущена в корне дерева с требованием отрезать от дерева [math]t[/math] вершин. Также известно, что в левом поддереве вершины находится [math]l[/math] вершин, а в правом [math]r[/math]. Рассмотрим сначала два тривиальных случая. Первый: [math]l = t[/math]. В этом случае процедура split должна просто пометить, что у корня больше нет левого сына, и вернуть его бывшего левого сына в качестве левого ответа, а сам корень — в качестве правого. Второй случай ([math]t = l + 1[/math]) рассматривается аналогично. Следующий случай не так тривиален: [math]t \lt l[/math]. В этом случае нужно рекурсивно запустить процедуру split от левого сына с тем же параметром [math]t[/math], и левая часть сына станет левым ответом нашей процедуры, а правая часть станет левым сыном корня, после чего корень станет правым ответом. Случай [math]t \gt l + 1[/math] рассматривается аналогично, с той лишь разницей, что от правого сына отрезается [math]t - l - 1[/math] вершин.

Merge

Посмотрим любую из реализаций процедуры merge. Заметим, что в ней программа ни разу не обращается к ключу [math]X[/math]. Поэтому реализация процедуры merge для декартова дерева по неявному ключу вообще не будет отличаться от реализации той же процедуры в обычном декартовом дереве.

Поддержание корректности ключей [math]X[/math]

Единственное действие, обеспечивающее корректность этих ключей заключается в том, что после любого действия с детьми вершины нужно записать в ее ключ [math]X[/math] сумму этих ключей в ее новых детях, увеличенную на единицу.

Применение описанного дерева

Что же мы получили? У нас есть структура, от которой можно отрезать слева кусок произвольной длины и слить два любых куска в один в нужном порядке. Теперь мы можем:

  • вставить элемент в любое место (отрежем нужное количество слева, сольем левое дерево с деревом из одного добавленного элемента и результат — с правым деревом)
  • переставить любой кусок массива куда угодно (сделаем нужные разрезы и слияния в правильном порядке)
  • совершать групповые операции с элементами. Вспомним реализацию таких операций в дереве отрезков и поймем, что ничего не помешает нам сделать то же самое с описанным деревом. В групповые операции включается, естественно, и взятие функции от отрезка.
  • сделав на одном исходном массиве два дерева из элементов разной четности, можно решить задачу про смену мест четных и нечетных на отрезке (одно из домашних заданий)
  • повелевать миром