Декартово дерево - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:35:28Z

rollbackEdits.php mass rollback

185.220.100.254 в 04:12, 1 сентября 2022

2022-09-01T04:12:38Z

94.25.177.20: /* Другой алгоритм за O(n\log n) */

2021-01-15T13:08:22Z

‎Другой алгоритм за O(n\log n)

DanilaB: /* Высота в декартовом дереве с случайными приоритетами */

2020-08-05T18:20:39Z

‎Высота в декартовом дереве с случайными приоритетами

Дмитрий Мурзин в 17:09, 16 января 2019

2019-01-16T17:09:28Z

93.175.2.181: Пропущена запятая

2018-11-18T16:37:20Z

Пропущена запятая

213.87.151.189: Исправил грамматическую ошибку

2018-10-29T09:37:13Z

Исправил грамматическую ошибку

Grey666: Арагон - женщина

2018-07-22T20:10:46Z

Арагон - женщина

Vsklamm: /* split */

2018-04-24T00:22:16Z

‎split

37.57.17.214: /* Другой алгоритм за O(n\log n) */ опечатка

2016-11-26T08:32:36Z

‎Другой алгоритм за O(n\log n): опечатка

← Предыдущая		Версия 16:35, 4 сентября 2022
Строка 1:		Строка 1:
−	~~{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"~~
−	\|+
−	~~\|-align="center"~~
−	~~\|'''НЕТ ВОЙНЕ'''~~
−	~~\|-style="font-size: 16px;"~~
−	\|
−	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
−
−	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
−
−	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
−
−	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
−
−	~~''Антивоенный комитет России''~~
−	~~\|-style="font-size: 16px;"~~
−	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
−	~~\|-style="font-size: 16px;"~~
−	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
−	\|}
−
	''Эта статья про курево''		''Эта статья про курево''

