1

我正在尝试在 C# 中实现一棵红黑树。我已经创建了一个名为 sRbTreeNode 的对象，它具有字符串键、颜色、左、右和父属性。我成功地实现了方法 Insert、InsertFixUp、LeftRotate、RightRotate、Delete，现在我遇到了方法 DeleteFixUp 的问题。

DeleteFixUp 负责在删除后再次平衡树（使用旋转和更改节点颜色）。

我尝试从一本名为“算法简介”的书中找到的伪代码实现该方法。

这是我的代码：

private static void DeleteFixup(ref sRbTreeNode root, sRbTreeNode x)
    {
        sRbTreeNode y;

        while (x != root && x.Color == BLACK)
        {
            if (x == x.Parent.Left)         // determine sub tree from parent
            {
                y = x.Parent.Right;         // y is x's sibling 
                if (y.Color == RED)
                {   // x is black, y is red - make both black and rotate
                    y.Color = BLACK;
                    x.Parent.Color = RED;
                    LeftRotate(ref root, x.Parent);
                    y = x.Parent.Right;
                }
                if (y.Left.Color == BLACK &&
                    y.Right.Color == BLACK)
                {   // children are both black
                    y.Color = RED;      // change parent to red
                    x = x.Parent;                   // move up the tree
                }
                else
                {
                    if (y.Right.Color == BLACK)
                    {
                        y.Left.Color = BLACK;
                        y.Color = RED;
                        RightRotate(ref root, y);
                        y = x.Parent.Right;
                    }
                    y.Color = x.Parent.Color;
                    x.Parent.Color = BLACK;
                    y.Right.Color = BLACK;
                    LeftRotate(ref root, x.Parent);
                    x = root;
                }
            }
            else
            {   // right subtree - same as code above with right and left swapped
                y = x.Parent.Left;
                if (y.Color == RED)
                {
                    y.Color = BLACK;
                    x.Parent.Color = RED;
                    RightRotate(ref root, x.Parent);
                    y = x.Parent.Left;
                }
                if (y.Right.Color == BLACK &&
                    y.Left.Color == BLACK)
                {
                    y.Color = RED;
                    x = x.Parent;
                }
                else
                {
                    if (y.Left.Color == BLACK)
                    {
                        y.Right.Color = BLACK;
                        y.Color = RED;
                        LeftRotate(ref root, y);
                        y = x.Parent.Left;
                    }
                    y.Color = x.Parent.Color;
                    x.Parent.Color = BLACK;
                    y.Left.Color = BLACK;
                    RightRotate(ref root, x.Parent);
                    x = root;
                }
            }
        }

        x.Color = BLACK;
    }

我每次在不同的地方都会遇到错误“对象引用未设置为对象的实例”......

我在互联网上搜索了这个的实现，刚刚找到了一篇关于 CodeProject 的文章，它的实现和我完全一样。我尝试复制他们的代码，希望我的眼睛错过了一些东西，但它也没有工作......

有人可以帮我，在我开始扯头发之前！！... ?? :)

4

4 回答 4

1

虽然可能不是您问题的直接答案，但您只需在调试器中单步执行您的代码， 就会学到很多东西。另外，您可能会自己解决问题！如果您需要帮助设置断点、检查变量或步进，请告诉我。Visual Studio 使用起来非常简单，几乎是脑死亡。

于 2010-02-22T21:57:56.050 回答
1

经过一番研究，我发现问题出在我处理我建造的红黑树的方式上。

根据有关该主题的书籍（包括我正在学习的书籍！），您应该让树​​底部的每个节点都指向一个“空节点”。空节点是没有值且颜色为黑色的节点。我以为我不必在我的树上实现空节点，并且在每个检查黑色节点的地方，我添加了“|| node == null”，因为它可能正在检查空节点。问题是有时您需要检查空节点的父节点，如果您实际上没有实现“空节点”，那么在尝试访问它的 Parent 属性时会出现错误。

我通过向每个没有子节点的节点添加一个具有空值和黑色的节点来实现一个“空节点”。它需要对树上的大多数操作方法进行一些调整，但最终它（几乎）解决了我所有的问题。

感谢大家试图帮助我！:)

于 2010-03-10T14:29:47.387 回答
0

有空参数滑入某处。

如果x == null，那么我们一测试就崩溃了if。

如果x.Parent' 的任何孩子为空，我们也会崩溃。

您需要测试这些空条件并适当地处理它们。

于 2010-02-22T21:41:47.157 回答
0

让我们来看看...

   while (x != root && (x == null || x.Color == BLACK))
    {
        if (x == x.Parent.Left)         // determine sub tree from parent

因此，如果 x 在开始时为 null，则尝试取消对 x.Parent 的引用，这将引发您得到的异常。我看了两行，已经发现了一个错误。

在取消引用之前，您需要在某个时候检查每个引用是否为 null。

于 2010-02-22T21:42:22.307 回答