Декартово дерево — различия между версиями
(Исправил грамматическую ошибку) (Метки: правка с мобильного устройства, правка из мобильной версии) |
м (rollbackEdits.php mass rollback) |
||
(не показано 5 промежуточных версий 5 участников) | |||
Строка 48: | Строка 48: | ||
С помощью этой операции можно слить два декартовых дерева в одно. | С помощью этой операции можно слить два декартовых дерева в одно. | ||
− | + | Причём, все ключи в первом(''левом'') дереве должны быть меньше, чем | |
ключи во втором(''правом''). В результате получается дерево, в котором есть все ключи из первого и второго деревьев: <tex>\mathrm{merge}(T_1, T_2) \to \{T\}</tex> | ключи во втором(''правом''). В результате получается дерево, в котором есть все ключи из первого и второго деревьев: <tex>\mathrm{merge}(T_1, T_2) \to \{T\}</tex> | ||
Строка 78: | Строка 78: | ||
=== Время работы === | === Время работы === | ||
− | Рассуждая аналогично операции <tex>\mathrm{split}</tex> приходим к выводу, что трудоёмкость операции <tex>\mathrm{merge}</tex> | + | Рассуждая аналогично операции <tex>\mathrm{split}</tex>, приходим к выводу, что трудоёмкость операции <tex>\mathrm{merge}</tex> |
равна <tex>O(h)</tex>, где <tex>h</tex> {{---}} высота дерева. | равна <tex>O(h)</tex>, где <tex>h</tex> {{---}} высота дерева. | ||
=== insert === | === insert === | ||
− | Операция <tex>\mathrm{insert}(T, k)</tex> добавляет в дерево <tex>T</tex> элемент <tex>k</tex>, где <tex>k.x</tex> {{---}} ключ, а <tex>k.y</tex>{{---}} приоритет. | + | Операция <tex>\mathrm{insert}(T, k)</tex> добавляет в дерево <tex>T</tex> элемент <tex>k</tex>, где <tex>k.x</tex> {{---}} ключ, а <tex>k.y</tex> {{---}} приоритет. |
Представим что элемент <tex>k</tex>, это декартово дерево из одного элемента, и для того чтобы его добавить в наше декартово дерево <tex>T</tex>, очевидно, нам нужно их слить. Но <tex>T</tex> может содержать ключи как меньше, так и больше ключа <tex>k.x</tex>, поэтому сначала нужно разрезать <tex>T</tex> по ключу <tex>k.x</tex>. | Представим что элемент <tex>k</tex>, это декартово дерево из одного элемента, и для того чтобы его добавить в наше декартово дерево <tex>T</tex>, очевидно, нам нужно их слить. Но <tex>T</tex> может содержать ключи как меньше, так и больше ключа <tex>k.x</tex>, поэтому сначала нужно разрезать <tex>T</tex> по ключу <tex>k.x</tex>. | ||
Строка 105: | Строка 105: | ||
# Разобьём наше дерево по ключу, который мы хотим удалить, то есть <tex>\mathrm{split }(T, k.x) \to \langle T_1, T_2\rangle</tex>. | # Разобьём наше дерево по ключу, который мы хотим удалить, то есть <tex>\mathrm{split }(T, k.x) \to \langle T_1, T_2\rangle</tex>. | ||
− | # Теперь отделяем от первого дерева элемент <tex>x</tex>, то есть самого левого | + | # Теперь отделяем от первого дерева элемент <tex>x</tex>, то есть самого левого ребёнка дерева <tex> T_2 </tex>. |
# Сливаем первое дерево со вторым, то есть <tex>\mathrm{merge }(T_1, T_2) \to T</tex>. | # Сливаем первое дерево со вторым, то есть <tex>\mathrm{merge }(T_1, T_2) \to T</tex>. | ||
Строка 116: | Строка 116: | ||
== Построение декартова дерева == | == Построение декартова дерева == | ||
− | Пусть нам известно из каких пар <tex>(x_i, y_i)</tex> требуется построить декартово дерево, | + | Пусть нам известно из каких пар <tex>(x_i, y_i)</tex> требуется построить декартово дерево, причём также известно, что <tex>x_1 < x_2 < \ldots < x_n</tex>. |
=== Алгоритм за <tex>O(n\log n)</tex> === | === Алгоритм за <tex>O(n\log n)</tex> === | ||
Отсортируем все приоритеты по убыванию за <tex> O(n\log n) </tex> и выберем первый из них, пусть это будет <tex>y_k</tex>. Сделаем <tex>(x_k, y_k)</tex> корнем дерева. Проделав то же самое с остальными вершинами получим левого и правого сына <tex>(x_k, y_k)</tex>. В среднем высота Декартова дерева <tex>\log n</tex> (см. далее) и на каждом уровне мы сделали <tex>O(n)</tex> операций. Значит такой алгоритм работает за <tex>O(n\log n)</tex>. | Отсортируем все приоритеты по убыванию за <tex> O(n\log n) </tex> и выберем первый из них, пусть это будет <tex>y_k</tex>. Сделаем <tex>(x_k, y_k)</tex> корнем дерева. Проделав то же самое с остальными вершинами получим левого и правого сына <tex>(x_k, y_k)</tex>. В среднем высота Декартова дерева <tex>\log n</tex> (см. далее) и на каждом уровне мы сделали <tex>O(n)</tex> операций. Значит такой алгоритм работает за <tex>O(n\log n)</tex>. | ||
Строка 122: | Строка 122: | ||
=== Другой алгоритм за <tex>O(n\log n)</tex> === | === Другой алгоритм за <tex>O(n\log n)</tex> === | ||
− | Отсортируем | + | Отсортируем пары <tex>(x_i, y_i)</tex> по убыванию <tex>x_i</tex> и положим их в очередь. Сперва достанем из очереди первые <tex>2</tex> элемента и сольём их в дерево и положим в конец очереди, затем сделаем то же самое со следующими двумя и т.д. Таким образом, мы сольём сначала <tex>n</tex> деревьев размера <tex>1</tex>, затем <tex>\dfrac{n}{2}</tex> деревьев размера <tex>2</tex> и так далее. При этом на уменьшение размера очереди в два раза мы будем тратить суммарно <tex>O(n)</tex> время на слияния, а всего таких уменьшений будет <tex>\log n</tex>. Значит полное время работы алгоритма будет <tex>O(n\log n)</tex>. |
=== Алгоритм за <tex>O(n)</tex> === | === Алгоритм за <tex>O(n)</tex> === | ||
Строка 128: | Строка 128: | ||
− | Заметим, что каждую вершину мы посетим максимум дважды: при непосредственном добавлении и, поднимаясь вверх (ведь после этого вершина будет лежать в | + | Заметим, что каждую вершину мы посетим максимум дважды: при непосредственном добавлении и, поднимаясь вверх (ведь после этого вершина будет лежать в чьём-то левом поддереве, а мы поднимаемся только по правому). Из этого следует, что построение происходит за <tex>O(n)</tex>. |
== Случайные приоритеты == | == Случайные приоритеты == | ||
Строка 140: | Строка 140: | ||
Будем считать, что все выбранные приоритеты <tex>y</tex> попарно различны. | Будем считать, что все выбранные приоритеты <tex>y</tex> попарно различны. | ||
− | Для начала | + | Для начала введём несколько обозначений: |
* <tex>x_k</tex> {{---}} вершина с <tex>k</tex>-ым по величине ключом; | * <tex>x_k</tex> {{---}} вершина с <tex>k</tex>-ым по величине ключом; | ||
* индикаторная величина <tex>A_{i, j} = \left\{\begin{array}{lllc} 1 ,&& x_i\ \text{is ancestor of} \ x_j\\ | * индикаторная величина <tex>A_{i, j} = \left\{\begin{array}{lllc} 1 ,&& x_i\ \text{is ancestor of} \ x_j\\ | ||
Строка 155: | Строка 155: | ||
Для подсчёта средней глубины вершин нам нужно сосчитать вероятность того, что вершина <tex>x_i</tex> является предком вершины <tex>x_k</tex>, то есть <tex>Pr[A_{i,k} = 1]</tex>. | Для подсчёта средней глубины вершин нам нужно сосчитать вероятность того, что вершина <tex>x_i</tex> является предком вершины <tex>x_k</tex>, то есть <tex>Pr[A_{i,k} = 1]</tex>. | ||
− | + | Введём новое обозначение: | |
* <tex>X_{i, k}</tex> {{---}} множество ключей <tex>\{x_i, \ldots, x_k\}</tex> или <tex>\{x_k, \ldots, x_i\}</tex>, в зависимости от <tex>i < k</tex> или <tex>i > k</tex>. <tex>X_{i, k}</tex> и <tex>X_{k, i}</tex> обозначают одно и тоже, их мощность равна <tex>|k - i| + 1</tex>. | * <tex>X_{i, k}</tex> {{---}} множество ключей <tex>\{x_i, \ldots, x_k\}</tex> или <tex>\{x_k, \ldots, x_i\}</tex>, в зависимости от <tex>i < k</tex> или <tex>i > k</tex>. <tex>X_{i, k}</tex> и <tex>X_{k, i}</tex> обозначают одно и тоже, их мощность равна <tex>|k - i| + 1</tex>. | ||
Строка 170: | Строка 170: | ||
Так как распределение приоритетов равномерное, каждая вершина среди <tex>X_{i, k}</tex> может иметь максимальный приоритет, мы немедленно приходим к следующему равенству: | Так как распределение приоритетов равномерное, каждая вершина среди <tex>X_{i, k}</tex> может иметь максимальный приоритет, мы немедленно приходим к следующему равенству: | ||
− | : <tex>Pr[A_{i, | + | : <tex>Pr[A_{i, k} = 1] = \left\{\begin{array}{lllc} \dfrac{1}{k - i + 1} ,&& k \ > \ i\\ |
0 ,&& k\ =\ i\\ | 0 ,&& k\ =\ i\\ | ||
\dfrac{1}{i - k + 1} ,&& k \ < \ i\\ | \dfrac{1}{i - k + 1} ,&& k \ < \ i\\ |
Текущая версия на 19:35, 4 сентября 2022
Эта статья про курево
Декартово дерево или дерамида (англ. Treap) — это структура данных, объединяющая в себе бинарное дерево поиска и бинарную кучу (отсюда и второе её название: treap (tree + heap) и дерамида (дерево + пирамида), также существует название курево (куча + дерево).
Более строго, это бинарное дерево, в узлах которого хранятся пары
, где — это ключ, а — это приоритет. Также оно является двоичным деревом поиска по и пирамидой по . Предполагая, что все и все являются различными, получаем, что если некоторый элемент дерева содержит , то у всех элементов в левом поддереве , у всех элементов в правом поддереве , а также и в левом, и в правом поддереве имеем: .Дерамиды были предложены Сиделем (Siedel) и Арагон (Aragon) в 1996 г.
Операции в декартовом дереве
split
Операция
(разрезать) позволяет сделать следующее: разрезать исходное дерево по ключу . Возвращать она будет такую пару деревьев , что в дереве ключи меньше , а в дереве все остальные: .Эта операция устроена следующим образом.
Рассмотрим случай, в котором требуется разрезать дерево по ключу, большему ключа корня. Посмотрим, как будут устроены результирующие деревья
и :- : левое поддерево совпадёт с левым поддеревом . Для нахождения правого поддерева , нужно разрезать правое поддерево на и по ключу и взять .
- совпадёт с .
Случай, в котором требуется разрезать дерево по ключу, меньше либо равному ключа в корне, рассматривается симметрично.
Псевдокод
Treap, Treap split(t: Treap, k: int): if t == return , else if k > t.x t1, t2 = split(t.right, k) t.right = t1 return t, t2 else t1, t2 = split(t.left, k) t.left = t2 return t1, t
Время работы
Оценим время работы операции
. Во время выполнения вызывается одна операция для дерева хотя бы на один меньшей высоты и делается ещё операций. Тогда итоговая трудоёмкость этой операции равна , где — высота дерева.merge
Рассмотрим вторую операцию с декартовыми деревьями —
(слить).С помощью этой операции можно слить два декартовых дерева в одно. Причём, все ключи в первом(левом) дереве должны быть меньше, чем ключи во втором(правом). В результате получается дерево, в котором есть все ключи из первого и второго деревьев:
Рассмотрим принцип работы этой операции. Пусть нужно слить деревья
и . Тогда, очевидно, у результирующего дерева есть корень. Корнем станет вершина из или с наибольшим приоритетом . Но вершина с самым большим из всех вершин деревьев и может быть только либо корнем , либо корнем . Рассмотрим случай, в котором корень имеет больший , чем корень . Случай, в котором корень имеет больший , чем корень , симметричен этому.Если
корня больше корня , то он и будет являться корнем. Тогда левое поддерево совпадёт с левым поддеревом . Справа же нужно подвесить объединение правого поддерева и дерева .Псевдокод
Treap merge(t1: Treap, t2: Treap): if t2 ==return t1 if t1 == return t2 else if t1.y > t2.y t1.right = merge(t1.right, t2) return t1 else t2.left = merge(t1, t2.left) return t2
Время работы
Рассуждая аналогично операции
, приходим к выводу, что трудоёмкость операции равна , где — высота дерева.insert
Операция
добавляет в дерево элемент , где — ключ, а — приоритет.Представим что элемент
, это декартово дерево из одного элемента, и для того чтобы его добавить в наше декартово дерево , очевидно, нам нужно их слить. Но может содержать ключи как меньше, так и больше ключа , поэтому сначала нужно разрезать по ключу .- Реализация №1
- Разобьём наше дерево по ключу, который мы хотим добавить, то есть .
- Сливаем первое дерево с новым элементом, то есть .
- Сливаем получившиеся дерево со вторым, то есть .
- Реализация №2
- Сначала спускаемся по дереву (как в обычном бинарном дереве поиска по ), но останавливаемся на первом элементе, в котором значение приоритета оказалось меньше .
- Теперь вызываем от найденного элемента (от элемента вместе со всем его поддеревом)
- Полученные и записываем в качестве левого и правого сына добавляемого элемента.
- Полученное дерево ставим на место элемента, найденного в первом пункте.
В первой реализации два раза используется
, а во второй реализации слияние вообще не используется.remove
Операция
удаляет из дерева элемент с ключом .- Реализация №1
- Разобьём наше дерево по ключу, который мы хотим удалить, то есть .
- Теперь отделяем от первого дерева элемент , то есть самого левого ребёнка дерева .
- Сливаем первое дерево со вторым, то есть .
- Реализация №2
- Спускаемся по дереву (как в обычном бинарном дереве поиска по ), и ищем удаляемый элемент.
- Найдя элемент, вызываем его левого и правого сыновей
- Результат процедуры ставим на место удаляемого элемента.
В первой реализации один раз используется
, а во второй реализации разрезание вообще не используется.Построение декартова дерева
Пусть нам известно из каких пар
требуется построить декартово дерево, причём также известно, что .Алгоритм за
Отсортируем все приоритеты по убыванию за
и выберем первый из них, пусть это будет . Сделаем корнем дерева. Проделав то же самое с остальными вершинами получим левого и правого сына . В среднем высота Декартова дерева (см. далее) и на каждом уровне мы сделали операций. Значит такой алгоритм работает за .
Другой алгоритм за
Отсортируем пары
по убыванию и положим их в очередь. Сперва достанем из очереди первые элемента и сольём их в дерево и положим в конец очереди, затем сделаем то же самое со следующими двумя и т.д. Таким образом, мы сольём сначала деревьев размера , затем деревьев размера и так далее. При этом на уменьшение размера очереди в два раза мы будем тратить суммарно время на слияния, а всего таких уменьшений будет . Значит полное время работы алгоритма будет .Алгоритм за
Будем строить дерево слева направо, то есть начиная с двоичное дерево поиска. При добавлении , пытаемся сделать его правым сыном , это следует сделать если , иначе делаем шаг к предку последнего элемента и смотрим его значение . Поднимаемся до тех пор, пока приоритет в рассматриваемом элементе меньше приоритета в добавляемом, после чего делаем его правым сыном, а предыдущего правого сына делаем левым сыном .
по , при этом помнить последний добавленный элемент . Он будет самым правым, так как у него будет максимальный ключ, а по ключам декартово дерево представляет собой
Заметим, что каждую вершину мы посетим максимум дважды: при непосредственном добавлении и, поднимаясь вверх (ведь после этого вершина будет лежать в чьём-то левом поддереве, а мы поднимаемся только по правому). Из этого следует, что построение происходит за .
Случайные приоритеты
Мы уже выяснили, что сложность операций с декартовым деревом линейно зависит от его высоты. В действительности высота декартова дерева может быть линейной относительно его размеров. Например, высота декартова дерева, построенного по набору ключей
, будет равна . Во избежание таких случаев, полезным оказывается выбирать приоритеты в ключах случайно.Высота в декартовом дереве с случайными приоритетами
Теорема: | ||||||
В декартовом дереве из случайными величинами c равномерным распределением, средняя глубина вершины . узлов, приоритеты которого являются | ||||||
Доказательство: | ||||||
Будем считать, что все выбранные приоритеты попарно различны.Для начала введём несколько обозначений:
В силу обозначений глубину вершины можно записать как количество предков:
Теперь можно выразить математическое ожидание глубины конкретной вершины:
Для подсчёта средней глубины вершин нам нужно сосчитать вероятность того, что вершина является предком вершины , то есть .Введём новое обозначение:
Так как распределение приоритетов равномерное, каждая вершина среди может иметь максимальный приоритет, мы немедленно приходим к следующему равенству:Подставив последнее в нашу формулу с математическим ожиданием получим: (здесь мы использовали неравенство )
| ||||||
Таким образом, среднее время работы операций
и будет .