Реализация декартового дерева java

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

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

Ключ X

Как известно, декартово дерево — это структура данных, объединяющая в себе бинарное дерево поиска и бинарную кучу. При реализации же декартова дерева по неявному ключу модифицируем эту структуру. А именно, оставим в нем только приоритет [math]Y[/math] , а вместо ключа [math]X[/math] будем использовать следующую величину: количество элементов в нашей структуре, находящихся левее нашего элемента. Иначе говоря, будем считать ключом порядковый номер нашего элемента в дереве, уменьшенный на единицу.

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

Вспомогательная величина С

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

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

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

Split

Пусть процедура [math]\mathrm[/math] запущена в корне дерева с требованием отрезать от дерева [math]k[/math] вершин. Также известно, что в левом поддереве вершины находится [math]l[/math] вершин, а в правом [math]r[/math] . Рассмотрим все возможные случаи:

• [math]l \geqslant k[/math] . В этом случае нужно рекурсивно запустить процедуру [math]\mathrm[/math] от левого сына с тем же параметром [math]k[/math] . При этом новым левым сыном корня станет правая часть ответа рекурсивной процедуры, а правой частью ответа станет корень.
• [math]l \lt k[/math] Случай симметричен предыдущему. Рекурсивно запустим процедуру [math]\mathrm[/math] от правого сына с параметром [math]k — l — 1[/math] . При этом новым правым сыном корня станет левая часть ответа рекурсивной процедуры, а левой частью ответа станет корень.

 [math]\langle[/math]Treap, Treap[math]\rangle[/math] split(Treap t, int k) if t == [math] \varnothing [/math] return [math]\langle[/math][math] \varnothing [/math], [math] \varnothing [/math][math]\rangle[/math] int l = t.left.size if l [math]\small<\geqslant>[/math] k [math]\langle[/math]t1, t2[math]\rangle[/math] = split(t.left, k) t.left = t2 update(t) return [math]\langle[/math]t1, t[math]\rangle[/math] else [math]\langle[/math]t1, t2[math]\rangle[/math] = split(t.right, k - l - 1) t.right = t1 update(t) return [math]\langle[/math]t, t2[math]\rangle[/math] 

Merge

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

Поддержание корректности значений C

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

void update(Treap t) t.size = 1 + t.left.size + t.right.size

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

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

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

См. также

Источники информации

Источник

Декартово дерево

Ниже представлена реализация и примеры работы обычного декартова дерева с функциями insert , erase , build .

Изучение данной структуры является промежуточным шагом в изучении более мощной её вариации — декартова дерева по неявному ключу.

Структура Node

Структура, из экземпляров которой и будет состоять дерево. Здесь и далее key будет означать ключ, priority — приоритет, l — указатель на левого потомка вершины, r — указатель на правого потомка вершины.

struct Node  int key, priority; Node *l, *r; Node(int x, int y): key(x), priority(y), l(0), r(0) <> >; typedef Node* pNode;

Функции merge и split

Почти все функции декартова дерева выражаются через две основные: split и merge , поэтому сначала дадим их реализацию.

split

Функция split принимает указатель на вершину t и ключ x , возвращает вершины l и r — указатели на корни левого и правого деревьев после разделения.

void split(pNode t, int x, pNode &l, pNode &r)  if (!t)  l = 0; r = 0; > else if (t->key > x)  split(t->l, x, l, t->l); r = t; > else  split(t->r, x, t->r, r); l = t; > >

merge

Функция merge принимает указатели на корни двух поддеревьев l и r , и возвращает указатель на новый корень r . Важно, чтобы ключи в левом поддереве были строго меньше ключей в правом поддереве.

void merge(pNode &t, pNode l, pNode r)  if (!l)  t = r; > else if (!r)  t = l; > else if (l->priority  r->priority)  merge(l->r, l->r, r); t = l; > else  merge(r->l, l, r->l); t = r; > >

Добавление и удаление

add

Чтобы вставить вершину a с ключом a->key и приоритетом a->priority спустимся по дереву до первого элемента t , у которого приоритет окажется больше a->priority , новая вершина будет стоять на месте этой вершины t . Произведём split от этой вершины и ключа a->key , полученные поддеревья l и r станут соответственно левым и правым поддеревом новой вершины.

void add(pNode &t, pNode a)  if (!t)  t = a; > else if (a->priority  t->priority)  split(t, a->key, a->l, a->r); t = a; > else  if (t->key  a->key)  add(t->r, a); > else  add(t->l, a); > > >

remove

Чтобы удалить вершину с ключом key также рекурсивно спустимся до вершины t с соответствующим ключом, затем выполним merge для её левого и правого поддерева. После merge не забудем удалить вершину.

void remove(pNode t, int key)  if (!t)  return; > if (t->key == key)  pNode tmp = t; merge(t, t->l, t->r); delete tmp; > else  if (t->key  key)  eraser(t->r, key); > else  eraser(t->l, key); > > > 

Построение дерева

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

Линейное построение

Линейное построение стоит применять в том случае, если вы не можете контролировать приоритеты и возможно вырождение дерева в цепочку. Стоит также заметить, что линейное построение, приведённое ниже, работает только с данными, отсортированными по ключам.

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

pNode build(vectorpairint, int>> &v)  stackpNode> st; int x, y; x = v.begin()->first; x = v.begin()->second; st.emplace(new Node(x, y)); for (int i = 1; i  v.size(); ++i)  x = v[i].first; y = v[i].second; pNode t = new Node(x, y); pNode next = 0; while (st.size() && st.top()->priority > y)  next = st.top(); st.pop(); > if (st.size())  st.top()->r = t; > t->l = next; st.emplace(t); > while (st.size() > 1)  st.pop(); > return st.top(); >

Легко заметить, что каждая вершина ровно однажды попадает в стек и ровно однажды оттуда выталкивается, следовательно сложность алгоритма линейно зависит от количества вершин.

Выбор приоритета

Выше было замечено, что в худшем случае декартово дерево может вырождаться в цепочку. Этого можно избегать, если у нас есть возможность самостоятельно выбирать приоритеты. Если приоритеты являются случайными величинами с равномерным распределением, то можно показать, что средняя глубина вершины будет порядка логарифма от количества вершин [1].

Хороший рандом в C++

Как было показано в [2], встроенный rand() может подвести в самый неожиданный момент. Вместо него можно использовать следующие варианты:

mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count()); int r = rnd();

Задачи

Вставка и удаление

Линейное построеине

Дальнейшее чтение

Updated: June 18, 2019

Leave a Comment

Your email address will not be published. Required fields are marked *

You May Also Enjoy

Наименьший общий предок (LCA)

Ниже представлено описание задачи, приведены ссылки на сторонние ресурсы с материалами, а также на упражнения, которые можно решить для практики по данной те.

Фильтрация посылок на informatics

При работе на сайте дистанционной подготовки по информатике (informatics.mccme.ru или informatics.msk.ru) часто возникает потребность отфильтровать посылки п.

Быстрая сортировка

Примеры реализации быстрой сортировки.

Линейная сортировка

Пример реализации линейной сортировки

Источник