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

Ctrlalt в 15:08, 24 мая 2023

2023-05-24T15:08:19Z

← Предыдущая версия		Версия от 15:08, 24 мая 2023
Строка 1:		Строка 1:
			== TLDR ==
			<youtube width="300" height="180">68mMGJl5F8s</youtube>
			<youtube width="300" height="180">WuuLjDIiJqc</youtube>
			<youtube width="300" height="180">8hNkIeTKCpk</youtube>

	== Общие сведения ==		== Общие сведения ==
	[[Файл:bst_example_3.png\|thumb\|360px\|Влияние порядка вставки элементов на форму дерева]]		[[Файл:bst_example_3.png\|thumb\|360px\|Влияние порядка вставки элементов на форму дерева]]

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

2020-08-21T05:20:45Z

Ссылки

← Предыдущая версия		Версия от 05:20, 21 августа 2020
Строка 357:		Строка 357:
	* [http://yadi.sk/i/0iYC_v63hfnyr Фолунин В. Особенности реализации ассоциативных массивов с дублирующимися ключами на декартовых деревьях]		* [http://yadi.sk/i/0iYC_v63hfnyr Фолунин В. Особенности реализации ассоциативных массивов с дублирующимися ключами на декартовых деревьях]
	Код:		Код:
	* [~~http~~://github.com/indy256/codelibrary/blob/master/~~java~~/~~src~~/~~TreapSimple~~.~~java CodeLibrary — Treap with explicit keys~~]		* [https://github.com/indy256/codelibrary/blob/master/cpp/structures/treap.h github.com/indy256/codelibrary/blob/master/cpp/structures/treap.h]
	* [http://github.com/ADJA/algos/blob/master/DataStructures/CartesianTree.cpp Algos — Cartesian tree]		* [http://github.com/ADJA/algos/blob/master/DataStructures/CartesianTree.cpp Algos — Cartesian tree]
	Задачи:		Задачи:

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

2020-08-21T05:15:21Z

Ссылки

← Предыдущая версия		Версия от 05:15, 21 августа 2020
Строка 349:		Строка 349:
	== Ссылки ==		== Ссылки ==
	Теория:		Теория:
			* [https://www.youtube.com/watch?v=68mMGJl5F8s&list=PLGhUJWLZ8uQ5Ewplzb1ER29p4-kQme5Yr&index=2 Фолунин В. Декартово дерево (плейлист)]
	* [http://e-maxx.ru/algo/treap e-maxx.ru — Декартово дерево]		* [http://e-maxx.ru/algo/treap e-maxx.ru — Декартово дерево]
	* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%94%D0%B5%D0%BA%D0%B0%D1%80%D1%82%D0%BE%D0%B2%D0%BE_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE neerc.ifmo.ru/wiki — Декартово дерево]		* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%94%D0%B5%D0%BA%D0%B0%D1%80%D1%82%D0%BE%D0%B2%D0%BE_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE neerc.ifmo.ru/wiki — Декартово дерево]

Ctrlalt в 23:58, 4 июля 2015

2015-07-04T23:58:01Z

← Предыдущая версия		Версия от 23:58, 4 июля 2015
Строка 73:		Строка 73:

	=== Разрезание декартова дерева (split) ===		=== Разрезание декартова дерева (split) ===
	Пусть дана дерамида <tt>T</tt> (с корнем <tt>t</tt>) и некоторое число <tt>k</tt>. Требуется составить две дерамиды: <tt>A</tt>, содержащую те элементы <tt>T</tt>, ключи которых ~~не превышают~~ <tt>k</tt>, и <tt>B</tt>, содержащую все остальные элементы <tt>T</tt>. Функция должна возвращать два значения; в рассмотренной реализации они передаются через параметры, а возвращаемым типом является <tt>void</tt>.		Пусть дана дерамида <tt>T</tt> (с корнем <tt>t</tt>) и некоторое число <tt>k</tt>. Требуется составить две дерамиды: <tt>A</tt>, содержащую те элементы <tt>T</tt>, ключи которых меньше <tt>k</tt>, и <tt>B</tt>, содержащую все остальные элементы <tt>T</tt>. Функция должна возвращать два значения; в рассмотренной реализации они передаются через параметры, а возвращаемым типом является <tt>void</tt>.

	void split(TreapNode t, int k, TreapNode &a, TreapNode *&b) {		void split(TreapNode t, int k, TreapNode &a, TreapNode *&b) {
	if (!t)		if (!t)
	a = b = NULL;		a = b = NULL;
	else if (t->k <= k) {		else if (t->k < k) {
	split(t->r, k, t->r, b);		split(t->r, k, t->r, b);
	a = t;		a = t;
Строка 87:		Строка 87:
	}		}

	Если <tt>(t->k <= k)</tt>, то <tt>t</tt> станет элементом <tt>A</tt>, иначе — элементом <tt>B</tt>. Пусть <tt>t</tt> становится частью <tt>A</tt> (нетрудно заметить, что <tt>t</tt> станет корнем <tt>A</tt>), тогда все элементы поддерева <tt>t->l</tt> также становятся частью <tt>A</tt>, так как их ключи меньше <tt>t->k</tt>, а следовательно, меньше <tt>k</tt>. Ситуация с поддеревом <tt>t->r</tt> сложнее: оно может содержать как элементы, ключи которых ~~не превышают~~ <tt>k</tt>, так и элементы, ключи которых ~~превышают~~ <tt>k</tt>. Поступим следующим образом: рекурсивно разрежем <tt>t->r</tt> по <tt>k</tt>, при этом получатся две дерамиды <tt>A'</tt> и <tt>B'</tt>. Дерамиду <tt>A'</tt> нужно оставить на месте <tt>t->r</tt>, тогда <tt>T</tt> будет содержать только элементы, ключи которых ~~не превышают~~ <tt>k</tt>. <tt>B'</tt> содержит только элементы с ключами, ~~большими~~ <tt>k</tt>. Таким образом, результатами операции разрезания являются <tt>T</tt> и <tt>B'</tt>. Симметричный случай рассматривается аналогично. Можно видеть, что операция разрезания также реализуется рекурсивно; базой рекурсии является случай, когда <tt>T</tt> пуста.		Если <tt>(t->k < k)</tt>, то <tt>t</tt> станет элементом <tt>A</tt>, иначе — элементом <tt>B</tt>. Пусть <tt>t</tt> становится частью <tt>A</tt> (нетрудно заметить, что <tt>t</tt> станет корнем <tt>A</tt>), тогда все элементы поддерева <tt>t->l</tt> также становятся частью <tt>A</tt>, так как их ключи меньше <tt>t->k</tt>, а следовательно, меньше <tt>k</tt>. Ситуация с поддеревом <tt>t->r</tt> сложнее: оно может содержать как элементы, ключи которых меньше <tt>k</tt>, так и элементы, ключи которых не меньше <tt>k</tt>. Поступим следующим образом: рекурсивно разрежем <tt>t->r</tt> по <tt>k</tt>, при этом получатся две дерамиды <tt>A'</tt> и <tt>B'</tt>. Дерамиду <tt>A'</tt> нужно оставить на месте <tt>t->r</tt>, тогда <tt>T</tt> будет содержать только элементы, ключи которых меньше <tt>k</tt>. <tt>B'</tt> содержит только элементы с ключами, не меньшими <tt>k</tt>. Таким образом, результатами операции разрезания являются <tt>T</tt> и <tt>B'</tt>. Симметричный случай рассматривается аналогично. Можно видеть, что операция разрезания также реализуется рекурсивно; базой рекурсии является случай, когда <tt>T</tt> пуста.

	== Реализация операций двоичного дерева поиска ==		== Реализация операций двоичного дерева поиска ==
Строка 95:		Строка 95:

	=== Вставка элемента ===		=== Вставка элемента ===
	Пусть в декартово дерево <tt>T</tt> нужно добавить новый элемент с ключом <tt>key</tt> и значением <tt>value</tt>. Этот элемент можно рассмотреть как полноценную дерамиду <tt>Tn</tt> (имеющую только один узел). Следовательно, можно произвести слияние исходной дерамиды с добавляемой. Однако для этого нужно обеспечить выполнение предварительного условия (все ключи в первой дерамиде должны быть не больше любого из ключей во второй дерамиде). Поэтому сначала разрежем <tt>T</tt> на две части: <tt>T1</tt>, содержащую ключи, ~~не большие~~ <tt>key</tt>, и <tt>T2</tt>, содержащую все остальные ключи. Теперь можно произвести два слияния, после чего элемент будет успешно добавлен в декартово дерево <tt>T</tt>.		Пусть в декартово дерево <tt>T</tt> нужно добавить новый элемент с ключом <tt>key</tt> и значением <tt>value</tt>. Этот элемент можно рассмотреть как полноценную дерамиду <tt>Tn</tt> (имеющую только один узел). Следовательно, можно произвести слияние исходной дерамиды с добавляемой. Однако для этого нужно обеспечить выполнение предварительного условия (все ключи в первой дерамиде должны быть не больше любого из ключей во второй дерамиде). Поэтому сначала разрежем <tt>T</tt> на две части: <tt>T1</tt>, содержащую ключи, меньшие <tt>key</tt>, и <tt>T2</tt>, содержащую все остальные ключи. Теперь можно произвести два слияния, после чего элемент будет успешно добавлен в декартово дерево <tt>T</tt>.

	void insert(int key, int value) {		void insert(int key, int value) {
Строка 105:		Строка 105:

	=== Удаление элемента ===		=== Удаление элемента ===
	Пусть требуется исключить из дерамиды <tt>T</tt> все элементы, ключи которых равны <tt>key</tt>. Разрежем <tt>T</tt> на дерамиды <tt>T1</tt> и <tt>T2</tt> по ключу <tt>(key ~~- 1)~~</tt>. Тогда все элементы <tt>T1</tt> имеют ключи, меньшие <tt>key</tt>. Разрежем <tt>T2</tt> по ключу <tt>key</tt>: правая получившаяся часть (<tt>T3</tt>) содержит элементы, ключи которых больше <tt>key</tt>, а в <tt>T2</tt> останутся только элементы с ключами, равными <tt>key</tt>. Таким образом, после объединения <tt>T1</tt> и <tt>T3</tt> мы получим декартово дерево, не содержащее элементов с ключами <tt>key</tt>.		Пусть требуется исключить из дерамиды <tt>T</tt> все элементы, ключи которых равны <tt>key</tt>. Разрежем <tt>T</tt> на дерамиды <tt>T1</tt> и <tt>T2</tt> по ключу <tt>key</tt>. Тогда все элементы <tt>T1</tt> имеют ключи, меньшие <tt>key</tt>. Разрежем <tt>T2</tt> по ключу <tt>(key + 1)</tt>: правая получившаяся часть (<tt>T3</tt>) содержит элементы, ключи которых больше <tt>key</tt>, а в <tt>T2</tt> останутся только элементы с ключами, равными <tt>key</tt>. Таким образом, после объединения <tt>T1</tt> и <tt>T3</tt> мы получим декартово дерево, не содержащее элементов с ключами <tt>key</tt>.

	Если требуется освободить память, занимаемую исключаемыми элементами, то можно воспользоваться простой рекурсивной процедурой, приведённой справа.		Если требуется освободить память, занимаемую исключаемыми элементами, то можно воспользоваться простой рекурсивной процедурой, приведённой справа.
Строка 113:		Строка 113:
	void remove(int key) {		void remove(int key) {
	TreapNode t1, t2, *t3;		TreapNode t1, t2, *t3;
	split(t, key ~~- 1~~, t1, t2);		split(t, key, t1, t2);
	split(t2, key, t2, t3);		split(t2, key + 1, t2, t3);
	t = merge(t1, t3);		t = merge(t1, t3);
	dispose(t2);		dispose(t2);
Строка 139:		Строка 139:
	int res = 0;		int res = 0;
	TreapNode t1, t2, *t3;		TreapNode t1, t2, *t3;
	split(t, key ~~- 1~~, t1, t2);		split(t, key, t1, t2);
	split(t2, key, t2, t3);		split(t2, key + 1, t2, t3);
	if (t2 != NULL)		if (t2 != NULL)
	res = t2->v;		res = t2->v;
Строка 213:		Строка 213:
	if (!t)		if (!t)
	a = b = NULL;		a = b = NULL;
	else if (t->k <= k) {		else if (t->k < k) {
	split(t->r, k, t->r, b);		split(t->r, k, t->r, b);
	a = t;		a = t;
Строка 233:		Строка 233:
	int rangeSum(int k1, int k2) {		int rangeSum(int k1, int k2) {
	TreapNode t1, t2, *t3;		TreapNode t1, t2, *t3;
	split(t, k1 ~~- 1~~, t1, t2);		split(t, k1, t1, t2);
	split(t2, k2, t2, t3);		split(t2, k2 + 1, t2, t3);
	int s = getSum(t2);		int s = getSum(t2);
	t1 = merge(t1, t2);		t1 = merge(t1, t2);
Строка 311:		Строка 311:
	if (!t)		if (!t)
	a = b = NULL;		a = b = NULL;
	else if (t->k <= k) {		else if (t->k < k) {
	split(t->r, k, t->r, b);		split(t->r, k, t->r, b);
	a = t;		a = t;
Строка 330:		Строка 330:
	void rangeAdd(int k1, int k2, int addVal) {		void rangeAdd(int k1, int k2, int addVal) {
	TreapNode t1, t2, *t3;		TreapNode t1, t2, *t3;
	split(t, k1 ~~- 1~~, t1, t2);		split(t, k1, t1, t2);
	split(t2, k2, t2, t3);		split(t2, k2 + 1, t2, t3);
	if (t2 != NULL)		if (t2 != NULL)
	t2->add += addVal;		t2->add += addVal;

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

2015-07-04T23:12:19Z

Ссылки

← Предыдущая версия		Версия от 23:12, 4 июля 2015
Строка 353:		Строка 353:
	* [http://habrahabr.ru/post/101818/ habrahabr.ru — Декартово дерево: Часть 1. Описание, операции, применения]		* [http://habrahabr.ru/post/101818/ habrahabr.ru — Декартово дерево: Часть 1. Описание, операции, применения]
	* [http://habrahabr.ru/post/102006/ habrahabr.ru — Декартово дерево: Часть 2. Ценная информация в дереве и множественные операции с ней]		* [http://habrahabr.ru/post/102006/ habrahabr.ru — Декартово дерево: Часть 2. Ценная информация в дереве и множественные операции с ней]
	* [http://yadi.sk/i/0iYC_v63hfnyr Фолунин В~~. А~~. Особенности реализации ассоциативных массивов с дублирующимися ключами на декартовых деревьях]		* [http://opentrains.mipt.ru/zksh/files/zksh2015/lectures/zksh_cartesian.pdf Иващенко Д., Семенов К. Декартово дерево]
			* [http://yadi.sk/i/0iYC_v63hfnyr Фолунин В. Особенности реализации ассоциативных массивов с дублирующимися ключами на декартовых деревьях]
	Код:		Код:
	* [http://github.com/indy256/codelibrary/blob/master/java/src/TreapSimple.java CodeLibrary — Treap with explicit keys]		* [http://github.com/indy256/codelibrary/blob/master/java/src/TreapSimple.java CodeLibrary — Treap with explicit keys]

Ctrlalt в 22:07, 4 июля 2015

2015-07-04T22:07:51Z

← Предыдущая версия		Версия от 22:07, 4 июля 2015
Строка 1:		Строка 1:
	~~<span style="color: orange;">'''Текст этой статьи готов, но ещё не обновлены изображения.'''</span>~~

	== Общие сведения ==		== Общие сведения ==
	[[Файл:bst_example_3.png\|thumb\|360px\|Влияние порядка вставки элементов на форму дерева]]		[[Файл:bst_example_3.png\|thumb\|360px\|Влияние порядка вставки элементов на форму дерева]]
Строка 42:		Строка 40:

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

	~~== Демонстрация работы ==~~
	*[http://people.ksp.sk/~kuko/bak/index.html Визуализатор древовидных структур], вкладка «Treap».

	== Реализация базовых операций ==		== Реализация базовых операций ==
Строка 347:		Строка 342:

	*Задачи, в которых требуется достаточно сбалансированное дерево поиска (например, эффективная реализация множеств или словарей);		*Задачи, в которых требуется достаточно сбалансированное дерево поиска (например, эффективная реализация множеств или словарей);
	*Широкий класс задач с запросами на диапазонах (RSQ, RMQ и др.). ~~Если данные задачи предполагают также групповое обновление элементов~~, то декартовы деревья являются одной из немногих структур данных, позволяющих эффективно их решать (конкуренцию им составляют деревья отрезков, однако они проигрывают декартовым деревьям по сложности реализации);		*Широкий класс задач с запросами на диапазонах (RSQ, RMQ и др.), в том числе с обновлениями на отрезках. В отличие от [[Дерево отрезков\|деревьев отрезков]], декартовы деревья позволяют выполнять запросы на изменяющихся множествах;
	*Поиск порядковых статистик (определение k-го по величине элемента) за O(logN). В этом случае нужно поддерживать поля <tt>cnt</tt>, и далее по этой информации определять, в каком поддереве будет располагаться нужный элемент;		*Поиск порядковых статистик (определение k-го по величине элемента) за O(logN). В этом случае нужно поддерживать поля <tt>cnt</tt>, и далее по этой информации определять, в каком поддереве будет располагаться нужный элемент;
	*Решение обратной задачи (определение номера элемента в отсортированной последовательности) за O(logN). Требуется разрезать дерамиду по заданному ключу и определить количество элементов в левой части;		*Решение обратной задачи (определение номера элемента в отсортированной последовательности) за O(logN). Требуется разрезать дерамиду по заданному ключу и определить количество элементов в левой части;
	*Декартово дерево служит основой для ещё более мощной структуры данных, именуемой декартовым деревом по неявному ключу, которую можно рассматривать как массив, позволяющий производить большое количество различных операций с логарифмическим временем выполнения.		*Декартово дерево служит основой для ещё более мощной структуры данных, именуемой [[Расширения декартова дерева\|декартовым деревом по неявному ключу]], которую можно рассматривать как массив, позволяющий производить большое количество различных операций с логарифмическим временем выполнения.

	== Ссылки ==		== Ссылки ==
			Теория:
	* [http://e-maxx.ru/algo/treap e-maxx.ru — Декартово дерево]		* [http://e-maxx.ru/algo/treap e-maxx.ru — Декартово дерево]
	* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%94%D0%B5%D0%BA%D0%B0%D1%80%D1%82%D0%BE%D0%B2%D0%BE_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE neerc.ifmo.ru/wiki — Декартово дерево]		* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%94%D0%B5%D0%BA%D0%B0%D1%80%D1%82%D0%BE%D0%B2%D0%BE_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE neerc.ifmo.ru/wiki — Декартово дерево]
	* [http://habrahabr.ru/post/101818/ habrahabr.ru — Декартово дерево: Часть 1. Описание, операции, применения]		* [http://habrahabr.ru/post/101818/ habrahabr.ru — Декартово дерево: Часть 1. Описание, операции, применения]
	* [http://habrahabr.ru/post/102006/ habrahabr.ru — Декартово дерево: Часть 2. Ценная информация в дереве и множественные операции с ней]		* [http://habrahabr.ru/post/102006/ habrahabr.ru — Декартово дерево: Часть 2. Ценная информация в дереве и множественные операции с ней]
	* [http://~~informatics~~.~~mccme.ru~~/~~course~~/~~view.php?id=18 informatics~~.~~mccme~~.~~ru — Курс «Структуры данных» — часть 4~~]		* [http://yadi.sk/i/0iYC_v63hfnyr Фолунин В. А. Особенности реализации ассоциативных массивов с дублирующимися ключами на декартовых деревьях]
			Код:
	* [http://github.com/indy256/codelibrary/blob/master/java/src/TreapSimple.java CodeLibrary — Treap with explicit keys]		* [http://github.com/indy256/codelibrary/blob/master/java/src/TreapSimple.java CodeLibrary — Treap with explicit keys]
	* [http://github.com/ADJA/algos/blob/master/DataStructures/CartesianTree.cpp Algos — Cartesian tree]		* [http://github.com/ADJA/algos/blob/master/DataStructures/CartesianTree.cpp Algos — Cartesian tree]
			Задачи:
			* [http://informatics.mccme.ru/course/view.php?id=18 informatics.mccme.ru — Курс «Структуры данных» — часть 4]

	[[Category:Балансирующиеся деревья]]		[[Category:Балансирующиеся деревья]]

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

2014-08-19T05:03:45Z

Ссылки

← Предыдущая версия		Версия от 05:03, 19 августа 2014
Строка 358:		Строка 358:
	* [http://habrahabr.ru/post/102006/ habrahabr.ru — Декартово дерево: Часть 2. Ценная информация в дереве и множественные операции с ней]		* [http://habrahabr.ru/post/102006/ habrahabr.ru — Декартово дерево: Часть 2. Ценная информация в дереве и множественные операции с ней]
	* [http://informatics.mccme.ru/course/view.php?id=18 informatics.mccme.ru — Курс «Структуры данных» — часть 4]		* [http://informatics.mccme.ru/course/view.php?id=18 informatics.mccme.ru — Курс «Структуры данных» — часть 4]
			* [http://github.com/indy256/codelibrary/blob/master/java/src/TreapSimple.java CodeLibrary — Treap with explicit keys]
	* [http://github.com/ADJA/algos/blob/master/DataStructures/CartesianTree.cpp Algos — Cartesian tree]		* [http://github.com/ADJA/algos/blob/master/DataStructures/CartesianTree.cpp Algos — Cartesian tree]

	[[Category:Балансирующиеся деревья]]		[[Category:Балансирующиеся деревья]]

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

2014-08-19T04:27:07Z

Ссылки

← Предыдущая версия		Версия от 04:27, 19 августа 2014
Строка 358:		Строка 358:
	* [http://habrahabr.ru/post/102006/ habrahabr.ru — Декартово дерево: Часть 2. Ценная информация в дереве и множественные операции с ней]		* [http://habrahabr.ru/post/102006/ habrahabr.ru — Декартово дерево: Часть 2. Ценная информация в дереве и множественные операции с ней]
	* [http://informatics.mccme.ru/course/view.php?id=18 informatics.mccme.ru — Курс «Структуры данных» — часть 4]		* [http://informatics.mccme.ru/course/view.php?id=18 informatics.mccme.ru — Курс «Структуры данных» — часть 4]
			* [http://github.com/ADJA/algos/blob/master/DataStructures/CartesianTree.cpp Algos — Cartesian tree]

	[[Category:Балансирующиеся деревья]]		[[Category:Балансирующиеся деревья]]

Ctrlalt в 19:11, 13 августа 2014

2014-08-13T19:11:37Z

← Предыдущая версия		Версия от 19:11, 13 августа 2014
Строка 351:		Строка 351:
	*Решение обратной задачи (определение номера элемента в отсортированной последовательности) за O(logN). Требуется разрезать дерамиду по заданному ключу и определить количество элементов в левой части;		*Решение обратной задачи (определение номера элемента в отсортированной последовательности) за O(logN). Требуется разрезать дерамиду по заданному ключу и определить количество элементов в левой части;
	*Декартово дерево служит основой для ещё более мощной структуры данных, именуемой декартовым деревом по неявному ключу, которую можно рассматривать как массив, позволяющий производить большое количество различных операций с логарифмическим временем выполнения.		*Декартово дерево служит основой для ещё более мощной структуры данных, именуемой декартовым деревом по неявному ключу, которую можно рассматривать как массив, позволяющий производить большое количество различных операций с логарифмическим временем выполнения.

			== Ссылки ==
			* [http://e-maxx.ru/algo/treap e-maxx.ru — Декартово дерево]
			* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%94%D0%B5%D0%BA%D0%B0%D1%80%D1%82%D0%BE%D0%B2%D0%BE_%D0%B4%D0%B5%D1%80%D0%B5%D0%B2%D0%BE neerc.ifmo.ru/wiki — Декартово дерево]
			* [http://habrahabr.ru/post/101818/ habrahabr.ru — Декартово дерево: Часть 1. Описание, операции, применения]
			* [http://habrahabr.ru/post/102006/ habrahabr.ru — Декартово дерево: Часть 2. Ценная информация в дереве и множественные операции с ней]
			* [http://informatics.mccme.ru/course/view.php?id=18 informatics.mccme.ru — Курс «Структуры данных» — часть 4]

	[[Category:Балансирующиеся деревья]]		[[Category:Балансирующиеся деревья]]

Ctrlalt: /* Демонстрация работы */

2013-08-23T19:47:44Z

Демонстрация работы

← Предыдущая версия		Версия от 19:47, 23 августа 2013
Строка 44:		Строка 44:

	== Демонстрация работы ==		== Демонстрация работы ==
	[http://people.ksp.sk/~kuko/bak/index.html Визуализатор древовидных структур], вкладка «Treap».		*[http://people.ksp.sk/~kuko/bak/index.html Визуализатор древовидных структур], вкладка «Treap».

	== Реализация базовых операций ==		== Реализация базовых операций ==