Tango-дерево - История изменений

Maintenance script: rollbackEdits.php mass rollback

2022-09-04T16:23:30Z

rollbackEdits.php mass rollback

185.220.101.186 в 05:14, 1 сентября 2022

2022-09-01T05:14:15Z

178.22.89.72 в 14:23, 29 мая 2015

2015-05-29T14:23:58Z

Shersh: /* Построение */

2014-06-16T18:51:25Z

‎Построение

Shersh: /* Ссылки */

2014-06-15T15:21:52Z

‎Ссылки

Shersh: /* Ссылки */

2014-06-12T16:29:26Z

‎Ссылки

Shersh в 12:30, 12 июня 2014

2014-06-12T12:30:38Z

Shersh: /* Поиск */

2014-06-11T22:35:03Z

‎Поиск

Shersh: /* Поиск */

2014-06-11T22:34:33Z

‎Поиск

Shersh: /* Построение */

2014-06-11T22:33:18Z

‎Построение

← Предыдущая		Версия 16:23, 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 Майкл Наки].
−	\|}
−
	'''Tango-дерево''' {{---}} online бинарное дерево поиска, которое изобрели Эрик Д. Демейн, Дион Хармон, Джон Яконо и Михаи Патраску в 2004 году.		'''Tango-дерево''' {{---}} online бинарное дерево поиска, которое изобрели Эрик Д. Демейн, Дион Хармон, Джон Яконо и Михаи Патраску в 2004 году.
	Это лучшая известная реализация на данный момент.		Это лучшая известная реализация на данный момент.

← Предыдущая		Версия 05:14, 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 Майкл Наки].
		+	\|}
		+
	'''Tango-дерево''' {{---}} online бинарное дерево поиска, которое изобрели Эрик Д. Демейн, Дион Хармон, Джон Яконо и Михаи Патраску в 2004 году.		'''Tango-дерево''' {{---}} online бинарное дерево поиска, которое изобрели Эрик Д. Демейн, Дион Хармон, Джон Яконо и Михаи Патраску в 2004 году.
	Это лучшая известная реализация на данный момент.		Это лучшая известная реализация на данный момент.

@@ Строка 4: / Строка 4: @@
 Время работы tango-дерева <tex>O(OPT_{dyn} \cdot \log \log n)</tex>
 ==Динамическая оптимальность==
-Рассмотрим для начала понятия online/offline динкамически/статически оптмального дерева поиска.
+Рассмотрим для начала понятия online/offline динамически/статически оптимального дерева поиска.

@@ Строка 188: / Строка 188: @@
 {{Определение
-|definition='''Жирный путь''' (англ. ''Prefered path'') {{---}} максимальный по включению путь, состоящий из жирный ребер.
+|definition='''Жирный путь''' (англ. ''Prefered path'') {{---}} максимальный по включению путь, состоящий из жирных ребер.
 }}

@@ Строка 277: / Строка 277: @@
 Операции вставки и удаления в tango-дереве не поддерживаются.
-==Ссылки==
+==Источники информации==
 *[http://www.lektorium.tv/lecture/14247  А.С.Станкевич, Дополнительные главы алгоритмов, Tango-деревья]
 *[http://erikdemaine.org/theses/dharmon.pdf Dion Harmon, New Bounds on Optimal Binary Search Trees]

← Предыдущая		Версия 16:29, 12 июня 2014
Строка 287:		Строка 287:
	[[Категория:Дискретная математика и алгоритмы]]		[[Категория:Дискретная математика и алгоритмы]]
	[[Категория:Деревья поиска]]		[[Категория:Деревья поиска]]
		+	[[Категория:Структуры данных]]

← Предыдущая		Версия 12:30, 12 июня 2014
Строка 1:		Строка 1:
−	'''Tango-дерево''' {{---}} online бинарное дерево поиска, которое изобрели Эрик Д. Демейн, Дион Хармон, Джон Яконо и ~~Mihai Patrascu~~ в 2004 году.	+	'''Tango-дерево''' {{---}} online бинарное дерево поиска, которое изобрели Эрик Д. Демейн, Дион Хармон, Джон Яконо и Михаи Патраску в 2004 году.
	Это лучшая известная реализация на данный момент.		Это лучшая известная реализация на данный момент.

@@ Строка 222: / Строка 222: @@
 Если текущий жирный путь не содержит искомый элемент, то сделаем переход по вспомогательной ссылке (красная стрелка в tango-дереве) и осуществим поиск в новом жирном пути (splay-дереве).
-Поиск в splay-дереве (синее дерево в splay-дереве) работает за высоту от количества вершин (количество вершин {{---}}} длина жирного пути (<tex>\log n</tex>)) {{---}} то есть за <tex>\log \log n</tex>.
+Поиск в splay-дереве (синее дерево в splay-дереве) работает за высоту от количества вершин (количество вершин {{---}} длина жирного пути (<tex>\log n</tex>)) {{---}} то есть за <tex>\log \log n</tex>.
 Поиск во всем дереве соответствует  <tex>(\log \log n) \cdot </tex> число проходов по нежирному ребру.

← Предыдущая		Версия 22:33, 11 июня 2014
Строка 198:		Строка 198:
	Из каждой вершины каждого splay-дерева создадим вспомогательную ссылку на корень другого splay-дерева, в котором лежит ее ребенок, связанный с ней нежирным ребром в исходном бинарном дереве поиска (при этом ссылка ставится на само дерево, а не на ребенка).		Из каждой вершины каждого splay-дерева создадим вспомогательную ссылку на корень другого splay-дерева, в котором лежит ее ребенок, связанный с ней нежирным ребром в исходном бинарном дереве поиска (при этом ссылка ставится на само дерево, а не на ребенка).

−	Корнем tango-дерева будет являться splay-дерево, которое есть жирный путь от корня исходного бинарного ~~дерев~~ поиска.	+	Корнем tango-дерева будет являться splay-дерево, которое есть жирный путь от корня исходного бинарного дерева поиска.