Red Black Trees Bottom-Up Insertion & Top-Down Deletion - SOFTSAM

About Software

30.03.2018

Red Black Trees Bottom-Up Insertion & Top-Down Deletion




 
///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
}
}
view raw RedBlackTree.cs hosted with ❤ by GitHub

Hiç yorum yok:

Yorum Gönder