首页 > 代码库 > 字典树
字典树
字典树（Trie）是一种很特别的树状信息检索数据结构，如同其名，它的构成就像一本字典，可以让你快速的进行字符插入、字符串搜索等。
Trie 一词来自 retrieval，发音为 /tri:/ "tree"，也有人读为 /tra?/ "try"。
字典树设计的核心思想是空间换时间，所以数据结构本身比较消耗空间。但它利用了字符串的共同前缀（Common Prefix）作为存储依据，以此来节省存储空间，并加速搜索时间。Trie 的字符串搜索时间复杂度为 O(m)，m 为最长的字符串的长度，其查询性能与集合中的字符串的数量无关。其在搜索字符串时表现出的高效，使得特别适用于构建文本搜索和词频统计等应用。
字典树的性质
- 根节点（Root）不包含字符，除根节点外的每一个节点都仅包含一个字符；
- 从根节点到某一节点路径上所经过的字符连接起来，即为该节点对应的字符串；
- 任意节点的所有子节点所包含的字符都不相同；
如下图的 Trie 树中包含了字符串集合 ["Joe", "John", "Johnny", "Jane", "Jack"]。
Trie 关键词查找过程：
- 每次从根结点开始搜索；
- 获取关键词的第一个字符，根据该字符选择对应的子节点，转到该子节点继续检索；
- 在相应的子节点上，获取关键词的第二个字符，进一步选择对应的子节点进行检索；
- 以此类推，进行迭代过程；
- 在某个节点处，关键词的所有字母已被取出，则读取附在该节点上的信息，查找完成。
关键词的插入和查找过程的时间复杂度均为 O(key_length)，空间复杂度 O(ALPHABET_SIZE * key_length * N) ，其中 N 是关键词的数量。
1 #include <stdio.h> 2 #include <stdlib.h> 3 #include <string.h> 4 5 #define ARRAY_SIZE(a) sizeof(a)/sizeof(a[0]) 6 7 // Alphabet size (# of symbols) 8 #define ALPHABET_SIZE (26) 9 10 // Converts key current character into index 11 // use only ‘a‘ through ‘z‘ and lower case 12 #define CHAR_TO_INDEX(c) ((int)c - (int)‘a‘) 13 14 // trie node 15 typedef struct trie_node trie_node_t; 16 struct trie_node 17 { 18 int value; 19 trie_node_t *children[ALPHABET_SIZE]; 20 }; 21 22 // trie ADT 23 typedef struct trie trie_t; 24 struct trie 25 { 26 trie_node_t *root; 27 int count; 28 }; 29 30 // Returns new trie node (initialized to NULLs) 31 trie_node_t *getNode(void) 32 { 33 trie_node_t *pNode = NULL; 34 35 pNode = (trie_node_t *)malloc(sizeof(trie_node_t)); 36 37 if (pNode) 38 { 39 int i; 40 41 pNode->value = http://www.mamicode.com/0; 42 43 for (i = 0; i < ALPHABET_SIZE; i++) 44 { 45 pNode->children[i] = NULL; 46 } 47 } 48 49 return pNode; 50 } 51 52 // Initializes trie (root is dummy node) 53 void initialize(trie_t *pTrie) 54 { 55 pTrie->root = getNode(); 56 pTrie->count = 0; 57 } 58 59 // If not present, inserts key into trie 60 // If the key is prefix of trie node, just marks leaf node 61 void insert(trie_t *pTrie, char key[]) 62 { 63 int level; 64 int length = strlen(key); 65 int index; 66 trie_node_t *pCrawl; 67 68 pTrie->count++; 69 pCrawl = pTrie->root; 70 71 for (level = 0; level < length; level++) 72 { 73 index = CHAR_TO_INDEX(key[level]); 74 if (!pCrawl->children[index]) 75 { 76 pCrawl->children[index] = getNode(); 77 } 78 79 pCrawl = pCrawl->children[index]; 80 } 81 82 // mark last node as leaf 83 pCrawl->value = http://www.mamicode.com/pTrie->count; 84 } 85 86 // Returns non zero, if key presents in trie 87 int search(trie_t *pTrie, char key[]) 88 { 89 int level; 90 int length = strlen(key); 91 int index; 92 trie_node_t *pCrawl; 93 94 pCrawl = pTrie->root; 95 96 for (level = 0; level < length; level++) 97 { 98 index = CHAR_TO_INDEX(key[level]); 99 100 if (!pCrawl->children[index])101 {102 return 0;103 }104 105 pCrawl = pCrawl->children[index];106 }107 108 return (0 != pCrawl && pCrawl->value);109 }110 111 // Driver112 int main()113 {114 // Input keys (use only ‘a‘ through ‘z‘ and lower case)115 char keys[][8] = { "the", "a", "there", "answer", "any", "by", "bye", "their" };116 117 char output[][32] = { "Not present in trie", "Present in trie" };118 119 trie_t trie;120 initialize(&trie);121 122 // Construct trie123 for (int i = 0; i < ARRAY_SIZE(keys); i++)124 {125 insert(&trie, keys[i]);126 }127 128 // Search for different keys129 printf("%s --- %s\n", "the", output[search(&trie, "the")]);130 printf("%s --- %s\n", "these", output[search(&trie, "these")]);131 printf("%s --- %s\n", "their", output[search(&trie, "their")]);132 printf("%s --- %s\n", "thaw", output[search(&trie, "thaw")]);133 134 return 0;135 }
Trie 的应用
- 字符串检索：事先将已知的一些字符串（字典）的有关信息保存到 Trie 里，查找另外一些未知字符串是否出现过或者出现频率。
- 字符串最长公共前缀：Trie 利用多个字符串的公共前缀来节省存储空间，反之，当我们把大量字符串存储到一棵 Trie 上时，我们可以快速得到某些字符串的公共前缀。
- 排序：Trie 树是一棵多叉树，只要先序遍历整棵树，输出相应的字符串，便是按字典序排序的结果。
- 作为其他数据结构和算法的辅助结构：如后缀树，AC自动机等。
字典树
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。