algorithm - 如何在任何树数据结构中为单个键存储多个值？

Question

我知道有一种名为 MultiMap 的数据结构，它是一种类似表的结构，具有 O(n) 线性搜索时间。我想有一个更好的搜索时间。因此，想知道我是否可以使用树结构或其变体(请建议)。

编辑:

好的，MultiMap 根据其实现的答案/文档进行 O(log n) 搜索和遍历。

1. 但我很困惑为什么将 n 记录为，如图所示:

因为首先，我必须转到第 n 个元素(我正在寻找的那个)，然后我将输入它的值(一个列表)，将遍历列表并找到值，或者简单地检索列表本身(值)？

1. 任何人都可以建议，BST 或 B-Tree 我应该选择其中一个来存储我的文本文件中的数据，该文本文件包含 10,000 行，每行的结构类似于 123 3456 4567 5678 321 (我喜欢更多 10,000 行这样的代码)在给出 123 时搜索 321，反之亦然。

我认为 B-Tree 是一个不错的选择，但我不确定，另一件事是搜索 321，我如何想象将 123 作为键存储，将 321 作为它的值存储？

** 可以有多个 123 3456 4567 5678 989，123 3456 4567 5678 787 所以这就是为什么我假设具有多个值的数据结构的键应该对此有所帮助.

Answer 1

多图的搜索时间复杂度是对数，不是线性的。

例如，实现该功能的实现是 C++ std::multimap ，它提供了一个 multimap::find方法，其中提到:

Complexity

Logarithmic in size.