What is the name of the data structure that is a tree on the backend but has a list like API?

Question

I'm looking for the name of a data structure. It is organized like a balanced tree. The elements need not be comparable. Instead of asking if the tree contains a thing (like you would with a collection of comparables), you can query for any k'th element in logarithmic time. You can insert before or after any k'th element. So the API is a bit like a list, except all operations are logarithmic.

I think "rope" might be similar but those seem to be restricted to strings only. It could be thought of as a segment tree, where every leaf has a weight of 1, but instead of storing the weights in the leaves the entry itself is stored.

Edit: I think it could also be referred to as an "Order Statistic Tree" but without the comparison operations.

Answer 1

In "Optimal Algorithms for List Indexing and Subset Rank" by Paul F. Dietz this data structure is called an "indexed list" and an algorithm is given that has complexity $O(\log n / \log\log n)$ for all operations. Unfortunately this term has little value as a search term.

While that is complex data structure note that you can transform any self-balanced tree into the data structure you want. Just replace the key field of each node with a field that keeps track of the number of elements to the left of it, and update this on inserts/deletes (takes $O(\log n)$ time). Then use that field as your key when searching for element $i$ in the tree.

Also check out "tiered vectors".

Answer 2

The skip list is not a balanced tree "under the hood", but is almost (probabilistically) tree-like.

It satisfies your "functional requirements" in that it has $O(\log n)$ insertion, and I believe* that you can make it so that it can give you the $k$th element in $O(\log n)$ time.

If you keep the list ordered, you can do queries in $O(\log n)$ time.