Possible to update nodes key in a red-black tree, without removing and inserting?

Question

Typically changes to a key in a red-black tree need to be performed by removing, then re-inserting the node.

Is it possible to performs key updates to a node in a red black tree that is more efficient than delete+insert?

Answer 1

Implement update with [search if required +] delete + insert

1 - delete the key O(log n)
2 - insert a new node with the new key O(log n)
Even if you search for a key first, it's O(log n).

See this page for more details on RBT.