首页 > 试题广场 >

在ASC算法team日常开发中，常常面临一些数据结构的抉择，

[单选题]
在ASC算法team日常开发中，常常面临一些数据结构的抉择，令人纠结。目前大家在策划一个FBI项目（Fast Binary Indexing），其中用到的词汇有6200条，词汇长度在10-15之间，词汇字符是英文字母，区分大小写。请在下面几个数据结构中选择一个使检索速度最快的： 
  • 二叉搜索树，比较函数开销：1次运算/每字符
  • 哈希表，hash算法开销：10次运算/每字符
  • 链表，比较函数开销：1次运算/每字符
  • TRIE树，寻找子节点开销：1次运算/每字符
添加回答
推荐
埃菲尔丶头像 埃菲尔丶
注解:又称单词查找树，Trie树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希表高。
编辑于 2015-02-04 20:54:26 回复(3)
牛客716774926号头像 牛客716774926号
TRIE树 寻找子节点一次开销是1，平均长度10-15，平均开销应该是13.
而哈希表没有冲突的情况下，只需要考虑哈希函数的开销，是10.
为什么不是B?
发表于 2020-07-28 10:16:34 回复(1)
sunwuyi头像 sunwuyi
哈希的复杂度不是o（1）吗？
发表于 2018-10-12 08:45:10 回复(5)
Aix码哥头像 Aix码哥
D
百度百科http://baike.baidu.com/link?url=PYYfck8aXrrJhPjyi1Ay52qBXccRDmdOY4BvLAu_hOxOFEA7yWYqux9LGPLWVJFjChZPNDYeIEOL5eKGm8jRejdW1Fdu0LFyZpxW2LUIQJxkPZSPylBiAcqb2TFK0rZTvs9wrxiwuYzPo0yNrOo8-q
发表于 2015-07-01 16:48:40 回复(0)
为什么不问问神奇海螺呢头像 为什么不问问神奇海螺呢
对于TRIE树（字典树）来说，能在O(len)的时间内查出该单词是否存在，而且空间占用少。
发表于 2018-12-07 14:57:53 回复(0)
SpringSnow头像 SpringSnow
注解:又称单词查找树，Trie树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。它的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希表高。
发表于 2019-06-19 20:29:34 回复(0)
爱恩彬头像 爱恩彬
其实这几个选项我都有点看不懂，最后面的1次运算/每字符是什么意思？
发表于 2018-08-31 15:22:16 回复(0)
纠结的哈士奇在笔试头像 纠结的哈士奇在笔试
TRIE树又称单词查找树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。他的优点是：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希表高
发表于 2023-04-26 09:43:34 回复(0)
空耳air头像 空耳air
今天做到这个了，根本不懂
发表于 2022-09-10 17:25:19 回复(0)
Andrew9646头像 Andrew9646

概念：又称单词查找树，Trie树，是一种树形结构，是一种哈希树的变种。典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），

应用场景：经常被搜索引擎系统用于文本词频统计。

优点：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希表高。

这样看舒服一点
发表于 2021-08-14 10:03:01 回复(0)
牛客670767258号头像 牛客670767258号
FBI??
发表于 2021-05-07 22:50:47 回复(0)
牛客818246740号头像 牛客818246740号
<p>trie树是哈希树的改版</p>
发表于 2020-06-30 11:36:45 回复(0)
黑闪⚡头像 黑闪⚡
咋这么多种树，有的都没见过
发表于 2020-05-12 15:54:50 回复(0)
已注销头像 已注销
字典树
发表于 2018-09-14 14:49:27 回复(0)
sky_头像 sky_
哈希的复杂度不是o（1）吗？
发表于 2017-05-28 18:18:51 回复(1)
向宇铜桌头像 向宇铜桌
这题用trie树空间复杂度要炸裂啊。。。。
发表于 2017-01-26 10:47:44 回复(4)
🔍搜索offer中头像 🔍搜索offer中
trie单词查找树
发表于 2016-10-08 08:49:39 回复(0)
提交观点

问题信息

树
来自：阿里巴巴2010搜索研...
难度：
17条回答 13816浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号