alan
alan

Reputation: 21

Question About Node Replacement Strategy in Linux Red-Black Tree: Why Not Simply Swap Data Instead of Nodes?

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

Answers (0)

Related Questions