Search code examples
red-black-tree

Update Node in Red Black Tree

I searched the answer, but I could not find it. If we want to update a node in a red-black tree, What do you have to do ?

The general solution appears in my mind is to delete the node that we want to update and reinsert it with new content. Is there any alternative solution to this ?

Solution

  • If the change alters the key data such that the node belongs in a different tree location then yes you need to remove and re-insert the node (you don't necessarily have to delete it as in free the node object but the tree does have to be rebalanced twice - once for the remove and once for the insert).

    If the change does not alter the node order then you just apply the change and nothing further need be done.