4

I am coding in Java and I need a sorted data structure of Integers that has a maximum of O(log(n)) insertion time and O(1) lookup by index. Is there an inbuilt data-structure that can do this, or if not, how do I program one myself?

I know that a Set can accomplish the first task, but to lookup element i, I would need to iterate over all the elements before i.

Improve this question
6
  • 1
    You can combine a tree-set with a hash-set... Commented Apr 8, 2017 at 18:52
  • I don't know if this is even possible. I suspect if it is possible, it'd require some highly complex data structure that performs worse in practice than a sorted ArrayList (linear insertion, constant lookup by index) or a self-balancing tree with child count info (logarithmic insertion and lookup by index). Commented Apr 8, 2017 at 18:55
  • There is no builtin, sorted data type that you can lookup an element by its index (where I assume its index represents the size of the collection when the element is inserted). However I did create something like this that I can post if you'd like! I believe what I had written is immutable, but it's possible to make it mutable if you change every index when an element is removed. Commented Apr 8, 2017 at 19:22
  • I think there is a confusion here. Does index i mean 'the ith element inserted' or 'the ith smallest element'? If it's the first, then just combine a list with a set. If it's the second, my gut tells me it is quite difficult to build (and perhaps impossible) Commented Apr 8, 2017 at 19:52
  • @WillemVanOnsem: That doesn't give O(1) lookup by index. Commented Apr 9, 2017 at 1:12

1 Answer 1

Reset to default
3

Possible solutions are trees that keep track of the number of child elements which Wikipedia refers to as "Order statistic trees". Lookup performance however would be tied to the height of tree, which is O(log n).

Trees that fan out quickly, like B-trees could reduce lookup by index significantly, although it will always remain O(log n).

Unfortunately, there is no such tree available in Java's collections framework. A couple of days of work and testing should however yield a reasonable implementation :)

Improve this answer
Sign up to request clarification or add additional context in comments.

3 Comments

That's the correct way to do it IMHO. However, the difficulty with this solution is that you will also need to implement the BST balancing yourself (with red-black trees for example, like is used by TreeMap). TreeMap's implementation is more than 3000 lines long.
TreeMap contains a lot of other stuff, I remember a Red Black implementation being around 200 lines orso.
Come to think of it, I once wrote a BTreeList structure, which allows fast insertion at any point, and fast get-by-index performance. It doesn't keep itself sorted, but combined with binary searches it can be kept sorted easily. The code looks old, I may dust it off and put it on github. I wrote it specifically for the use case of large sorted directories of files where you need to maintain both an index and a sort order.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.