Balanced tree with constant-time successor and predecessor given node pointers?

Question

I was asked this question, which I personally find hard:

Create a data structure that can:

Insert elements, Remove elements, Search Elements, In time O(log n)

In addition, It should have the following two functions which work in time O(1):

1. next(x): given a pointer to the node of value x, return a pointer to the node with the smallest bigger value than x.

2. previous(x) given a pointer to the node of value x, return a pointer to the node with the biggest smallest value than x.

Answer 1

If each node contains a pointer to its successor and a pointer to its predecessor, or equivalently - if you maintain both a doublely linked list and a tree, where each node in the tree points to its equivalent node in the list and vice versa - you'll get want you want. Updating the list on insert/delete is O(1) (after locating the closest node in the tree). Searching is performed on the tree. Succesor / predecessor are performed on the list.

Answer 2

@RogerLindsjö's idea from the comments is a good one. Essentially, keep a regular, balanced BST, then thread a doubly-linked list through the nodes keeping them in sorted order. That way, given a pointer to a node in the tree, you can find the largest value smaller than it or the smallest value greater than it simply by following the next or previous pointers in each node.

You can maintain this list through insertions and deletions without changing the overall runtime of an insert or delete. For example, here's how you might do an insertion of an element x:

1. Do a standard BST successor query to find the smallest value larger than x in the tree, and a standard BST predecessor query to find the largest value smaller than x in the tree. Each search takes time O(log n) to complete.
2. Do a regular BST insertion to insert x. Then, set its next and previous pointers to the two elements you found in the previous step, and update those nodes to point to your new node x. This also takes time O(log n).

The total time for the insertion is then O(log n), matching what a balanced tree can provide.

I'll leave it to you to figure out deletion, which can similarly maintain the linked list pointers without changing the overall cost of the operation.