字典树

字典树（Trie）是一种用于快速查找、插入和删除字符串的数据结构。它是由n个节点组成的有根树，每个节点代表一个字符串（字母或数字），根节点不包含字符。从根节点到某一节点，路径上经过的字符连接起来，为该节点对应的字符串。每个节点的所有子节点包含的字符都不相同。字典树的主要应用场景包括自动补全、拼写检查、前缀搜索等。它具有高效、占用空间小等优点，因此在实际应用中得到了广泛应用。