1

是否有在 java 中实现的数据结构提供以下保证：

  • 元素总是排序的
  • 添加一个元素至少执行 O(lg n)
  • 在特定索引处获取元素至少执行 O(lg n)

基本上我希望能够做到以下几点：

SomeDataStructure elements = new SomeDataStructure();
elements.add(5);
elements.add(1);
elements.add(10);
assertEquals(1, elements.get(0));
assertEquals(5, elements.get(1));
assertEquals(10, elements.get(2));

其中add和get方法都至少在 O(lg n) 时执行。

这似乎应该能够用树结构来完成，但我找不到任何提供索引 get 方法的实现。我还研究了为此使用/扩展 java.util.TreeMap ，但所有的旋转逻辑都是私有的，所以我无法跟踪树是如何被改变的。

4

3 回答 3

0

看起来您可以使用TreeMap, 然后添加一个get遍历树以获取该索引的方法？

您也许可以使用keySet迭代器按顺序遍历它们，但没有关于其性能的文档。

于 2012-08-01T16:59:54.490 回答
0

如果您不需要交错读取和写入 - 即，您想一次构建所有数据结构，然后在其中查找内容，而无需在构建后对其进行修改 - 那么我会简单地构建一个列表，对其进行排序，然后在列表中使用索引。在这种情况下，一棵树是多余的，因为在构建它时不需要保持结构的排序。

List<Integer> elements = new ArrayList<Integer>(3);
elements.add(5);
elements.add(1);
elements.add(10);

Collections.sort(elements);

assertEquals(1, elements.get(0));
assertEquals(5, elements.get(1));
assertEquals(10, elements.get(2));

每次添加发生在 O(1) 时间（因此添加 n 项需要 O(n)），排序发生在 O(n * log(n)) 时间，给你一个 O(n + n * log) 的整体复杂度(n)) = O(n * log(n)) 用于构建结构。这与每次在 O(log(n)) 时间内添加 n 个元素相同。但是，查找将在恒定 (O(1)) 时间内发生，从而为您提供比基于树的解决方案更好的效率。

如果您想保证结构永远不会被修改（即永远不会丢失其排序），您可以将上面的第 5 行替换为：

elements = Collections.unmodifiableList(Collections.sort(elements));

如果有人试图修改列表，这将引发异常，这将提示您正在发生错误。

于 2012-08-01T17:19:12.150 回答
-1

来自 TreeMap 的JavaSE 文档：

此实现为 containsKey、get、put 和 remove 操作提供有保证的 log(n) 时间成本。

您可以通过查找有关您正在使用的任何实现的信息来找到相同的信息。

于 2012-08-01T16:17:32.213 回答