实现一个站内导航搜索 引子 前缀Trie, 又叫字符Tire, trie来自单词retrieval, 一开始念作tree,后来改念try, 毕竟它与树是不一样的东西。网上许多文章都搞混了trie与树。 trie是通过”边“来储存字符的一种树状结构,所谓边就是节点与节点间的连接。trie每条边只能存放一个字符。 它与hash树很相似,或者说它是哈希树的变种,哈希树是用边来存放一个整数(可以是一位数或两位数)。前树Tire与哈希树都是多叉树,换言之,父节点有N个子节点。前缀Tire主要用于字符串的快速检索,查询效率比哈希表高。前缀Trie的核心思想是空间换时间。利用字符串的公共前缀来降低...