Is there a data structure with the following operations?

• get(idx) -> Item gets the item at index idx.
• insert(idx, item) inserts item at index idx in the structure. Should be O(log N) worst case.
• delete(idx) deletes item at index idx.
• track_index(idx) -> Handle gives a "handle" associated with the item at idx, so that I can later use the next function to ask what the index of that item is.
• retrieve_index(handle) -> index returns the current index of the item associated with the handle created by the previous function.

I would like all of these to have O(log N) worst-case runtime.

I already have an idea on how to implement it (I'm thinking AVL tree with each node storing the number of its left and right descendants), but I want to know if there is already a name for something like this, or if it is possible to repurpose some other common data structures to get these operations.

EDIT: My item data type is not totally nor partially ordered.

CodePudding user response：

You can use any of the self-balancing search trees (AVL, red-black, B-tree, B -tree, ...) and augment their nodes with a node count attribute which is kept updated during manipulations. Similarly, you can augment a Skip List with such properties.

This will allow for retrieving/inserting/removing elements by their index with O(logn) time complexity.

The "handle" would be the pointer to where the value is found in the tree, and by threading the tree (i.e. including parent pointers), such handle gives complete information as to where the value is in the tree, allowing for getting its index, its predecessor or successor.

CodePudding user response：

One option for a data structure with these properties is a balanced binary search tree. This type of tree has O(log N) insertion, deletion, and search time complexity, as well as the ability to track the indices of items in the tree.