A rare array with the index O (1) and O (1) prev and next

Question

I want to implement a data structure with operations as related to arrays, i.e. indexing and linked list - quick access to the previous / next item. It looks like a sparse array, but memory is not a concern - the problem is time complexity.

Requirements:

• - an integer with a limited range of 1..N - you can allow yourself to allocate an array for it (i.e. memory is not a problem)

Operations:

• insert(key, data) - O (1)
• find(key) - O (1) - returns a "node" with data
• delete(node) - O (1)
• next(node) - O (1) - find the next busy node, in order by key
• prev(node) - O (1)

I was thinking about implementing in an array with pointers to the next / previous occupied element, but I have problems with the insert operation - how to find the previous and next elements, i.e. place in the double linked list where to put a new element - I do not know how to do this O(1) .

If this is not possible, please provide evidence.

Answer 1

You can do this with the Van Emde Boas tree .

The tree supports the required operations:

 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 of your keys have 16-bit integers from 0 to 65535, m will 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 will have O (1) complexity.

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

DETAILS

This tree works using a large array of child trees.

For example, suppose we have 16-bit keys. An array of 2 ^ 8 (= 256) child trees will be stored in the first layer of the tree. The first child is responsible for keys from 0 to 255, the second for keys 256, 257, .., 511, etc.

This makes it easy to find if a node is present, since we can simply jump directly to the corresponding element in the array.

However, this alone would make it difficult to find the next element, since we might need to find 256 child trees to find a nonzero element.

The Van Emde Boas tree contains two add-ons that make it easy to find the following item:

• For each tree, min and max are stored, so O (1) works to see if we have reached our limits.
• The auxiliary tree is used to store indices of nonzero children. This auxiliary tree is a Van Emde Boas tree the size of the square root of the original size.