我已经实现了一棵红黑树,但效果不佳。它以不正确的方式插入节点。我认为这是因为 FixUp。有谁知道我错在哪里?当我插入(1、4、9、16)时。在节点 16,它将根颜色设置为红色。然后它停止。
我已经调试了它,但我自己无法找到错误。我是 c# 的新手,而且我现在已经工作了大约 3 个小时。没有成功。
这是我的代码:
public void insert(int score, int spelersnummer)
{
size++;
Node z = new Node(score, spelersnummer);
z.leftChilds++;
Node y = null;
Node x = this.root;
while (x != null)
{
y = x;
if (z.boom < x.boom) // boom staat voor score!
{
x.leftChilds++;
x = x.left;
}
else
{
x = x.right;
}
}
if (y == null)
{
this.root = z;
}
else if (z.boom < y.boom)
{
y.left = z;
y.leftChilds++;
z.parent = y;
}
else
{
y.right = z;
z.parent = y;
}
// Z heeft automatisch left = null, right = null, color = red
insertFixUp(z);
}
public void insertFixUp(Node z)
{
// check of parent bestaat en parent.parent NullPointerException?
if(z.parent != null && z.parent.parent != null)
{
while (z != null && z.parent != null && z.parent.parent != null && !z.parent.isBlack) // ass long as color is not black, thus red
{
if (z.parent == z.parent.parent.left)
{
Node y = z.parent.parent.right;
if (y != null && !y.isBlack)
{
z.parent.isBlack = true;
y.isBlack = true;
z.parent.parent.isBlack = false;
z = z.parent.parent;
}
else if (z == z.parent.right)
{
z = z.parent;
leftRotate(z);
}
z.parent.isBlack = true;
z.parent.parent.isBlack = false;
rightRotate(z.parent.parent);
}
else
{
Node y = z.parent.parent.left; // left instead of right
if (y != null && !y.isBlack) // is red?
{
z.parent.isBlack = true; // color = black
y.isBlack = true; // color = black
z.parent.parent.isBlack = false; // color = red
z = z.parent.parent;
}
else
{
if (z == z.parent.left) // left instead of right
{
z = z.parent;
rightRotate(z);
}
z.parent.isBlack = true; // color is black
z.parent.parent.isBlack = false; // color is red
leftRotate(z.parent.parent);
}
}
}
}
}
public void leftRotate(Node x)
{
Node y = x.right;
x.right = y.left;
if (y != null && y.left != null)
{
y.left.parent = x;
}
y.parent = x.parent;
if (x.parent == null)
{
root = y;
}
else if (x.parent.left != null && x == x.parent.left)
{
x.parent.left = y;
}
else
{
x.parent.right = y;
}
y.left = x;
x.parent = y;
int lefts;
lefts = (x.left != null) ? x.left.leftChilds : 0;
x.leftChilds = lefts + 1;
lefts= (y.left != null) ? y.left.leftChilds : 0;
y.leftChilds = lefts + 1;
}
public void rightRotate(Node x)
{
Node y = x.left;
x.left = y.right;
if (y != null && x != null && y.right != null)
{
y.right.parent = x;
}
y.parent = x.parent;
if (x.parent == null)
{
root = y;
}
else if (x.parent.right != null && x == x.parent.right)
{
x.parent.right = y;
}
else
{
x.parent.left = y;
}
y.right = x;
x.parent = y;
int lefts;
lefts = (x.left != null) ? x.left.leftChilds : 0;
x.leftChilds = lefts + 1;
lefts = (y.left != null) ? y.left.leftChilds : 0;
y.leftChilds = lefts + 1;
}