Created
April 8, 2018 13:51
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
//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