Augmenting a tree such that we preserve the insertion operation optimal runtime
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'