Trie 树

Trie树可以看做一种确定有限状态自动机(Deterministic Finit Automata)
\((S, \Sigma,K,F, \delta )\)
\(其中, \S是状态集(Trie树上所有的节点), \\Sigma 是字母表\{a,b,c,...,z\}, \K是起始状态(只有root),\ F是终止状态集, 也就是字典中每一个单词,\\delta是转移函数, 是图的边, 从一个状态后加某字母进入下一个状态.\)

Trie存储了前缀(而且容易查找不同字符串的公共前缀), 避免了查字典的时候暴力地重复比较, 所以具有比较高的效率, 插入和查询都是\(O(len)\).
以下给出简单Trie树的实现:

//Trie
#include<cstdio>
#include<cstring>
#include<iostream>
struct TrieNode {
	TrieNode* next[26];
	bool last;
	TrieNode():last(false) {
		memset(next, 0, sizeof(next));
	}
};
class Trie {
private:
	TrieNode* root;
	void DelTrie(TrieNode* t) {
		if (!t)return;
		for (int i = 0; i < 26; ++i) {
			if (t->next[i])
				DelTrie(t->next[i]);
		}
		delete t;
	}
public:
	Trie() {
		root = new TrieNode;
	}
	~Trie() {
		DelTrie(root);
	}
	void insert(char * s) {
		if (!s[0])return;
		TrieNode* p = root;
		for (int i = 0; s[i]; ++i) {
			if (!p->next[s[i] - ‘a‘])
				p->next[s[i] - ‘a‘] = new TrieNode;
			p->next[s[i] - ‘a‘];
		}
		p->last = true;
	}
	bool query(char* s) {
		if (!s[0])return false;
		TrieNode* p = root;
		for (int i = 0; s[i]; ++i) {
			if (!p->next[s[i] - ‘a‘])
				return false;
			p = p->next[s[i] - ‘a‘];
		}
		if (p->last)return true;
                return false;
	}
};

Trie 树

原文：https://www.cnblogs.com/dwt2021/p/14416218.html