This file contains hidden or 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
///SOFTSAM | |
///You can use this code wherever you want... | |
using System; | |
namespace RedBlackTrees | |
{ | |
enum TreeDirection:byte { None=0,Right,Left} | |
class RedBlackTree | |
{ | |
Node root = null; | |
#region Insertion | |
public void Insert(int data) | |
{ | |
if (root == null) | |
{ | |
Node newNode = new Node(data); | |
root = newNode; | |
root.treeColor = TreeColor.Black; | |
return; | |
} | |
InsertRec(root, root, root, data); | |
} | |
void InsertRec(Node node, Node parent, Node grandP, int data) | |
{ | |
if (node == null) | |
{ | |
Node newNode = new Node(data); | |
if (data < parent.data) | |
{ | |
parent.left = newNode; | |
newNode.parent = parent; | |
} | |
else if (data > parent.data) | |
{ | |
parent.right = newNode; | |
newNode.parent = parent; | |
} | |
node = newNode; | |
} | |
else | |
{ | |
if (data < node.data) | |
InsertRec(node.left, node, node.parent, data); | |
if (data > node.data) | |
InsertRec(node.right, node, node.parent, data); | |
} | |
bool isBalanced = IsTreeBalanced(node); | |
if (isBalanced == false) | |
BalanceTree(node); | |
} | |
#endregion | |
#region Balancing Section | |
private bool IsTreeBalanced(Node node) | |
{ | |
if (node.parent != null) | |
return !(node.treeColor == TreeColor.Red && node.parent.treeColor == TreeColor.Red); | |
return true; | |
} | |
private void BalanceTree(Node node) | |
{ | |
Node grandParent = node.parent.parent; | |
Node parent = node.parent; | |
Node uncle = null; | |
if (grandParent.right != parent) | |
uncle = grandParent.right; | |
else | |
uncle = grandParent.left; | |
//CASE 1: | |
//if uncle is nil then it means it is black | |
//but if it is not nil or black then we need to apply first case | |
if (uncle != null && uncle.treeColor == TreeColor.Red) | |
{ | |
uncle.treeColor = TreeColor.Black; | |
parent.treeColor = TreeColor.Black; | |
grandParent.treeColor = TreeColor.Red; | |
} | |
//CASE 2: | |
else if (uncle == null || uncle.treeColor == TreeColor.Black) | |
{ | |
//Left Left situation | |
if (grandParent.left != null && parent.left != null && grandParent.left == parent && parent.left == node) | |
{ | |
// Console.WriteLine("left left situation"); | |
RotateRight(parent, grandParent); | |
} | |
//right right situation | |
else if (grandParent.right != null && parent.right != null && grandParent.right == parent && parent.right == node) | |
{ | |
// Console.WriteLine("right right situation"); | |
RotateLeft(parent, grandParent); | |
} | |
//right left situation | |
else if (grandParent.right != null && parent.left != null && grandParent.right == parent && parent.left == node) | |
{ | |
// Console.WriteLine("right left situation"); | |
SingleRightRotation(node, parent, grandParent); | |
RotateLeft(node, node.parent); | |
} | |
//left right situation | |
else if (grandParent.left != null && parent.right != null && grandParent.left == parent && parent.right == node) | |
{ | |
// Console.WriteLine("left right situation"); | |
SingleLeftRotation(node, parent, grandParent); | |
RotateRight(node, node.parent); | |
} | |
} | |
//find root from current node | |
root = node; | |
while (node != null) | |
{ | |
root = node; | |
node = node.parent; | |
} | |
//root is always black. it might be diffirent node | |
root.treeColor = TreeColor.Black; | |
PrintColors(); | |
} | |
#endregion | |
#region Rotating Section | |
private void SingleLeftRotation(Node node, Node parent, Node grandParent) | |
{ | |
Node temp = node.left; | |
//node is parents parent now | |
node.left = parent; | |
parent.parent = node; | |
//so node is the new child of gp | |
grandParent.left = node; | |
node.parent = grandParent; | |
parent.right = temp; | |
if (temp != null) | |
temp.parent = parent; | |
} | |
private void SingleRightRotation(Node node, Node parent, Node grandParent) | |
{ | |
Node temp = node.right; | |
//node is parents parent now | |
node.right = parent; | |
parent.left = temp; | |
parent.parent = node; | |
//so node is the new child of gp | |
grandParent.right = node; | |
node.parent = grandParent; | |
if (temp != null) | |
temp.parent = parent; | |
} | |
private void RotateRight(Node parent, Node grandParent) | |
{ | |
Node tempParentRight = parent.right; | |
parent.parent = grandParent.parent; | |
if (grandParent.parent != null && grandParent.parent.right == grandParent) | |
{ | |
grandParent.parent.right = parent; | |
} | |
else if (grandParent.parent != null && grandParent.parent.left == grandParent) | |
{ | |
grandParent.parent.left = parent; | |
} | |
parent.right = grandParent; | |
grandParent.parent = parent; | |
grandParent.left = tempParentRight; | |
if (tempParentRight != null) | |
tempParentRight.parent = grandParent; | |
//swap colors | |
TreeColor tempNodeColor = grandParent.treeColor; | |
grandParent.treeColor = parent.treeColor; | |
parent.treeColor = tempNodeColor; | |
} | |
private void RotateLeft(Node parent, Node grandParent) | |
{ | |
// Console.WriteLine(parent.data); | |
Node tempParentLeft = parent.left; | |
parent.parent = grandParent.parent; | |
if (grandParent.parent != null && grandParent.parent.right == grandParent) | |
{ | |
grandParent.parent.right = parent; | |
} | |
else if (grandParent.parent != null && grandParent.parent.left == grandParent) | |
{ | |
grandParent.parent.left = parent; | |
} | |
parent.left = grandParent; | |
grandParent.parent = parent; | |
grandParent.right = tempParentLeft; | |
if (tempParentLeft != null) | |
tempParentLeft.parent = grandParent; | |
//swap colors | |
TreeColor tempNodeColor = grandParent.treeColor; | |
grandParent.treeColor = parent.treeColor; | |
parent.treeColor = tempNodeColor; | |
} | |
#endregion | |
#region Printing Section | |
public void PrintColors() | |
{ | |
PColors(root); | |
Console.ForegroundColor = ConsoleColor.DarkBlue; | |
Console.WriteLine("---------------------"); | |
} | |
int i = 5; | |
private void PColors(Node node) | |
{ | |
if (node == null) | |
{ | |
return; | |
} | |
PrintToScreen(node); | |
PColors(node.left); | |
PColors(node.right); | |
//Console.WriteLine(node.treeColor.ToString() + " for val:" + node.data); | |
} | |
private void PrintToScreen(Node node) | |
{ | |
if (node.treeColor == TreeColor.Red) | |
Console.ForegroundColor = ConsoleColor.Red; | |
else | |
Console.ForegroundColor = ConsoleColor.Black; Console.WriteLine(new string(' ', i) + node.data); | |
} | |
///Coded by SOFTSAM | |
///ref https://www.geeksforgeeks.org/c-program-red-black-tree-insertion/ ->Images | |
#endregion | |
public bool Find(int data) | |
{ | |
Node n = FindRec(root, data); | |
if (n != null) | |
return true; | |
else | |
return false; | |
} | |
Node FindRec(Node node, int data) | |
{ | |
if (node == null) | |
return null; | |
if (node.data == data) | |
return node; | |
if (data < node.data) | |
return FindRec(node.left, data); | |
else if (data > node.data) | |
return FindRec(node.right, data); | |
return null; | |
} | |
#region Deletion Section | |
bool NodeHasChild(Node node) | |
{ | |
return (node != null && (node.right != null || node.right != null)); | |
} | |
public void Delete(int data) | |
{ | |
Node x, p, s=null; | |
x = p = root; | |
// root.treeColor = TreeColor.Red; | |
//I need tree direction for rotating tree when we need I dont want to check every time x==x.parent.right or something... | |
TreeDirection treeDirection=TreeDirection.None; | |
while (true) | |
{ | |
if (data == x.data) | |
{ | |
//find the max value of left sub tree and change datas and do all recolorings | |
//if you find a node which has no child then check rules and delete | |
if (NodeHasChild(x)) | |
{ | |
TreeDirection tD = TreeDirection.None; | |
Node currentNode=null; | |
//biggest val of left | |
if (x.left != null) | |
{ | |
currentNode = x.left; | |
while (currentNode != null) | |
{ | |
if (currentNode.right != null) | |
currentNode = currentNode.right; | |
else | |
break; | |
} | |
tD = TreeDirection.Left; | |
} | |
//smallest val of right | |
if (x.right != null) | |
{ | |
currentNode = x.right; | |
while (currentNode != null) | |
{ | |
if (currentNode.left != null) | |
currentNode = currentNode.left; | |
else | |
break; | |
} | |
tD = TreeDirection.Right; | |
} | |
int cData = currentNode.data; | |
currentNode.data = x.data; | |
x.data = cData; | |
if(tD == TreeDirection.Right) | |
{ | |
x = x.right; | |
} | |
else if(tD == TreeDirection.Left) | |
{ | |
x = x.left; | |
} | |
//if the leaf node is red then change the val and delete it | |
//it wont change the black height of the tree | |
if (currentNode.treeColor == TreeColor.Red) | |
{ | |
DelFunc(currentNode, tD); | |
break; | |
} | |
//Console.WriteLine(currentNode.data); | |
continue; | |
} | |
else | |
{ | |
DelFunc(x, treeDirection); | |
break; | |
} | |
} | |
if(isRed(x)) | |
{ | |
treeDirection = Move(data, ref x, ref p, ref s); | |
} | |
//this can only happen in the main root | |
else if(x == root && !isRed(x)&&!isRed(x.left)&&!isRed(x.right)) | |
{ | |
Console.WriteLine("root black childs black"); | |
x.treeColor = TreeColor.Red; | |
treeDirection = Move(data,ref x,ref p,ref s); | |
} | |
else if(isRed(x.left) || isRed(x.right)) | |
{ | |
//check if there is a red node under x if there is just move | |
//move to the node which is appropriate | |
treeDirection = Move(data, ref x, ref p, ref s); | |
//check where did you move | |
//if you are in red node keep moving | |
if (isRed(x)) | |
{ | |
treeDirection = Move(data, ref x, ref p, ref s); | |
} | |
//if you are in black node rotate red node around parent | |
else | |
{ | |
//rotate s around p | |
if(treeDirection == TreeDirection.Right) | |
{ | |
//rotate left side | |
SingleLeftRotation(s, p, p.parent); | |
} | |
else if(treeDirection == TreeDirection.Left) | |
{ | |
//rotate right side | |
SingleRightRotation(s, p, p.parent); | |
} | |
//recolor p and s | |
TreeColor temp = s.treeColor; | |
s.treeColor = p.treeColor; | |
p.treeColor = temp; | |
} | |
} | |
//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; | |
} | |
private void DelFunc(Node x, TreeDirection treeDirection) | |
{ | |
if (treeDirection == TreeDirection.Left) | |
{ | |
x.parent.left = null; | |
} | |
else if (treeDirection == TreeDirection.Right) | |
{ | |
x.parent.right = null; | |
} | |
x.parent = null; | |
} | |
private TreeDirection Move(int data,ref Node x,ref Node p,ref Node s) | |
{ | |
if (data < x.data && isRed(x)) | |
{ | |
p = x; | |
s = x.right; | |
x = x.left; | |
return TreeDirection.Left; | |
} | |
if (data > x.data && isRed(x)) | |
{ | |
p = x; | |
s = x.left; | |
x = x.right; | |
return TreeDirection.Right; | |
} | |
return TreeDirection.None; | |
} | |
bool isRed(Node node) | |
{ | |
return node != null && node.treeColor == TreeColor.Red; | |
} | |
///Coded by SOFTSAM | |
///ref RED BLACK TREES FIRAT UNIVERSITY Algorithm Analysis Week 7 Red Black Trees ->Images | |
#endregion | |
} | |
} |
Hiç yorum yok:
Yorum Gönder