java - 字典数据结构+快速复杂度方法

Question

我正在尝试从头开始构建一个能够容纳大量字典(单词/字符)的数据结构。

“单词”可以由任意多的字符组成。

字典需要标准方法，例如搜索、插入、删除。

我需要这些方法的时间复杂度优于 O(log(n))，所以介于O(log(n)) 到 O(1)，例如 log(log(n))

其中 n = 字典大小(元素数量)

我研究了各种树结构，例如具有 log(n) 方法(不够快)的 b 树以及似乎最适合字典的 trie，但是由于单词可以任意大，它的复杂度似乎不会比 log(n) 快。

如果可以，请提供任何解释

Answer 1

trie 对内存有很大的要求，但访问时间通常比 O(log n) 快。

如果我没记错的话，访问时间取决于单词的长度，而不是结构中单词的数量。

效率和内存消耗还取决于您选择使用的 trie 的具体实现。那里有一些非常有效的实现。

有关 Tries 的更多信息，请参阅:

http://en.wikipedia.org/wiki/Trie

http://algs4.cs.princeton.edu/52trie/

http://algs4.cs.princeton.edu/52trie/TrieST.java.html

https://www.topcoder.com/community/data-science/data-science-tutorials/using-tries/