Множество и словарь. Реализация на деревьях поиска - История изменений

Ctrlalt в 15:05, 24 мая 2023

2023-05-24T15:05:39Z

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

	== Общие сведения ==		== Общие сведения ==
	Иногда решение задачи требует применения [[АТД «Множество». Реализация на битовых векторах\|абстрактного типа данных «Множество»]], однако отсутствует возможность отмечать каждое допустимое значение отдельной логической переменной (если множество имеет большую мощность или бесконечно, как, например, множество строк или вещественных чисел). В этом случае необходима такая реализация множества, которая явно хранит выбранные элементы внутри себя, а также позволяет оперативно их отыскивать, добавлять и удалять. Такие требования роднят множество с другим типом данных, именуемым словарём.		Иногда решение задачи требует применения [[АТД «Множество». Реализация на битовых векторах\|абстрактного типа данных «Множество»]], однако отсутствует возможность отмечать каждое допустимое значение отдельной логической переменной (если множество имеет большую мощность или бесконечно, как, например, множество строк или вещественных чисел). В этом случае необходима такая реализация множества, которая явно хранит выбранные элементы внутри себя, а также позволяет оперативно их отыскивать, добавлять и удалять. Такие требования роднят множество с другим типом данных, именуемым словарём.

Ctrlalt: /* Удаление из двоичного дерева поиска */

2019-02-06T11:35:42Z

Удаление из двоичного дерева поиска

← Предыдущая версия		Версия от 11:35, 6 февраля 2019
Строка 202:		Строка 202:
	delete n;		delete n;
	n = child;		n = child;
	~~return;~~		} else {
	} else {
	TreeNode *succ = successor(n);		TreeNode *succ = successor(n);
	n->key = succ->key;		n->key = succ->key;
Строка 209:		Строка 208:
	remove(n->right, succ->key);		remove(n->right, succ->key);
	}		}
			return;
	}		}
	if (key < n->key)		if (key < n->key)

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

2016-07-24T20:29:43Z

Ссылки

← Предыдущая версия		Версия от 20:29, 24 июля 2016
Строка 395:		Строка 395:
	Код:		Код:
	* [http://github.com/indy256/codelibrary/blob/master/java/src/BinarySearchTree.java CodeLibrary — Binary Search Tree]		* [http://github.com/indy256/codelibrary/blob/master/java/src/BinarySearchTree.java CodeLibrary — Binary Search Tree]
			* [http://algs4.cs.princeton.edu/code/edu/princeton/cs/algs4/BST.java.html algs4.cs.princeton.edu/code — binary search tree]
	Задачи:		Задачи:
	* [http://informatics.mccme.ru/course/view.php?id=18 informatics.mccme.ru — Курс «Структуры данных» — часть 3]		* [http://informatics.mccme.ru/course/view.php?id=18 informatics.mccme.ru — Курс «Структуры данных» — часть 3]

Ctrlalt: /* Удаление из двоичного дерева поиска */

2016-01-21T14:06:48Z

Удаление из двоичного дерева поиска

← Предыдущая версия		Версия от 14:06, 21 января 2016
Строка 207:		Строка 207:
	n->key = succ->key;		n->key = succ->key;
	n->value = succ->value;		n->value = succ->value;
	remove(n->~~left~~, succ->key);		remove(n->right, succ->key);
	}		}
	}		}

Ctrlalt в 13:13, 8 июля 2015

2015-07-08T13:13:12Z

