Uri*_*Uri 10 trie data-structures
我最喜欢的大学数据结构之一就是Trie.如果共享前缀,它是一个很好的数据结构,用于保存大量字符串.查找也很好,因为它们是在字符串的O(| length |)处完成的,无论集合中有多少字符串.
相比之下,平衡树的设置项数量为O(log N),加上您为比较支付的费用.哈希表将涉及哈希计算,比较等.
因此,令我惊讶的是,在大多数语言的标准库中没有Trie实现.
我能想到的唯一原因是内存访问成本太高的可能性.如果进行树查找,则不是在调查O(log N)位置,而是在进行O(| length |)不同的位置,并产生所有后果.如果字符串很长,这可能会导致太多.
所以我想知道:我刚才描述的问题有多少？当您需要存储大型字符串或字符串映射时,您会怎么做？