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。