1
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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".

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.