← Предыдущая		Версия 04:12, 1 сентября 2022
Строка 1:		Строка 1:
		+	{\| class="wikitable" align="center" style="color: red; background-color: black; font-size: 56px; width: 800px;"
		+	\|+
		+	\|-align="center"
		+	\|'''НЕТ ВОЙНЕ'''
		+	\|-style="font-size: 16px;"
		+	\|
		+	24 февраля 2022 года российское руководство во главе с Владимиром Путиным развязало агрессивную войну против Украины. В глазах всего мира это военное преступление совершено от лица всей страны, всех россиян.
		+
		+	Будучи гражданами Российской Федерации, мы против своей воли оказались ответственными за нарушение международного права, военное вторжение и массовую гибель людей. Чудовищность совершенного преступления не оставляет возможности промолчать или ограничиться пассивным несогласием.
		+
		+	Мы убеждены в абсолютной ценности человеческой жизни, в незыблемости прав и свобод личности. Режим Путина — угроза этим ценностям. Наша задача — обьединить все силы для сопротивления ей.
		+
		+	Эту войну начали не россияне, а обезумевший диктатор. И наш гражданский долг — сделать всё, чтобы её остановить.
		+
		+	''Антивоенный комитет России''
		+	\|-style="font-size: 16px;"
		+	\|Распространяйте правду о текущих событиях, оберегайте от пропаганды своих друзей и близких. Изменение общественного восприятия войны - ключ к её завершению.
		+	\|-style="font-size: 16px;"
		+	\|[https://meduza.io/ meduza.io], [https://www.youtube.com/c/popularpolitics/videos Популярная политика], [https://novayagazeta.ru/ Новая газета], [https://zona.media/ zona.media], [https://www.youtube.com/c/MackNack/videos Майкл Наки].
		+	\|}
		+
	''Эта статья про курево''		''Эта статья про курево''

@@ Строка 122: / Строка 122: @@
 === Другой алгоритм за <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>(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> ===

@@ Строка 170: / Строка 170: @@
 Так как распределение приоритетов равномерное, каждая вершина среди <tex>X_{i, k}</tex> может иметь максимальный приоритет,  мы немедленно приходим к следующему равенству:
-: <tex>Pr[A_{i, j} = 1] = \left\{\begin{array}{lllc} \dfrac{1}{k - i + 1} ,&& k \ > \ i\\
+: <tex>Pr[A_{i, k} = 1] = \left\{\begin{array}{lllc} \dfrac{1}{k - i + 1} ,&& k \ > \ i\\
 ,&& k\ =\ i\\
 \dfrac{1}{i - k + 1} ,&& k \ < \ i\\

@@ Строка 48: / Строка 48: @@
 С помощью этой операции можно слить два декартовых дерева в одно.
-Причем, все ключи в первом(''левом'') дереве должны быть меньше, чем
+Причём, все ключи в первом(''левом'') дереве должны быть меньше, чем
 ключи во втором(''правом''). В результате получается дерево, в котором есть все ключи из первого и второго деревьев:  <tex>\mathrm{merge}(T_1, T_2) \to \{T\}</tex>
@@ Строка 82: / Строка 82: @@
 === 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>.
@@ Строка 105: / Строка 105: @@
 # Разобьём наше дерево по ключу, который мы хотим удалить, то есть <tex>\mathrm{split }(T, k.x) \to \langle T_1, T_2\rangle</tex>.
-# Теперь отделяем от первого дерева элемент <tex>x</tex>, то есть самого левого ребенка дерева <tex> T_2 </tex>.
+# Теперь отделяем от первого дерева элемент <tex>x</tex>, то есть самого левого ребёнка дерева <tex> T_2 </tex>.
 # Сливаем первое дерево со вторым, то есть <tex>\mathrm{merge }(T_1, T_2) \to T</tex>.
@@ Строка 116: / Строка 116: @@
 == Построение декартова дерева ==
-Пусть нам известно из каких пар <tex>(x_i, y_i)</tex> требуется построить декартово дерево, причем также известно, что <tex>x_1 < x_2 < \ldots < x_n</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>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>(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>(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> ===
@@ Строка 128: / Строка 128: @@
-Заметим, что каждую вершину мы посетим максимум дважды: при непосредственном добавлении и, поднимаясь вверх (ведь после этого вершина будет лежать в чьем-то левом поддереве, а мы поднимаемся только по правому). Из этого следует, что построение происходит за <tex>O(n)</tex>.
+Заметим, что каждую вершину мы посетим максимум дважды: при непосредственном добавлении и, поднимаясь вверх (ведь после этого вершина будет лежать в чьём-то левом поддереве, а мы поднимаемся только по правому). Из этого следует, что построение происходит за <tex>O(n)</tex>.
 == Случайные приоритеты ==
@@ Строка 140: / Строка 140: @@
 Будем считать, что все выбранные приоритеты <tex>y</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\\
@@ Строка 155: / Строка 155: @@
 Для подсчёта средней глубины вершин нам нужно сосчитать вероятность того,  что вершина <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>.

@@ Строка 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> {{---}} высота дерева.

@@ Строка 3: / Строка 3: @@
 '''Декартово дерево или дерамида''' (англ. ''Treap'') {{---}} это структура данных, объединяющая в себе [[Дерево поиска, наивная реализация|бинарное дерево поиска]] и [[Двоичная куча|бинарную кучу]] (отсюда и второе её название: treap (tree + heap) и дерамида (дерево + пирамида), также существует название курево (куча + дерево).
-Более строго, это бинарное дерево, в узлах которого хранится пары <tex> (x,y) </tex>, где <tex>x</tex> {{---}} это ключ, а <tex>y</tex> {{---}} это приоритет. Также оно является двоичным деревом поиска по <tex>x</tex> и пирамидой по <tex>y</tex>. Предполагая, что все <tex>x</tex> и все <tex>y</tex> являются различными, получаем, что если некоторый элемент дерева содержит <tex>(x_0,y_0)</tex>, то у всех элементов в левом поддереве <tex>x < x_0</tex>, у всех элементов в правом поддереве <tex> x > x_0</tex>, а также и в левом, и в правом поддереве имеем: <tex> y < y_0</tex>.
+Более строго, это бинарное дерево, в узлах которого хранятся пары <tex> (x,y) </tex>, где <tex>x</tex> {{---}} это ключ, а <tex>y</tex> {{---}} это приоритет. Также оно является двоичным деревом поиска по <tex>x</tex> и пирамидой по <tex>y</tex>. Предполагая, что все <tex>x</tex> и все <tex>y</tex> являются различными, получаем, что если некоторый элемент дерева содержит <tex>(x_0,y_0)</tex>, то у всех элементов в левом поддереве <tex>x < x_0</tex>, у всех элементов в правом поддереве <tex> x > x_0</tex>, а также и в левом, и в правом поддереве имеем: <tex> y < y_0</tex>.
 Дерамиды были предложены Сиделем (Siedel) и Арагон (Aragon) в 1996 г.

@@ Строка 5: / Строка 5: @@
 Более строго, это бинарное дерево, в узлах которого хранится пары <tex> (x,y) </tex>, где <tex>x</tex> {{---}} это ключ, а <tex>y</tex> {{---}} это приоритет. Также оно является двоичным деревом поиска по <tex>x</tex> и пирамидой по <tex>y</tex>. Предполагая, что все <tex>x</tex> и все <tex>y</tex> являются различными, получаем, что если некоторый элемент дерева содержит <tex>(x_0,y_0)</tex>, то у всех элементов в левом поддереве <tex>x < x_0</tex>, у всех элементов в правом поддереве <tex> x > x_0</tex>, а также и в левом, и в правом поддереве имеем: <tex> y < y_0</tex>.
-Дерамиды были предложены Сиделем (Siedel) и Арагоном (Aragon) в 1996 г.
+Дерамиды были предложены Сиделем (Siedel) и Арагон (Aragon) в 1996 г.
 == Операции в декартовом дереве ==

@@ Строка 11: / Строка 11: @@
 [[file:split.png|thumb|400px|Операция split]]
-Операция <tex>\mathrm{split}</tex> (''разрезать'') позволяет сделать следующее, разрезать исходное дерево <tex>T</tex> по ключу <tex>k</tex>. Возвращать она будет такую пару деревьев <tex>\langle T_1, T_2\rangle </tex>, что в дереве <tex>T_1</tex> ключи меньше <tex>k</tex>, а в дереве <tex>T_2</tex> все остальные:  <tex>\mathrm{split}(T, k) \to \langle T_1, T_2\rangle </tex>.
+Операция <tex>\mathrm{split}</tex> (''разрезать'') позволяет сделать следующее: разрезать исходное дерево <tex>T</tex> по ключу <tex>k</tex>. Возвращать она будет такую пару деревьев <tex>\langle T_1, T_2\rangle </tex>, что в дереве <tex>T_1</tex> ключи меньше <tex>k</tex>, а в дереве <tex>T_2</tex> все остальные:  <tex>\mathrm{split}(T, k) \to \langle T_1, T_2\rangle </tex>.
 Эта операция устроена следующим образом.