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

Question

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).