c# - 红黑树删除问题C#

Question

我正在尝试用 C# 实现红黑树。我已经创建了一个名为 sRbTreeNode 的对象，它具有 String 键、Color、Left、Right 和 Parent 属性。 我成功地实现了 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 上找到了一篇文章，它的实现和我做的一模一样。我尝试复制他们的代码，希望我的眼睛遗漏了什么，但它也没有用......

有人可以帮助我，在我开始扯掉我的头发之前!!...？？ :)

Answer 1

虽然这可能不是您问题的直接答案，但您将通过在调试器中单步执行代码来学到 难以置信的知识。 另外您可能会自己解决问题!如果您需要帮助设置断点、检查变量或步进，请告诉我。 Visual Studio 非常易于使用，几乎让人脑残。