Reputation: 21
I'm looking at the node replacement method in the Linux Red-Black tree implementation (rb_replace_node
). To replace the victim
node with newnode
, all pointers that were pointing to victim
are redirected to newnode
, and then newnode
's color, parent, left child, and right child pointers are replaced with those of victim
. This has me puzzled: why can't we simply replace the key
and data
fields of victim
with those of newnode
? This approach would seemingly achieve the same effect without actually swapping the two node variables, and it might be more efficient.
Here is the code snippet of rb_replace_node:
void rb_replace_node(struct rb_node *victim, struct rb_node *newnode,
struct rb_root *root)
{
struct rb_node *parent = victim->rb_parent;
/* Set the surrounding nodes to point to the replacement */
if (parent) {
if (victim == parent->rb_left)
parent->rb_left = newnode;
else
parent->rb_right = newnode;
} else {
root->rb_node = newnode;
}
if (victim->rb_left)
victim->rb_left->rb_parent = newnode;
if (victim->rb_right)
victim->rb_right->rb_parent = newnode;
/* Copy the pointers/colour from the victim to the replacement */
*newnode = *victim; //color,parent,left,right are assigned, not including key and data
}
My assumption is
void rb_replace_node(struct rb_node *victim, struct rb_node *newnode,
struct rb_root *root)
{
victim->key=newnode->key;
victim->data=newnode->data;
delete newnode;
}
Could someone explain why the more direct approach isn't taken?
Upvotes: 0
Views: 35