Sparse array with O(1) indexing and O(1) prev and next

Question

I want to implement data structure with operations both pertinent to arrays - i.e. indexing, and linked list - quick access to prev/next item. Resembles sparse array, but the memory is not a concern - the concern is time complexity.

Requirements:

• key is integer with a limited range 1..N - you can afford to allocate an array for it (i.e. memory is not a concern)

Operations:

• insert(key, data) - O(1)
• find(key) - O(1) - returns the "node" with data
• delete(node) - O(1)
• next(node) - O(1) - find next occupied node, in the ordering given by key
• prev(node) - O(1)

I was thinking of implementation in an array with pointers to the next/prev occupied item, but I have problems in the insert operation - how do I find the prev and next items, i.e. the place in the double linked list where to put the new item - I don't know how to make this O(1).

If this is not possible please provide a proof.

Answer 1

You can do this with a Van Emde Boas tree.

The tree supports the operations you require:

Insert: insert a key/value pair with an m-bit key
Delete: remove the key/value pair with a given key
Lookup: find the value associated with a given key
FindNext: find the key/value pair with the smallest key at least a given k
FindPrevious: find the key/value pair with the largest key at most a given k

And the time complexity is O(logm) where m is the number of bits in the keys.

For example if all your keys are 16 bit integers between 0 and 65535, m would be 16.

EDIT

If the keys are in the range 1..N, the complexity is O(loglogN) for each of these operations.

The tree also supports min and max operations, which would have complexity O(1).

• Insert O(loglogN)
• Find O(loglogN)
• Delete O(loglogN)
• Next O(loglogN)
• Prev O(loglogN)
• Max O(1)
• Min O(1)

DETAILS

This tree works by using a large array of children trees.

For example, suppose we had 16 bit keys. The first layer of the tree would store an array of 2^8 (=256) children trees. The first child is responsible for keys from 0 to 255, the second for keys 256,257,..,511, etc.

This makes it very easy to lookup to see whether a node is present as we can simply go straight to the corresponding array element.

However, by itself this would make finding the next element hard as we might need to search 256 children trees to find a nonzero element.

The Van Emde Boas tree contains two additions that make it easy to find the next element:

1. A min and max is stored for each tree so it is O(1) work to see whether we have reached our limits
2. An auxiliary tree is used to store the indexes of non-zero children. This auxiliary tree is a Van Emde Boas tree of size the square root of the original size.