Проблема с удалением узла в Red-Black-Tree (код C)

Я пытаюсь построить скелет Красно-Черного Дерева, согласно алгоритмам Кормена.

На данный момент Insert, Search и InsertFixup, а также любые связанные с ними методы (например, вращение влево\вправо) работают правильно.

Моя проблема связана с удалением узла - дерево не исправляется должным образом.

Я сравниваю свое дерево после удаления узла с деревом в следующем симуляторе RB-TREE: https://www.cs.usfca.edu/~galles/visualization/RedBlack.html

Алгоритмы, которые я использую: RB-DELETE

/*
RB-DELETE(T, z)
1 if left[z] = nil[T] or right[z] = nil[T]
2    then y ← z
3    else y ← TREE-SUCCESSOR(z)
4 if left[y] ≠ nil[T]
5    then x ← left[y]
6    else x ← right[y]
7 p[x] ← p[y]
8 if p[y] = nil[T]
9    then root[T] ← x
10    else if y = left[p[y]]
11            then left[p[y]] ← x
12            else right[p[y]] ← x
13 if y != z
14    then key[z] ← key[y]
15         copy y's satellite data into z
16 if color[y] = BLACK
17    then RB-DELETE-FIXUP(T, x)
18 return y

УДАЛИТЬ-ИСПРАВИТЬ

 RB-DELETE-FIXUP(T, x)
 1 while x ≠ root[T] and color[x] = BLACK
 2     do if x = left[p[x]]
 3           then w ← right[p[x]]
 4                if color[w] = RED
 5                   then color[w] ← BLACK                        ▹  Case 1
 6                        color[p[x]] ← RED                       ▹  Case 1
 7                        LEFT-ROTATE(T, p[x])                    ▹  Case 1
 8                        w ← right[p[x]]                         ▹  Case 1
 9                if color[left[w]] = BLACK and color[right[w]] = BLACK
 10                   then color[w] ← RED                          ▹  Case 2
 11                        x p[x]                                  ▹  Case 2
 12                   else if color[right[w]] = BLACK
 13                           then color[left[w]] ← BLACK          ▹  Case 3
 14                                color[w] ← RED                  ▹  Case 3
 15                                RIGHT-ROTATE(T, w)              ▹  Case 3
 16                                w ← right[p[x]]                 ▹  Case 3
 17                         color[w] ← color[p[x]]                 ▹  Case 4
 18                         color[p[x]] ← BLACK                    ▹  Case 4
 19                         color[right[w]] ← BLACK                ▹  Case 4
 20                         LEFT-ROTATE(T, p[x])                   ▹  Case 4
 21                         x ← root[T]                            ▹  Case 4
 22        else (same as then clause with "right" and "left" exchanged)
 23 color[x] ← BLACK

И мой фактический код:

<сильный>1. Пересадить

static void RBTreeTransplant(RBtree_node_t ** pRoot,
    RBtree_node_t * pDeletedNode, RBtree_node_t * pBrother) {
if (NULL == pDeletedNode->parent) {
    *pRoot = pBrother;
} else if (pDeletedNode == pDeletedNode->parent->left) {
    pDeletedNode->parent->left = pBrother;
} else {
    pDeletedNode->parent->right = pBrother;
}

pBrother->parent = pDeletedNode->parent;
} // RBTreeTransplant

<сильный>2. УдалитьFixUp

static void RBDeleteFixUp(RBtree_node_t ** pRoot, RBtree_node_t * pNode) {
RBtree_node_t * pAidNode = NULL;

while ((pNode != *pRoot) && (pNode->color == RB_COLOR_BLACK)) {
    if (pNode == pNode->parent->left) {
        pAidNode = pNode->parent->right; // pAidNode is pNode's brother

        // CASE1: pNode's brother is RED:
        // * Paint pNode's brother(pAidNode) BLACK
        // * Paint pNode's parent RED
        // * Left Rotate pNode's parent
        // * point pAidNode to pNode's Parent right children
        if (pAidNode->color == RB_COLOR_RED) {
            pAidNode->color = RB_COLOR_BLACK;
            pNode->parent->color = RB_COLOR_RED;
            RBRotate(pRoot, pNode->parent, RB_ROTATE_LEFT);
            pAidNode = pNode->parent->right;
            continue;
        } // CASE1

        // CASE2: pNode's brother is BLACK and both his childrens are BLACK
        // * Paint pNode's brother(pAideNode) RED
        // * point pNode to pNode's parent
        if ((pAidNode->left->color == RB_COLOR_BLACK)
                && (pAidNode->right->color == RB_COLOR_BLACK)) {
            pAidNode = RB_COLOR_RED;
            pNode = pNode->parent;
            continue;
        } // CASE2

        //CASE3: pNode's brother and his brother right children is BLACK
        // * Paint pAidNode LEFT children as BLACK
        // * Paint pAidNode as RED
        // * Right Rotate pAidNode
        // * point pAidNode to pNode parent right children
        else if (pAidNode->right->color == RB_COLOR_BLACK) {
            pAidNode->left->color = RB_COLOR_BLACK;
            pAidNode->color = RB_COLOR_RED;
            RBRotate(pRoot, pAidNode, RB_ROTATE_RIGHT);
            pAidNode = pNode->parent->right;
            continue;
        } // CASE3

        //CASE4: pNode's brother is BLACK, and his brother right children is RED
        // * Paint pAidNode as pNode's parent
        // * Paint pNode's parent BLACK
        // * Paint pAidNode right children BLACK
        // * Left Rotate pNode's parent
        // * Set pNode as the new root
        pAidNode->color = pNode->parent->color;
        pNode->parent->color = RB_COLOR_BLACK;
        pAidNode->right->color = RB_COLOR_BLACK;
        RBRotate(pRoot, pNode->parent, RB_ROTATE_LEFT);
        pNode = *pRoot;
    }
} // while

pNode->color = RB_COLOR_BLACK;
 } // RBTreeDeleteFixUp

<сильный>3. УзелУдалить

static StatusType RBNodeDelete(RBtree_node_t ** pRoot,
    RBtree_node_t * pNode) {
RBtree_node_t * pAidNode = pNode;
RBtree_node_t * pExtraAidNode = NULL;
RBtree_color originalNodeColor = RB_COLOR_BLACK;

if ((NULL == pRoot) || (NULL == *pRoot) || (NULL == pNode)) {
    return INVALID_INPUT;
}

originalNodeColor = pNode->color;

// CASE1: Node to delete has no LEFT.
if (NULL == pNode->left) {
    pExtraAidNode = pNode->right;
    RBTreeTransplant(pRoot, pNode, pNode->right);
} // End of CASE1

// CASE2: Node to delete has LEFT but has no RIGHT
else if (NULL == pNode->right) {
    pExtraAidNode = pNode->left;
    RBTreeTransplant(pRoot, pNode, pNode->left);
} // End of CASE2

// CASE3: Node to delete has both children
else {
    pAidNode = RBTreeMin(pNode->right); // Find Successor
    originalNodeColor = pAidNode->color; // Save color of successor
    pExtraAidNode = pAidNode->right;

    if (pAidNode->parent == pNode) { // Successor has no LEFT cause its nill
        pExtraAidNode->parent = pAidNode;
    } else {
        RBTreeTransplant(pRoot, pAidNode, pAidNode->right);
        pAidNode->right = pNode->right;
        pAidNode->right->parent = pAidNode;
    }

    RBTreeTransplant(pRoot, pNode, pAidNode);
    pAidNode->left = pNode->left;
    pAidNode->left->parent = pAidNode;
    pAidNode->color = pNode->color;
} // End of CASE3

if (originalNodeColor == RB_COLOR_BLACK) {
    RBDeleteFixUp(pRoot, pExtraAidNode);
}

// Free allocated node memory
RBTreeSingleNodeDestroy(pNode);

return SUCCESS;

Я буду рад узнать, что я делаю неправильно в моем delete\deletefixup, что портит реализацию удаления.

Спасибо!


c red-black-tree
person Adiel    schedule 18.01.2015    source источник
comment
Я удивлен, что ваш DeleteFixUp работает. В случае 2 у вас есть pAidNode = RB_COLOR_RED;, но вы должны назначить цвет узла, а не сам узел. Вам также не хватает регистра else самого высокого уровня внутри цикла while, который соответствует этой части псевдокода: else (same as then clause with "right" and "left" exchanged). Вы разместили правильный код?   -  person Sanfer    schedule 11.07.2016

Ответы (2)


arrow_upward
0
arrow_downward

Я надеюсь, что добавлю ответ в тему правильно.

Похоже, вся моя проблема была не в коде,

но ссылка на симулятор RBTREE, с которой я сравнивал.

Не уверен, что на самом деле происходит на этом сайте, но после того, как почти сдался и вручную проверил полученное дерево после удаления из него узлов -

кажется, что после каждого удаления я получаю идеально сбалансированное красное черное дерево со всеми реализованными функциями.

Извините за трату вашего времени.

Спокойной ночи

person Adiel    schedule 18.01.2015

arrow_upward
0
arrow_downward

В зависимости от последовательности вставок и удалений мы можем создать два RB-дерева, содержащие одинаковые ключи, но имеющие разную форму. Конечно, при такой последовательности конечное дерево всегда должно быть одним и тем же. Симулятор в этом смысле полезен (хотя в вашем случае он оказывается сломанным?!).

В любом случае может быть полезно иметь функцию, которая проверяет, действительно ли данное дерево является RB-деревом.

Если вы хотите проверить правильность RB-дерева, вы можете попробовать это:

/**
 * This functions returns:
 *   - -1 if the tree is not valid
 *   - The number of black nodes in a path from the root to a leaf otherwise
 */
