"prefix list"数据结构的名称?



我正在为我的数据结构寻找一个好名字,它包含列表的所有"以开头"的子列表,例如:

Given list: [A, B, C]
My data structure: [ [A], [A, B], [A, B, C] ]

请注意,我的数据结构只包括有序组合(例如,不包括[C, B, A]),而不包括所有组合(例如不包括[B, C])。只有所有前缀(在某种程度上)。

这种数据结构有正确的数学/编程术语吗?

使用TRIE。你可以在互联网上的资源上阅读更多关于这个数据结构的信息。

如果我们想要查找和前缀搜索这两种操作,Trie是合适的。它主要用于字典和拼写检查器。使用Trie,我们可以支持O(n)时间中的所有操作,如插入、搜索、删除,其中n是要处理的单词的长度。

Trie的另一个优点是,我们可以按字母顺序打印所有单词。

使用Trie的缺点是它使用了更多的内存。要解决此问题,您可以阅读关于三元搜索树

最新更新