# Augmenting a tree such that we preserve the insertion operation optimal runtime

Suppose we are given a red-black tree with $$n$$ vertices with distinct keys and we want to store, as addition information in each vertex $$v$$, the biggest key out of the keys that are smaller than $$v$$ (or nothing if it doesn't exist). Can we insert a new element in this tree in $$O(\log n)$$ time?

I think that we can. My idea is that while traversing the tree in order to determine where to insert the new element, we could just update this additional information for every vertex that we encounter. The problem with this is that we may not update all the required vertices, for instance:

        (80)
/      \
(1)      (81)
/   \     /   \
(0) (79) (77)  (82)


Here, if we would try to insert $$76$$, we would not update the additional information in the vertex with value $$77$$ if we use the method I described above.

I would like strongly appreciate hints to improve my solution (mostly I would want only hints).

• If that were a binary search tree, we should have 80 > 77 > 81. Please correct your example. – Apass.Jack Mar 21 at 17:20
• Hint, if some entry should be updated, then find and update it. Note that $O(\log n)+O(\log n)$ time is still $O(\log n)$ time. – Apass.Jack Mar 21 at 17:22
• @Apass.Jack I see, you're saying that we construct a binary search tree by taking an array of numbers and then inserting them 1 by 1. If that were the case, doesn't my idea work? And regarding your second comment, how could we determine which vertices we should update without traversing the whole tree? – user101904 Mar 21 at 17:30

I think you mean $$successor$$ & $$predecessor$$.
Formally: $$predecessor(v): x$$ s.t $$x \leq v$$ (or smaller if your keys are distinct) and no $$y$$ exists in your structure s.t $$y \leq v$$ and $$y > x$$
Symmetrical definition for $$successor(v)$$.
You can apply several methods for each node to know its $$successor/predecessor$$ in $$O(1)$$ time. A simple option is pointers - you "pay" $$log(n)$$ while inserting, pay another $$log(n)$$ to find $$successor/predecessor$$, and update the corresponding fields.