int isRBTreeValid(RBTree_node_t *root) {
    int isBlack = 1, leftBlackNodes, rightBlackNodes;
    // A leaf is black, leaves are NULL nodes.
    if (!root)
        return 1;
    // The children of a red node are black
    if (RB_COLOR_RED == root->color) {
        if ((root->left && RB_COLOR_RED == root->left->color) ||
            (root->right && RB_COLOR_RED == root->right->color)) {
            return -1;
        }
        isBlack = 0;
    }
    if (0 > (leftBlackNodes = isRBTreeValid(root->left)))
        return -1;
    if (0 > (rightBlackNodes = isRBTreeValid(root->right)))
        return -1;
    // There must be the same number of black nodes in each path from the root to a leaf.
    if (leftBlackNodes != rightBlackNodes)
        return -1;
    return isBlack + leftBlackNodes;
}

Чтобы завершить проверку, вы должны убедиться, что корень черный. Вы можете обернуть это в:

int isRBTreeReallyValid(RBTree_node_t *root) {
    return (!root) ||
        (RB_COLOR_BLACK == root->color && 0 < isRBTreeValid(root));
}
person Rerito    schedule 20.01.2015
comment
Эй, спасибо за код! после неудачного опыта потраченных часов, думая, что моя функция удаления неверна, я также создал свой собственный метод, который делает именно то, что делает ваша программа. Тем не менее, ценю ваши усилия, извините и спасибо :-) - person Adiel; 21.01.2015