c# - 根的红黑树删除

Question

除非删除根，否则我的红黑树删除算法运行良好。其中只有一个 child 被保存，其余的树值都丢失了。

我认为问题出在 removeNode() 方法中，其中

if (remove == root)
{
    root = child;
} 

下面是删除的方法:

//Searching for value to remove
public void removeSearch(int value)
{
    RedBlackNode rt = root;
    while (rt != sentinel)
    {
        int compare = value.CompareTo(rt.getItem());
        if (compare == 0)
        {
            if (rt.getLeft() == sentinel || rt.getRight() == sentinel)
            {
                removeNode(rt);
            }
            else
            {
                RedBlackNode successor = inOrderSuccessor(rt);
                rt.setItem(successor.getItem());
                removeNode(rt);                        
            }
            return;
        }
        else
        {
            rt = rt.getChild(compare);
            //return true;
        }
    }
}

protected RedBlackNode inOrderSuccessor(RedBlackNode node)
{
    RedBlackNode descendant = node.getRight();

        while (descendant.getLeft() != sentinel)
        {
            descendant = descendant.getLeft();
        }
    return descendant;
}

protected void removeNode(RedBlackNode remove)
{
    count -= 1;
    RedBlackNode child;
    if (remove.getLeft() != sentinel)
    {
        child = remove.getLeft();
    }
    else
    {
        child = remove.getRight();
    }
    linkParentAndChild(remove.getParent(), child, comparison(remove, remove.getParent()));

    if(remove==root)
    {
        root = child;
    }
    if(remove.isBlack())
    {
        DeleteFix(child);
    }
}

protected void DeleteFix(RedBlackNode node)
{
    while((node!=root)&&(node.isBlack()))
    {
        RedBlackNode parent = node.getParent();
        int compare = comparison(node, parent);
        RedBlackNode sibling = parent.getChild(-compare);
        if(sibling.isRed())
        {
            sibling.setBlack();
            parent.setRed();
            rotate(-compare, parent);
            sibling = node.getParent().getChild(-compare);
        } 
        if(sibling.hasTwoBlackChildren())
        {
            sibling.setRed();
            node = node.getParent();
        }else
        {
            if(sibling.getChild(-compare).isBlack())
            {
                sibling.getChild(compare).setBlack();
                sibling.setRed();
                rotate(compare, sibling);
                sibling = parent.getChild(-compare);
            }
            sibling.setColour(parent.getColour());
            parent.setBlack();
            sibling.getChild(-compare).setBlack();
            rotate(-compare, parent);
            node = root;
        }
    }
    node.setBlack();
}

任何帮助都会很棒。谢谢

Answer 1

和我一起过一遍:

if (remove.getLeft() != sentinel)
{
    child = remove.getLeft();
}
else
{
    child = remove.getRight();
}
linkParentAndChild(remove.getParent(), child, comparison(remove, remove.getParent()));

if(remove==root)
{
    root = child;
}

首先，假设remove == root。然后，假设根的左 child 是 sentinel。第一个 if 分支评估为 false，执行 else 子句，并且 child 成为右节点。然后，您尝试获取根的父级(大概是 null 但我不知道)并将其链接到正确的节点......我想这最终什么都不做但我没有肯定知道，因为您没有提供该方法。然后，您将根替换为 child，这是正确的节点，因为 linkParentAndChild 被(大概)传入了 null，所以没有办法恢复左节点，所以你破坏它然后它就消失了。如果左侧节点不是 sentinel，则过程完全相同，但您将保留左侧而不是右侧。

希望这能弄清楚为什么会发生这种情况。我不会告诉你如何解决它，原因有二:

1. 这几乎肯定是家庭作业，除非是为了家庭作业，否则没有人会实现红黑树。
2. 我不太记得红黑树的实现细节，主要是因为第一个原因。

祝你好运!