首页 > 代码库 > Trie字典树算法
Trie字典树算法
特性
Trie树属于树形结构,查询效率比红黑树和哈希表都要快。假设有这么一种应用场景:有若干个英文单词,需要快速查找某个单词是否存在于字典中。使用Trie时先从根节点开始查找,直至匹配到给出字符串的最后一个节点。在建立字典树结构时,预先把带有相同前缀的单词合并在同一节点,直至两个单词的某一个字母不同,则再从发生差异的节点中分叉一个子节点。
节点结构:
每个节点对应一个最大可储存字符数组。假设字典只存26个小写英文字母,那么每个节点下应该有一个长度为26的数组。换言说,可存的元素类型越多,单个节点占用内存越大。如果用字典树储存汉字,那么每个节点必须为数千个常用汉字开辟一个数组作为储存空间,占用的内存实在不是一个数量级。不过Trie树就是一种用空间换时间的数据结构,鱼和熊掌往往不可兼得。
建树细节:
- 取要插入字符串的首个字符,从根节点的孩子节点开始,匹配当前字符是否已有节点,有则把指针指向该节点。无则为该字符创建节点,并把指针指向该新建节点。
- 迭代。
- 遇到要插入字符串末尾结束符时停止迭代,并把最后一个非’\0′字符对应的节点设为末端节点。
查找细节:
循环取要插入字符串的首个字符,从根节点的孩子节点开始,匹配当前字符是否已有节点,有则继续循环,无则返回False. 直至匹配到最后一个字符则完成查找。
树结构图:
我们用apps, apply, apple, append, back, basic, backen几英文单词创建树形结构:
上图很容易看出,有相同前缀的英文单词,会合并在同一个节点,Trie树顺着一个个节点进行检索,直至找到最后一个节点。代码如下:
1 #include <stdio.h> 2 3 struct trie_node 4 { 5 static const int letter_count = 26; 6 7 int count; 8 bool is_terminal; 9 char letter;10 trie_node* childs[letter_count];11 12 trie_node()13 : letter(0), count(1), is_terminal(false)14 {15 for (int i = 0; i < letter_count; ++i)16 childs[i] = NULL;17 }18 };19 20 class trie21 {22 public:23 trie()24 : root_node_(NULL)25 {26 }27 28 ~trie()29 {30 delete_trie(root_node_);31 }32 33 public:34 trie_node* create()35 {36 trie_node* n = new trie_node();37 return n;38 }39 40 void insert(const char* str)41 {42 if (!root_node_ || !str)43 root_node_ = create();44 45 trie_node* next_element_node = root_node_;46 while (*str != 0)47 {48 char element_index = *str - ‘a‘;49 if (!next_element_node->childs[element_index])50 {51 next_element_node->childs[element_index] = create();52 }53 else54 {55 next_element_node->childs[element_index]->count++;56 }57 58 next_element_node = next_element_node->childs[element_index];59 next_element_node->letter = *str;60 str++;61 }62 63 next_element_node->is_terminal = true;64 }65 66 bool find_word_exists(const char* str)67 {68 if (!root_node_ || !str)69 return NULL;70 71 trie_node* element_node = root_node_;72 do73 {74 element_node = element_node->childs[*str - ‘a‘];75 if (!element_node) return false;76 str++;77 } while (*str != 0);78 79 return element_node->is_terminal;80 }81 82 void delete_trie(trie_node* node)83 {84 if (!node) return;85 for(int i = 0; i < trie_node::letter_count; i++)86 {87 if(node->childs[i] != NULL)88 delete_trie(node->childs[i]);89 }90 91 delete node;92 }93 94 private:95 trie_node* root_node_;96 };
转:http://powman.org/archives/trie.html
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。