Вопрос о стратегии замены узлов в Linux «Красно-черное дерево»: почему бы просто не поменять местами данные вместо узлов ⇐ Linux

[Anonymous]

Я рассматриваю метод замены узлов в реализации красно-черного дерева Linux (

Код: Выделить всё

rb_replace_node). Чтобы заменить узел жертвы

на новый узел, все указатели, указывающие на жертву, перенаправляются на новый узел, а затем цвет нового узла, родительский, слева. дочерний элемент, а указатели правого дочернего элемента заменяются указателями жертвы. Это меня озадачило: почему мы не можем просто заменить поля key и data жертвы на поля newnode? Этот подход, по-видимому, позволит достичь того же эффекта без фактической замены двух переменных узла и может быть более эффективным.
Вот фрагмент кода 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
}

Мое предположение:

Код: Выделить всё

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;
}

Может ли кто-нибудь объяснить, почему не используется более прямой подход?


Подробнее здесь: https://stackoverflow.com/questions/787 ... not-simply