What is a data structure that supports fast next-higher-element and next-lower-element?

Question

Specifically I want O(log n) insertion/deletion times and O(1) operation for find_next_higher_element which given an element in the data structure returns the element just greater than it in constant time. I don't know if this is even possible but my intuition tells me it is.

Answer 1

Any threaded tree will do.

Finger trees can also be adapted to nicely handle iteration.

Answer 2

A B+Tree structure allows for O(1) next/previous operation as all elements are in a linked list of leaf pages.

Answer 3

A red-black tree will allow you to insert and delete in O(log n) time, but next-higher/lower may take O(log n).

You can remedy this though, by putting the nodes of the tree in a doubly linked list. On insert or delete, you can find the next higher/lower nodes and fix up the linking pointers.

There's a long discussion of maintaining trees with efficient iteration in The Art of Computer Programming by Knuth.

Answer 4

I think almost all tree structures can be modified in a way such that this works.

You "just" have to add a doubly-linked list "below" the tree storing the actual elements. Elements in the tree are then just for navigational issues. Note that adding this doubly-linked list increases the amount of work to be done when inserting and deleting elements. The asymptotic runtimes will not be changed (at least in most cases).