Skip to content

Instantly share code, notes, and snippets.

//if there is no red nodes under X so we have to check childrens of sibling of X
else
{
//if sibling is on the left side so you have to make double rotation
if (isRed(s.left) && treeDirection == TreeDirection.Right)
{
//left left ->single rotation
RotateRight(s, s.parent);
TreeColor temp = p.treeColor;
p.treeColor = TreeColor.Black;
x.treeColor = temp;
s.treeColor = temp;
if(s.right != null)
s.right.treeColor = TreeColor.Black;
}
else if (isRed(s.right) && treeDirection == TreeDirection.Right)
{
//left right ->double
SingleLeftRotation(s.right, s, s.parent);
RotateRight(s.right, s);
x.treeColor = TreeColor.Red;
p.treeColor = TreeColor.Black;
}
else if (isRed(s.right) && treeDirection == TreeDirection.Left)
{
//right right -> single rot
RotateLeft(s, s.parent);
TreeColor temp = p.treeColor;
p.treeColor = TreeColor.Black;
x.treeColor = temp;
s.treeColor = temp;
if(s.left!=null)
s.left.treeColor = TreeColor.Black;
}
else if (isRed(s.left) && treeDirection == TreeDirection.Left)
{
//right left -> double
SingleRightRotation(s.right, s, s.parent);
RotateRight(s.right, s);
x.treeColor = TreeColor.Red;
p.treeColor = TreeColor.Black;
}
else
{
//all childrens of s are black recolor p,x,s
TreeColor temp = x.parent.treeColor;
x.parent.treeColor = x.treeColor;
x.treeColor = temp;
s.treeColor = temp;
}
}
}
root.treeColor = TreeColor.Black;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment