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

我已经增加了一些基本的方法来打印树，找到根，最小/ 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。 。

Answer 2

我不明白为什么你应该有过任何引用问题 - 左/右/父节点可以被复制，就像在这个伪代码。

你应该能够将其扩展到C＃没有太多的大惊小怪 - 除非你正在使用的“裁判”的关键字，在这种情况下，你很可能得到不可预知的结果。

或许，如果你能证明你其实已经写了迄今为止的代码，我们可以帮助调试。

Answer 3

我的建议：

• 不包括父指针。它们对于插入或删除算法不是必需的，并且会使您的代码更加复杂。例如，LeftRotate只能使用一个参数编写，如果不使用父指针，则其大小只有一半。
• 使用的enum为Color属性，而不是一个string，并在构造函数初始化它。
• 如果您尚未阅读this article。