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).
I think you mean $successor$ &amp; $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 &gt; 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.

A doubly linked list would work just as well (in which case you save pointers to the list in the tree nodes, from which you can go to next or previous list node for successor/ predecessor respectively)

btw, your example is wrong. the key '77' cannot be in the right subtree of '80'