java - 具有 O(logN) 插入的排序数据结构，提供插入点索引

Question

我的目标是一个可以完成两件事的排序数据结构:

快速插入(根据排序顺序在位置)

我可以快速地将我的数据分割成大于或小于或等于一个元素的所有内容的集合。 我需要知道每个分区的大小 ，并且我需要能够“获取”这些分区。

目前，我正在使用 ArrayList 在 java 中实现它。这很容易提供＃2，因为我可以执行二进制搜索( Collections.binarySearch )并获得一个插入索引，告诉我将在什么时候插入一个元素。然后基于索引范围从 0 到数组大小的事实，我立即知道有多少元素大于我的元素或小于我的元素，并且我可以轻松获取这些元素(作为子列表)。但是，这没有属性 #1，并导致过多的数组复制。

这让我想使用像 SkipList 或 RedBlackTree 这样可以更快地执行插入的东西，但是我不知道如何在不花费 O(N) 时间的情况下满足属性#2。

任何建议，将不胜感激。谢谢

编辑:感谢以下引用数据结构的答案，这些数据结构在 O(logN) 时间内执行插入并且也可以快速分区，但我想强调 size() 要求 - 我需要知道这些分区的大小必须遍历整个分区(其中， according to this 是 TreeSet 所做的。这背后的原因是，在我的用例中，我使用多个不同的数据结构副本维护我的数据，每个副本使用不同的比较器，然后需要询问“根据什么比较器是大于特定元素最小的所有事物的集合”。在 ArrayList 的情况下，这实际上很容易，并且只需要 O(YlogN) 其中 Y 是比较器的数量，因为我只是二进制搜索每个 Y 数组并返回具有最高插入索引的数组列表。我不清楚如何在不采用 O(YN) 的情况下使用 TreeSet 来实现这一点。

我还应该补充一点，即使无法准确解决插入索引的近似答案，它仍然很有值(value)。

Answer 1

使用通用 Java TreeSet .插入需要 O(logN)，因此您的第 1 个要求已完成。这是文档中的引用:

This implementation provides guaranteed log(n) time cost for the basic operations (add, remove and contains).

并且因为它实现了 NavigableSet interface ，您有 #2 或您的要求，使用以下方法:

tailSet(someElem) 返回 Set从 someElem 开始查看直到最后一个元素

headSet(someElem) 返回 Set从第一个元素开始查看直到 someElem

subSet(fromElem, toElem) 返回 Set从 fromElem 开始查看直到 toElem

这些操作被包含/排除提供的边界的版本重载。
TreeSet非常灵活:它允许您定义 Comparator订购 Set以自定义方式，或者您也可以依赖元素的自然顺序。

编辑:

根据返回子集的要求 size()操作至 不是 是 O(n) ，恐怕Java API中没有临时实现。

是的， TreeSet 返回的 Collection View 范围操作，实现 size()通过“跳转”到 O(log n) 中 View 的第一个元素时间，然后迭代后续元素，每次迭代加1，直到到达子集的末尾。

我必须说这很不幸，因为并不总是需要遍历返回的子集 View ，但有时，提前知道子集的大小可能非常有用(因为它是您的用例)。

因此，为了满足您的要求，您需要另一个结构，或者至少需要一个辅助结构。经过一番研究，我建议您使用 Fenwick tree . Fenwick 树也称为二进制索引树 (BIT)，可以是不可变的或可变的。不可变版本是用数组实现的，而可变版本可以用平衡二叉树实现，即红黑树(Java TreeSet 实际上是作为红黑树实现的)。 Fenwick 树主要用于存储频率并计算直到 O(log n) 中给定元素的所有频率的总和。时间。

请引用 this question here on Stack Overflow对于这个完全未知但非常有用的结构的完整介绍。 (由于堆栈溢出中的解释，我不会在这里复制它)。

Here's another Stack Overflow question询问如何正确初始化 Fenwick 树和 here's actual Java code showing how to implement Fenwick tree's operations .最后， here's a very good theoretic explanation关于所使用的结构和底层算法。

Web 中所有示例的问题在于它们使用结构的不可变版本，这不适合您，因为您需要在向结构中添加元素的过程中交错查询。但是，它们对于完全理解所使用的结构和算法都非常有用。

我的建议是你学习 Java TreeMap的实现，看看如何修改/扩展它，以便您可以将其变成保留 1 的 Fenwick 树作为每个键的值。这个 1将是每个键的频率。所以Fenwick树的基本操作 getSum(someElement)实际上会返回从第一个元素到 someElement 的子集的大小, 在 O(log n)时间。

因此，挑战在于实现一个平衡树(实际上是 Java 的 Red-Black TreeMap 的后代)，它实现了您需要的所有 Fenwick 树的操作。我相信你会完成 getSum(somElement) ，但也许您也可以扩展返回的子树范围 View ，以便它们都引用 getSum(someElelment)实现时 size()范围 View 的操作。

希望这会有所帮助，至少我希望这是一个很好的起点。请让我知道您是否需要澄清以及示例。