我正在尝试在 C# 中实现一棵红黑树。我已经创建了一个名为 sRbTreeNode 的对象,它具有字符串键、颜色、左、右和父属性。我成功地实现了方法 Insert、InsertFixUp、LeftRotate、RightRotate、Delete,现在我遇到了方法 DeleteFixUp 的问题。
DeleteFixUp 负责在删除后再次平衡树(使用旋转和更改节点颜色)。
我尝试从一本名为“算法简介”的书中找到的伪代码实现该方法。
这是我的代码:
private static void DeleteFixup(ref sRbTreeNode root, sRbTreeNode x)
{
sRbTreeNode y;
while (x != root && x.Color == BLACK)
{
if (x == x.Parent.Left) // determine sub tree from parent
{
y = x.Parent.Right; // y is x's sibling
if (y.Color == RED)
{ // x is black, y is red - make both black and rotate
y.Color = BLACK;
x.Parent.Color = RED;
LeftRotate(ref root, x.Parent);
y = x.Parent.Right;
}
if (y.Left.Color == BLACK &&
y.Right.Color == BLACK)
{ // children are both black
y.Color = RED; // change parent to red
x = x.Parent; // move up the tree
}
else
{
if (y.Right.Color == BLACK)
{
y.Left.Color = BLACK;
y.Color = RED;
RightRotate(ref root, y);
y = x.Parent.Right;
}
y.Color = x.Parent.Color;
x.Parent.Color = BLACK;
y.Right.Color = BLACK;
LeftRotate(ref root, x.Parent);
x = root;
}
}
else
{ // right subtree - same as code above with right and left swapped
y = x.Parent.Left;
if (y.Color == RED)
{
y.Color = BLACK;
x.Parent.Color = RED;
RightRotate(ref root, x.Parent);
y = x.Parent.Left;
}
if (y.Right.Color == BLACK &&
y.Left.Color == BLACK)
{
y.Color = RED;
x = x.Parent;
}
else
{
if (y.Left.Color == BLACK)
{
y.Right.Color = BLACK;
y.Color = RED;
LeftRotate(ref root, y);
y = x.Parent.Left;
}
y.Color = x.Parent.Color;
x.Parent.Color = BLACK;
y.Left.Color = BLACK;
RightRotate(ref root, x.Parent);
x = root;
}
}
}
x.Color = BLACK;
}
我每次在不同的地方都会遇到错误“对象引用未设置为对象的实例”......
我在互联网上搜索了这个的实现,刚刚找到了一篇关于 CodeProject 的文章,它的实现和我完全一样。我尝试复制他们的代码,希望我的眼睛错过了一些东西,但它也没有工作......
有人可以帮我,在我开始扯头发之前!!... ?? :)