5

我正在大学学习算法课程,对于我的一个项目,我想在 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'关键字。

我究竟做错了什么 ?

4

3 回答 3

2

因为在你的方法体中你这样做:

root = y;

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

于 2010-02-12T14:35:55.290 回答
1

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

您应该能够毫不费力地将其扩展为 C# - 除非您使用 'ref' 关键字,在这种情况下,您很可能会得到不可预知的结果。

也许如果你能展示你到目前为止实际编写的代码,我们可以帮助调试它。

于 2010-02-12T13:06:12.007 回答
1

我的建议:

  • 不要包含父指针。它们对于插入或删除算法不是必需的,并且会使您的代码更加复杂。例如LeftRotate,可以只用一个参数编写,如果不使用父指针,长度大约是原来的一半。
  • enum对属性使用Colora 而不是 a string,并在构造函数中对其进行初始化。
  • 如果你还没有阅读这篇文章。
于 2010-02-12T13:06:50.713 回答