set + nth element : fast implementation

Question

For the following data structure:

• add an element in O(lg(n))
• remove an element in O(lg(n))
• find the k'th element in O(lg(n))

we can use a balanced BST which each node has size of it's subtree, but it needs to implement red-black tree which is not fast to code.

any better solution?

Answer 1

The general type of structure you are looking for is qualified with Indexed or Indexable, that is a structure augmented with count to be able to access elements by indexes.

You could use either:

• an Indexed Tree: Binary Search Tree (Red-Black Tree, AVL Tree), B-Tree, Finger-Tree, ...
• an Indexed Skip-List

(and perhaps a few others :p)

I tend to think that Skip-Lists are easier to implement than BST, as you can use a randomized height instead of all the balancing stuff.