C#引用麻烦

Question

我正在大学学习算法课程，对于我的一个项目，我想用 C# 实现一棵红黑树（实现本身不是项目，但只是我决定选择帮助我的东西） 。

我的红黑树应该保存字符串键，我为每个节点创建的对象如下所示：

class sRbTreeNode
{
    public sRbTreeNode Parent = null;
    public sRbTreeNode Right = null;
    public sRbTreeNode Left = null;
    public String Color;
    public String Key;

    public sRbTreeNode()
    {
    }

    public sRbTreeNode(String key)
    {
        Key = key;
    }
}

我已经添加了一些用于打印树、查找根、最小/最大键（按字母表）等的基本方法...

我在插入节点时遇到问题（因此构建树）。 熟悉红黑树的人都知道，当向一侧添加节点时，您可能会改变树的平衡。 要解决此问题，您需要围绕树上的节点“旋转”以平衡树。

我用伪代码编写了 RightRotate 和 LeftRotate 方法，然后当我尝试用 C# 实现它时，我创建的 sRbTreeNode 对象遇到了一堆引用问题。

这是我为 LeftRotate 方法编写的伪代码：

LeftRotate(root, node)
    y <- node.Right;
    node.Right <- y.Left;
    if (y.Left != null)
        y.Left.Parent <- node;
    y.Parent <- node.Parent;
    if (node.Parent = null)
        root <- y;
    else
        if (node = node.Parent.Left)
            node.Parent.Left = y;
        else
            node.Parent.Right = y;
    y.Left <- node;
    node.Parent <- y

我收到了直接实现它的建议，但不使用我最初尝试过的“ref”关键字。 这就是我所做的：

public static void LeftRotate(sRbTreeNode root, sRbTreeNode node)
    {
        sRbTreeNode y = node.Right;
        node.Right = y.Left;
        if (y.Left != null)
            y.Left.Parent = node;
        y.Parent = node.Parent;
        if (node.Parent == null)
            root = y;
        else
            if (node == node.Parent.Left)
                node.Parent.Left = y;
            else
                node.Parent.Right = y;
        y.Left = node;
        node.Parent = y;
    }

现在，当我调试时，我发现它工作正常，但是我传递给此方法的对象仅在该方法的范围内旋转。当它离开这个方法时，看起来实际的节点没有改变。这就是为什么我首先想到使用“ref”关键字。

我做错了什么？

Answer 1

因为在方法的主体中，您执行以下操作：

root = y;

您需要使用 ref 修饰符传递 root 。 node 不需要，因为 node 本身永远不会更新以指向不同的 ndoe。
。

Answer 2

我不明白为什么您应该对引用有任何问题 - 可以像在这个伪代码中一样复制左/右/父节点。

您应该能够将其扩展到 C# 而无需太多麻烦 - 除非您使用“ref”关键字，在这种情况下您很可能会得到不可预测的结果。

也许如果您可以显示到目前为止您实际编写的代码，我们可以帮助调试它。

Answer 3

我的建议：

• 不要包含父指针。它们对于插入或删除算法不是必需的，并且会使您的代码更加复杂。例如，LeftRotate 只需要一个参数即可编写，如果不使用父指针，长度将缩短一半左右。
• 使用枚举作为Color属性而不是字符串，并在构造函数中对其进行初始化。
• 如果您还没有阅读本文，请阅读。