rikki_tikki 13 июл 2022 в 12:59

Префиксное дерево (trie) — вставка и поиск

4 мин

Перевод

Префиксное дерево (нагруженное дерево, trie) — структура данных для эффективного поиска. С его помощью сложность поиска можно довести до оптимального уровня — длины ключа. Вспомним, что в хорошо сбалансированном бинарном дереве поиска данные можно найти за время, пропорциональное M * log N, где M — максимальная длина строки, а N — количество ключей в дереве. В префиксном дереве — O(M), но увеличиваются требования к памяти. Подробнее о применении префиксных деревьев см. в этой статье.

Из узла префиксного дерева выходят несколько ветвей. Каждая из этих веток представляет собой возможный символ ключа. Последний узел ключа помечается специальным образом как конечный. Для этого можно использовать, например, поле isEndOfWord в структуре TreeNode, представляющей узел дерева. Структура TreeNode для узлов с символами английского алфавита может выглядеть следующим образом:

// Узел префиксного дерева 
struct TrieNode 
{ 
 	struct TrieNode *children[ALPHABET_SIZE];
 	// isEndOfWord is true if the node 
 	// represents end of a word 
 	bool isEndOfWord; 
};

Вставка ключа в префиксное дерево очень проста. Символы ключа — это отдельные узлы в дереве. Обратите внимание, что в нашем примере в поле children хранится массив указателей (или ссылок) на узлы следующего уровня, а индекс вычисляется на основе кода символа. При добавлении нового ключа, а также при дополнении существующего, строятся недостающие узлы, и последний узел помечается как окончание слова. Если добавляемый ключ является префиксом существующего ключа, то нужно просто пометить конечный узел. Длина ключа определяет глубину дерева.

Поиск ключа аналогичен вставке, однако здесь мы только сравниваем символы и перемещаемся вниз. Поиск может остановиться при завершении строки или отсутствии ключа в дереве. В первом случае, если поле isEndofWord последнего узла истинно, то ключ существует в дереве. Во втором случае поиск завершается без просмотра всех символов ключа, так как ключ отсутствует.

На рисунке ниже показано построение префиксного дерева с использованием ключей, приведенных в примере ниже.

На рисунке каждый символ имеет тип trie_node_t. Например, три дочерних узла a, b и t корня root заполнены, а все остальные ссылки на дочерние элементы будут NULL. Аналогично у узла "a" на следующем уровне только один дочерний элемент ("n"), а все остальные дочерние элементы будут NULL.

Видео смотрите в оригинале статьи.
Рекомендуемая практика на вставку и поиск в префиксном дереве

Trie | (Insert and Search) | Practice | GeeksforGeeks

practice.geeksforgeeks.org

Сложность вставки и поиска для префиксного дерева равна O(длина_ключа), однако требования к памяти будут O(РАЗМЕР_АЛФАВИТА * длина_ключа* N), где N — количество ключей в дереве. Стоит отметить, что существуют эффективные представления узлов дерева (например, сжатые префиксные деревья, тернарное дерево поиска и т. д.), позволяющие минимизировать требования к памяти.

Пример реализации префиксного дерева на C++:

// C++ implementation of search and insert
// operations on Trie
#include <bits/stdc++.h>
using namespace std;

const int ALPHABET_SIZE = 26;

// trie node
struct TrieNode
{
	struct TrieNode *children[ALPHABET_SIZE];

	// isEndOfWord is true if the node represents
	// end of a word
	bool isEndOfWord;
};

// Returns new trie node (initialized to NULLs)
struct TrieNode *getNode(void)
{
	struct TrieNode *pNode = new TrieNode;

	pNode->isEndOfWord = false;

	for (int i = 0; i < ALPHABET_SIZE; i++)
		pNode->children[i] = NULL;

	return pNode;
}

// If not present, inserts key into trie
// If the key is prefix of trie node, just
// marks leaf node
void insert(struct TrieNode *root, string key)
{
	struct TrieNode *pCrawl = root;

	for (int i = 0; i < key.length(); i++)
	{
		int index = key[i] - 'a';
		if (!pCrawl->children[index])
			pCrawl->children[index] = getNode();

		pCrawl = pCrawl->children[index];
	}

	// mark last node as leaf
	pCrawl->isEndOfWord = true;
}

// Returns true if key presents in trie, else
// false
bool search(struct TrieNode *root, string key)
{
	struct TrieNode *pCrawl = root;

	for (int i = 0; i < key.length(); i++)
	{
		int index = key[i] - 'a';
		if (!pCrawl->children[index])
			return false;

		pCrawl = pCrawl->children[index];
	}

	return (pCrawl->isEndOfWord);
}

// Driver
int main()
{
	// Input keys (use only 'a' through 'z'
	// and lower case)
	string keys[] = {"the", "a", "there",
					"answer", "any", "by",
					"bye", "their" };
	int n = sizeof(keys)/sizeof(keys[0]);

	struct TrieNode *root = getNode();

	// Construct trie
	for (int i = 0; i < n; i++)
		insert(root, keys[i]);

	// Search for different keys
	search(root, "the")? cout << "Yes\n" :
						cout << "No\n";
	search(root, "these")? cout << "Yes\n" :
						cout << "No\n";
	search(root, "their")? cout << "Yes\n" :
						cout << "No\n";
	search(root, "thaw")? cout << "Yes\n" :
						cout << "No\n";
	return 0;
}

Вывод:

the --- Present in trie
these --- Not present in trie
their --- Present in trie
thaw --- Not present in trie

Дерево отрезков — это структура данных, которая позволяет алгоритмически просто и логарифмически быстро находить сумму элементов массива на заданном отрезке. Сегодня вечером состоится бесплатное занятие, на котором мы рассмотрим идею дерева отрезков, узнаем, как его строить, обновлять и быстро O(log n) вычислять сумму чисел любого отрезка данного массива. Алгоритм очень простой и экономный: нужно O(n) памяти. Регистрация по ссылке.
Также приглашаем всех желающих на вебинар «Пирамидальная сортировка выбором», на котором мы расскажем идею алгоритма и наглядно продемонстрируем его работу на визуальных примерах с конкретными числами. Регистрация на урок.

Теги:

Хабы:

Префиксное дерево (trie) — вставка и поиск

Публикации

Информация