1. 简述 Trie 树是一种高效的字符串查找的数据结构。可用于搜索引擎中词频统计,自动补齐等。 在一个Trie 树中插入、查找某个单词的时间复杂度是 O(len), len是单词的长度。 如果采用平衡二叉树来存储的话,时间复杂度是 O(lgN), N为树中单词的总数。 此外,Trie 树还特别擅长 前缀搜索,比方说现在输入法中的自动补齐,输入某个单词的前缀,abs, 立刻弹出 abstract 等单词。 Trie 树优良的查找性能是建立在 牺牲空间复杂度的基础之上的。 本文将给出一个 Trie树的简单实例,并用这…

2014年4月25日 0条评论 4点热度 阅读全文