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;
    }
}

我已经添加了一些打印树的基本方法,找到root,min/max键(按字母表)等等...

我在插入节点时遇到问题(因此,构建树).熟悉红黑树的人都知道,在向一侧添加节点时,您可能已经改变了树的平衡.要解决此问题,您需要围绕树上的节点"旋转"以平衡树.

我在伪代码中编写了一个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;

你需要传入root一个ref修饰符。node不需要，因为node它本身永远不会更新以指向不同的 ndoe。。