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