← Предыдущая версия		Версия от 13:13, 8 июля 2015
Строка 293:		Строка 293:

	== Множество на деревьях поиска в STL ==		== Множество на деревьях поиска в STL ==
	В стандартной библиотеке шаблонов C++ присутствует шаблон <tt>set<T></tt>. Для возможности его использования требуется подключить заголовочный файл <tt><set></tt> и пространство имён <tt>std</tt>. В том же заголовочном файле описан шаблон <tt>multiset<T></tt>, представляющий множество, в котором могут храниться несколько одинаковых значений. Оба шаблона обычно реализованы на балансирующихся двоичных деревьях поиска.		В стандартной библиотеке шаблонов C++ присутствует шаблон [http://www.cplusplus.com/reference/set/set/ <tt>set<T></tt>]. Для возможности его использования требуется подключить заголовочный файл <tt><set></tt> и пространство имён <tt>std</tt>. В том же заголовочном файле описан шаблон [http://www.cplusplus.com/reference/set/multiset/ <tt>multiset<T></tt>], представляющий множество, в котором могут храниться несколько одинаковых значений. Оба шаблона обычно реализованы на балансирующихся двоичных деревьях поиска.

	#include <iostream>		#include <iostream>
Строка 339:		Строка 339:

	== Словарь на деревьях поиска в STL ==		== Словарь на деревьях поиска в STL ==
	В стандартной библиотеке шаблонов C++ присутствует шаблон <tt>map<T1, T2></tt>. Для возможности его использования требуется подключить заголовочный файл <tt><map></tt> и пространство имён <tt>std</tt>. В том же заголовочном файле описан шаблон <tt>multimap<T></tt>, представляющий словарь, в котором могут храниться несколько пар с одинаковыми ключами. Оба шаблона обычно реализованы на балансирующихся двоичных деревьях поиска.		В стандартной библиотеке шаблонов C++ присутствует шаблон [http://www.cplusplus.com/reference/map/map/ <tt>map<T1, T2></tt>]. Для возможности его использования требуется подключить заголовочный файл <tt><map></tt> и пространство имён <tt>std</tt>. В том же заголовочном файле описан шаблон [http://www.cplusplus.com/reference/map/multimap/ <tt>multimap<T1, T2></tt>], представляющий словарь, в котором могут храниться несколько пар с одинаковыми ключами. Оба шаблона обычно реализованы на балансирующихся двоичных деревьях поиска.

	#include <iostream>		#include <iostream>

Ctrlalt в 00:13, 5 июля 2015

2015-07-05T00:13:40Z

← Предыдущая версия		Версия от 00:13, 5 июля 2015
Строка 55:		Строка 55:
	Пусть вершина A указывает на вершины B и C. Тогда B и C — ''потомки'' A, A — ''родитель'' B и C. Односвязный список имеет начальный элемент; по аналогии, двоичное дерево также имеет стартовую вершину — ''корень''. Из корня по указателям можно добраться до любой вершины дерева. Вершины, не имеющие потомков, называются ''листьями''.		Пусть вершина A указывает на вершины B и C. Тогда B и C — ''потомки'' A, A — ''родитель'' B и C. Односвязный список имеет начальный элемент; по аналогии, двоичное дерево также имеет стартовую вершину — ''корень''. Из корня по указателям можно добраться до любой вершины дерева. Вершины, не имеющие потомков, называются ''листьями''.

	Когда речь идёт о двоичном дереве поиска (англ. binary search tree, BST), подразумевается дерево, на элементы которого наложены дополнительные ограничения по размещению. Мы уже сталкивались с подобным: двоичное дерево, в котором ключ вершины не меньше, чем ключи её потомков, именуется [[АТД «Очередь с приоритетами»#Определение пирамиды\|пирамидой]]. В пирамиде непосредственные потомки узла являются равноправными; в двоичном дереве поиска выделяется ''левый потомок'' и ''правый потомок'', и дополнительное ограничение сформулировано следующим образом: ключи в левом поддереве ~~не превышают~~ ключа в родителе, а ключи в правом поддереве ~~больше~~ ключа в родителе (''основное свойство дерева поиска'').		Когда речь идёт о двоичном дереве поиска (англ. binary search tree, BST), подразумевается дерево, на элементы которого наложены дополнительные ограничения по размещению. Мы уже сталкивались с подобным: двоичное дерево, в котором ключ вершины не меньше, чем ключи её потомков, именуется [[АТД «Очередь с приоритетами»#Определение пирамиды\|пирамидой]]. В пирамиде непосредственные потомки узла являются равноправными; в двоичном дереве поиска выделяется ''левый потомок'' и ''правый потомок'', и дополнительное ограничение сформулировано следующим образом: ключи в левом поддереве меньше ключа в родителе, а ключи в правом поддереве не меньше ключа в родителе (''основное свойство дерева поиска'').

	{\| align="center"		{\| align="center"
Строка 129:		Строка 129:
	if (n == NULL)		if (n == NULL)
	n = new TreeNode(key, value);		n = new TreeNode(key, value);
	else if (key <= n->key)		else if (key < n->key)
	insert(n->left, key, value);		insert(n->left, key, value);
	else		else
Строка 153:		Строка 153:
	TreeNode n = root, &child;		TreeNode n = root, &child;
	while (true) {		while (true) {
	if (key <= n->key)		if (key < n->key)
	child = n->left;		child = n->left;
	else		else
Строка 181:		Строка 181:
	Конечно, можно подвесить одно из поддеревьев к листу второго и далее рассматривать случай удаления узла с одним потомком, но такой подход увеличивает высоту дерева. Поэтому используется другое решение: удаляемый узел заменяется некоторым из его потомков (не обязательно непосредственных).		Конечно, можно подвесить одно из поддеревьев к листу второго и далее рассматривать случай удаления узла с одним потомком, но такой подход увеличивает высоту дерева. Поэтому используется другое решение: удаляемый узел заменяется некоторым из его потомков (не обязательно непосредственных).

	Чтобы при этом не нарушилось основное свойство двоичного дерева, ключ этого потомка должен быть ~~не меньше~~ всех ключей левого поддерева удаляемого узла и ~~меньше~~ всех ключей правого поддерева удаляемого узла. Как можно догадаться, этому условию удовлетворяет только один потомок — узел с ~~максимальным~~ ключом в ~~левом~~ поддереве, ~~непосредственный предшественник удаляемого узла~~. Найти его можно, переходя по ~~правым~~ ссылкам в поддереве <tt>n->~~left~~</tt>, где <tt>n</tt> — удаляемый элемент. Далее производится обмен этих узлов и уничтожение ссылки на удаляемый узел.		Чтобы при этом не нарушилось основное свойство двоичного дерева, ключ этого потомка должен быть больше всех ключей левого поддерева удаляемого узла и не больше всех ключей правого поддерева удаляемого узла. Как можно догадаться, этому условию удовлетворяет только один потомок — узел с минимальным ключом в правом поддереве, т. е. узел, непосредственно следующий за удаляемым. Найти его можно, переходя по левым ссылкам в поддереве <tt>n->right</tt>, где <tt>n</tt> — удаляемый элемент. Далее производится обмен этих узлов и уничтожение ссылки на удаляемый узел.

	Можно видеть, что операция удаления элемента из двоичного дерева является достаточно сложной, и, кроме того, она реорганизует дерево, что в некоторых случаях является нежелательным. Поэтому часто удаление элемента заменяется присвоением ему некоторого «признака отсутствия», который позволяет игнорировать этот элемент в операциях поиска.		Можно видеть, что операция удаления элемента из двоичного дерева является достаточно сложной, и, кроме того, она реорганизует дерево, что в некоторых случаях является нежелательным. Поэтому часто удаление элемента заменяется присвоением ему некоторого «признака отсутствия», который позволяет игнорировать этот элемент в операциях поиска.

	Ниже приведён пример рекурсивной реализации удаления элемента. Вспомогательная функция <tt>~~predecessor~~()</tt> определяет ~~непосредственного предшественника~~ для заданного узла, имеющего двух потомков.		Ниже приведён пример рекурсивной реализации удаления элемента. Вспомогательная функция <tt>successor()</tt> определяет непосредственный последующий узел для заданного узла, имеющего двух потомков.

	TreeNode ~~predecessor~~(TreeNode n) {		TreeNode successor(TreeNode n) {
	TreeNode *l = n->~~left~~;		TreeNode *r = n->right;
	while (l->~~right~~ != NULL)		while (r->left != NULL)
	l = l->~~right~~;		r = r->left;
	return l;		return r;
	}		}

Строка 204:		Строка 204:
	return;		return;
	} else {		} else {
	TreeNode *~~pred~~ = ~~predecessor~~(n);		TreeNode *succ = successor(n);
	n->key = ~~pred~~->key;		n->key = succ->key;
	n->value = ~~pred~~->value;		n->value = succ->value;
	remove(n->left, ~~pred~~->key);		remove(n->left, succ->key);
	}		}
	}		}
Строка 264:		Строка 264:
	if (n == NULL)		if (n == NULL)
	n = new TreeNode(key, value);		n = new TreeNode(key, value);
	if (key <= n->key)		if (key < n->key)
	n->left = insert(n->left, key, value);		n->left = insert(n->left, key, value);
	else		else

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

2015-07-04T22:08:52Z

Ссылки

← Предыдущая версия		Версия от 22:08, 4 июля 2015
Строка 392:		Строка 392:
	Теория:		Теория:
	* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%94%D0%B5%D1%80%D0%B5%D0%B2%D0%BE_%D0%BF%D0%BE%D0%B8%D1%81%D0%BA%D0%B0,_%D0%BD%D0%B0%D0%B8%D0%B2%D0%BD%D0%B0%D1%8F_%D1%80%D0%B5%D0%B0%D0%BB%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F neerc.ifmo.ru/wiki — Дерево поиска, наивная реализация]		* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%94%D0%B5%D1%80%D0%B5%D0%B2%D0%BE_%D0%BF%D0%BE%D0%B8%D1%81%D0%BA%D0%B0,_%D0%BD%D0%B0%D0%B8%D0%B2%D0%BD%D0%B0%D1%8F_%D1%80%D0%B5%D0%B0%D0%BB%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F neerc.ifmo.ru/wiki — Дерево поиска, наивная реализация]
	* [http://informatics.mccme.ru/course/view.php?id=18 informatics.mccme.ru — Курс «Структуры данных» — часть 3]
	* [http://algs4.cs.princeton.edu/lectures/32BinarySearchTrees.pdf algs4.cs.princeton.edu/lectures — 3.2 Binary Search Trees]		* [http://algs4.cs.princeton.edu/lectures/32BinarySearchTrees.pdf algs4.cs.princeton.edu/lectures — 3.2 Binary Search Trees]
	Код:		Код:
	* [http://github.com/indy256/codelibrary/blob/master/java/src/BinarySearchTree.java CodeLibrary — Binary Search Tree]		* [http://github.com/indy256/codelibrary/blob/master/java/src/BinarySearchTree.java CodeLibrary — Binary Search Tree]
	Задачи:		Задачи:
			* [http://informatics.mccme.ru/course/view.php?id=18 informatics.mccme.ru — Курс «Структуры данных» — часть 3]
	* [[:Категория: Задачи: map\|Задачи: map]]		* [[:Категория: Задачи: map\|Задачи: map]]

	[[Category:Базовые структуры и абстрактные типы данных]]		[[Category:Базовые структуры и абстрактные типы данных]]

Ctrlalt в 21:52, 4 июля 2015

2015-07-04T21:52:41Z

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

	== Демонстрация работы ==		== Демонстрация работы ==
	*[http://www.cs.usfca.edu/~galles/visualization/BST.html ~~Двоичное дерево поиска и его основные операции~~]		* [http://www.cs.usfca.edu/~galles/visualization/BST.html Data Structure Visualizations — Binary Search Tree]
	*[http://~~people.ksp~~.~~sk/~kuko~~/~~bak/index~~.html ~~Визуализатор древовидных структур], вкладка~~ &~~laquo~~;~~BST».~~		* [http://visualgo.net/bst.html VisuAlgo — Binary Search Tree, AVL Tree]

	== Реализация ==		== Реализация ==
Строка 388:		Строка 388:

	Элементы внутри <tt>map</tt> и <tt>multimap</tt> упорядочены по возрастанию ключей.		Элементы внутри <tt>map</tt> и <tt>multimap</tt> упорядочены по возрастанию ключей.

	~~== Ссылки на задачи ==~~
	* [http://codeforces.ru/gym/100070/problem/C Codeforces #100070.C — Правое вхождение]

	== Ссылки ==		== Ссылки ==
			Теория:
	* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%94%D0%B5%D1%80%D0%B5%D0%B2%D0%BE_%D0%BF%D0%BE%D0%B8%D1%81%D0%BA%D0%B0,_%D0%BD%D0%B0%D0%B8%D0%B2%D0%BD%D0%B0%D1%8F_%D1%80%D0%B5%D0%B0%D0%BB%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F neerc.ifmo.ru/wiki — Дерево поиска, наивная реализация]		* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%94%D0%B5%D1%80%D0%B5%D0%B2%D0%BE_%D0%BF%D0%BE%D0%B8%D1%81%D0%BA%D0%B0,_%D0%BD%D0%B0%D0%B8%D0%B2%D0%BD%D0%B0%D1%8F_%D1%80%D0%B5%D0%B0%D0%BB%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D1%8F neerc.ifmo.ru/wiki — Дерево поиска, наивная реализация]
	* [http://informatics.mccme.ru/course/view.php?id=18 informatics.mccme.ru — Курс «Структуры данных» — часть 3]		* [http://informatics.mccme.ru/course/view.php?id=18 informatics.mccme.ru — Курс «Структуры данных» — часть 3]
	* [http://algs4.cs.princeton.edu/lectures/32BinarySearchTrees.pdf algs4.cs.princeton.edu/lectures — 3.2 Binary Search Trees]		* [http://algs4.cs.princeton.edu/lectures/32BinarySearchTrees.pdf algs4.cs.princeton.edu/lectures — 3.2 Binary Search Trees]
	* [http:~~//visualgo.net/bst.html VisuAlgo — Binary Search Tree, AVL Tree]~~		Код:
	* [http://github.com/indy256/codelibrary/blob/master/java/src/BinarySearchTree.java CodeLibrary — Binary Search Tree]		* [http://github.com/indy256/codelibrary/blob/master/java/src/BinarySearchTree.java CodeLibrary — Binary Search Tree]
			Задачи:
			* [[:Категория: Задачи: map\|Задачи: map]]

	[[Category:Базовые структуры и абстрактные типы данных]]		[[Category:Базовые структуры и абстрактные типы данных]]

Ctrlalt в 21:29, 4 июля 2015

2015-07-04T21:29:58Z

← Предыдущая версия		Версия от 21:29, 4 июля 2015
Строка 126:		Строка 126:
	\|-		\|-
	\|		\|
	TreeNode insert(TreeNode n, int key, int value) {		void insert(TreeNode *&n, int key, int value) {
	if (n == NULL)		if (n == NULL)
	~~return~~ new TreeNode(key, value);		n = new TreeNode(key, value);
	if (key <= n->key)		else if (key <= n->key)
	~~n->left =~~ insert(n->left, key, value);		insert(n->left, key, value);
	else		else
	~~n->right =~~ insert(n->right, key, value);		insert(n->right, key, value);
	}		}

	void insert(int key, int value) {		void insert(int key, int value) {
	~~root =~~ insert(root, key, value);		insert(root, key, value);
	}		}

Строка 194:		Строка 194:
	}		}

	TreeNode remove(TreeNode n, int key) {		void remove(TreeNode *&n, int key) {
	if (n == NULL)		if (n == NULL)
	return;		return;
Строка 201:		Строка 201:
	TreeNode *child = (n->left != NULL ? n->left : n->right);		TreeNode *child = (n->left != NULL ? n->left : n->right);
	delete n;		delete n;
	return ~~child~~;		n = child;
			return;
	} else {		} else {
	TreeNode *pred = predecessor(n);		TreeNode *pred = predecessor(n);
	n->key = pred->key;		n->key = pred->key;
	n->value = pred->value;		n->value = pred->value;
	~~n->left =~~ remove(n->left, pred->key);		remove(n->left, pred->key);
	~~return n~~;
	}		}
	}		}
	if (key < n->key)		if (key < n->key)
	~~n->left =~~ remove(n->left, key);		remove(n->left, key);
	else		else
	~~n->right =~~ remove(n->right, key);		remove(n->right, key);
	}		}

	void remove(int key) {		void remove(int key) {
	~~root =~~ remove(root, key);		remove(root, key);
	}		}

Строка 261:		Строка 261:
	}		}

	TreeNode insert(TreeNode n, int key, int value) {		void insert(TreeNode *n, int key, int value) {
	if (n == NULL)		if (n == NULL)
	~~return~~ new TreeNode(key, value);		n = new TreeNode(key, value);
	if (key <= n->key)		if (key <= n->key)
	n->left = insert(n->left, key, value);		n->left = insert(n->left, key, value);
Строка 282:		Строка 282:

	void insert(int key, int value) {		void insert(int key, int value) {
	~~root =~~ insert(root, key, value);		insert(root, key, value);
	}		}

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

2014-10-26T00:30:35Z

Ссылки

← Предыдущая версия		Версия от 00:30, 26 октября 2014
Строка 388:		Строка 388:

	Элементы внутри <tt>map</tt> и <tt>multimap</tt> упорядочены по возрастанию ключей.		Элементы внутри <tt>map</tt> и <tt>multimap</tt> упорядочены по возрастанию ключей.

			== Ссылки на задачи ==
			* [http://codeforces.ru/gym/100070/problem/C Codeforces #100070.C — Правое вхождение]

	== Ссылки ==		== Ссылки ==