C++ : Running time of next() and prev() in a multiset iterator?

What is the time complexity of applying the next() and prev() function on an multiset<int>::iterator type object where the corresponding multiset contains the N elements?

I understand that in STL, a multiset is implemented as a balanced binary search tree and hence I expect the time complexity to be O(log N) per operation (in the worst case) but have a hunch that this should be O(1) on average.

But what if the tree is implemented as follows - when inserting element x in the balanced binary search tree, we can also retrieve the the largest number in the tree smaller than x and the smallest number in the tree larger than x in O(log N). Thus in theory, we can have each node in the tree maintain pointer to its next and prev elements so that next() and prev() then run in constant time per query.

Can anybody share some light on what's up?