2

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?

ideasman42
  • 42,413
  • 44
  • 197
  • 320
Ned
  • 355
  • 2
  • 9
  • 24
  • What's a key update? Removing a key-value pair, re-inserting the value under a new key? –  Mar 27 '14 at 10:03
  • @delnan while re-inserting is typically used - there would be times updating in-place is faster. It's an interesting question! - Did anyone try this? – ideasman42 Oct 30 '17 at 23:54

1 Answers1

2

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.

Mohsen Kamrani
  • 7,177
  • 5
  • 42
  • 66
  • 2
    This answer seems incomplete, an algorithm could at least check if the order is unchanged with relation to other nodes. And while I don't _know_ if its possible, it seems plausible that certain operations could be performed without a full delete+insert. – ideasman42 Oct 30 '17 at 02:09