/*
* Red Black Tree for CSC 3102 Portfolio
*/
/*
* --REQUIRED METHODS-- (Restructuring)
* TreeNode Restructure(TreeNode x)
* void Rotate(TreeNode x)
*
* --REQUIRED METHODS-- (Red-Black Tree)
* void Add(int val)
* int CheckColor(int val)
* int BDepth(int val)
*
* void Remove(int val)
*/
namespace RedBlackTree
{
class TreeNode
{
public int data;
public char color;
public TreeNode? p, rChild, lChild;
public TreeNode()
{
data = 0;
color = default;
p = null;
rChild = null;
lChild = null;
}
public TreeNode(int data)
{
this.data = data;
color = 'R';
p = null;
rChild = null;
lChild = null;
}
}
class RedBlackTree
{
public TreeNode? root;
/*
* Basic constructor for the Red-Black Tree
*/
public RedBlackTree()
{
root = null;
}
public void Add(int val)
{
var node = new TreeNode(val);
if (root == null)
{
root = node;
}
else
{
var trav = root;
while (true)
{
if (val <= trav.data) //move to the left
{
if (trav.lChild == null)
{
trav.lChild = node;
node.p = trav;
break;
}
else
{
trav = trav.lChild;
}
}
else //move to the right
{
if (trav.rChild == null)
{
trav.rChild = node;
node.p = trav;
break;
}
else
{
trav = trav.rChild;
}
}
} // end of while loop
}
Restructure(node);
}
/*
* removes the node that has the specified value
* Uses ReplacementNode(int value) to remove the value from the tree
* @value - the data of the node that is being removed
*/
public int? Remove(int value)
{
if (root == null)
{
return null;
}
TreeNode v = root;
while (v.data != value) //find the node that value is at
{
if (value < v.data)
{
if (v.lChild == null)
{
return null;
}
else
{
v = v.lChild;
}
}
else //(value > v.data)
{
if (v.rChild == null)
{
return null;
}
else
{
v = v.rChild;
}
}
} //end of while loop
TreeNode u = Replace(v);
bool doubleBlack = ((u == null || u.color == 'B') && (v.color == 'B'));
TreeNode tempP = v.p;
if (u == null)
{
if (v == root)
{
root = null;
}
else
{
if (doubleBlack)
{
DoubleBlack(v);
}
else
{
if (v.p.lChild == v && v.p.rChild != null)
{
v.p.rChild.color = 'R';
}
else if (v.p.rChild == v && v.p.lChild != null)
{
v.p.lChild.color = 'R';
}
}
if (v.p.lChild == v)
{
v.p.lChild = null;
}
else
{
v.p.rChild = null;
}
}
return value;
}
if (v.lChild == null || v.rChild == null)
{
if (v == root)
{
root = u;
u.p = v.p; ;
u.rChild = v.rChild;
u.lChild = v.lChild;
v.p = v.rChild = v.lChild = null;
Remove(u.data);
}
else
{
if (v.p.lChild == v)
{
v.p.lChild = u;
}
else
{
v.p.rChild = u;
}
u.p = v.p;
if (doubleBlack)
{
DoubleBlack(u);
}
else
{
u.color = 'B';
}
}
return value;
}
//2 children
u.p = v.p;
u.lChild = v.lChild;
u.rChild = v.rChild;
v.p = v.lChild = v.rChild = null;
Remove(u.data);
return value;
}
/*
* Fixes Double Black Condition
*/
void DoubleBlack(TreeNode x)
{
if (x == root)
{
x.color = 'B';
return;
}
TreeNode? s; //sibling
if ( x.p.lChild == x) //x is parent's left child, so s is parent's right child
{
s = x.p.rChild;
}
else //(x.p.rChild == x), x is parent's right child, so s is parent's left child
{
s = x.p.lChild;
}
if (s == null)
{
DoubleBlack(x.p);
}
else
{
if (s.color == 'R')
{
x.p.color = 'R';
s.color = 'B';
if (x.p.lChild == x) //sibling is on the right
{
if (s.rChild == null)
{
var temp = new TreeNode();
s.rChild = temp;
}
Rotate(s.rChild);
s.rChild = null;
}
else //x.p.rChild == x, sibling is on the left
{
if (s.lChild == null)
{
var temp = new TreeNode();
s.lChild = temp;
}
Rotate(s.lChild);
s.lChild = null;
}
DoubleBlack(x);
}
else //s.color == 'B'
{
if (s.rChild != null && s.rChild.color == 'R' || s.lChild != null && s.lChild.color == 'R')
{
if (s.lChild != null && s.lChild.color == 'R')
{
if (x.p.rChild == x) //sibling is on left
{
s.lChild.color = s.color;
s.color = x.p.color;
Rotate(s.lChild);
}
else //sibling is on right
{
s.lChild.color = s.color;
DoubleRotate(s.lChild);
}
}
else
{
if (x.p.rChild == x) //sibling is on left
{
s.rChild.color = s.color;
DoubleRotate(s.rChild);
}
else //sibling is on right
{
s.rChild.color = s.color;
s.color = s.p.color;
Rotate(s.rChild);
}
}
x.p.color = 'B';
}
else //both children are black
{
s.color = 'R';
if (x.p.color == 'B')
{
DoubleBlack(x.p);
}
else
{
x.p.color = 'B';
}
}
}
}
}
/*
* Returns the right first, then left most node as the succcessor
*/
TreeNode Successor(TreeNode x)
{
TreeNode node = x;
node = node.rChild;
while (node.lChild != null)
{
node = node.lChild;
}
return node;
}
TreeNode? Replace(TreeNode x)
{
if (x.rChild != null && x.lChild != null)
{
return Successor(x);
}
else if(x.rChild == null && x.lChild == null)
{
return null;
}
else if (x.rChild == null && x.lChild != null)
{
return x.lChild;
}
else // (x.lChild == null && x.rChild != null)
{
return x.rChild;
}
}
/*
* Checks the color of the node with the specified value
* Returns -1 if value DNE, 0 if red, 1 if black, 2 if double black
*/
int CheckColor(int val)
{
var node = root;
while (node != null)
{
if (node.data == val)
{
if (node.color == 'B')
{
return 1;
}
else if (node.color == 'R')
{
return 0;
}
else //(node.color == 'D')
{
return 2;
}
}
else if (val < node.data)
{
node = node.lChild;
}
else //(val > node.data)
{
node = node.rChild;
}
} //end of while loop
return -1;
}
/*
* Searches for specified value in tree, and returns number of black nodes
*/
int BDepth(int val)
{
if (!Has(val))
{
return -1;
}
return Bdepth(root, val);
}
/*
* Helper function that uses recursion to find the number of black nodes that are ancestors to the specified value
*/
int Bdepth(TreeNode node, int val)
{
if (val < node.data)
{
if (node.color == 'B')
{
return 1 + Bdepth(node.lChild, val);
}
else
{
return Bdepth(node.lChild, val);
}
}
else if (val > node.data)
{
if (node.color == 'B')
{
return 1 + Bdepth(node.rChild, val);
}
else
{
return Bdepth(node.rChild, val);
}
}
else
{
if (node.color == 'B')
{
return 1;
}
else
{
return 0;
}
}
}
/*
* Checks the tree to see if it has the value
*/
bool Has(int val)
{
var node = root;
while (node != null)
{
if (val == node.data)
{
return true;
}
else if (val < node.data)
{
node = node.lChild;
}
else //(val > node.data)
{
node = node.rChild;
}
}
return false;
}
/*
* Notices the node that broke a condition, and corrects it
*/
TreeNode Restructure(TreeNode x)
{
if (root.color == 'R') //the root is red
{
root.color = 'B';
}
while (x != root && x != null && x.color == 'R' && x.p.color == 'R')
{
if (x.p.p != null && x.p == x.p.p.lChild)
{
var unc = x.p.p.rChild; //x's uncle
if (unc != null && unc.color == 'R')
{
unc.color = 'B'; //change uncles color
x.p.color = 'B'; //change parent's color
x.p.p.color = 'R'; //change grandparent's color
x = x.p;
}
else
{
if (x == x.p.lChild) //line condition
{
Rotate(x);
x.p.color = 'R';
x.color = 'B';
if (x.p.rChild != null)
{
x.p.rChild.color = 'B';
}
x = x.p;
}
else //zigzag condition
{
DoubleRotate(x);
x.color = 'R';
if (x.rChild != null)
{
x.rChild.color = 'B';
}
if (x.lChild != null)
{
x.lChild.color = 'B';
}
}
}
}
else if (x.p.p != null && x.p == x.p.p.rChild)
{
var unc = x.p.p.lChild;
if (unc != null && unc.color == 'R')
{
unc.color = 'B';
x.p.color = 'B';
x.p.p.color = 'R';
x = x.p;
}
else
{
if (x.p.rChild == x) //line condition
{
Rotate(x);
x.p.color = 'R';
x.color = 'B';
if (x.p.lChild != null)
{
x.p.lChild.color = 'B';
}
x = x.p;
}
else
{
DoubleRotate(x);
x.color = 'R';
if (x.rChild != null)
{
x.rChild.color = 'B';
}
if (x.lChild != null)
{
x.lChild.color = 'B';
}
}
}
}
}
root.color = 'B';
return x;
}
/*
* Rotates a node when it breaks a condition
* @x - the node that is at the bottom of the rotation
*/
public void Rotate(TreeNode x)
{
if (x.p.lChild == x) //rotate towards the right
{
if (x.p.p == root)
{
var y = x.p;
var z = root;
var newLChild = y.rChild;
root = y; //establish y's parent-child connections, and make it the new root
y.p = null;
y.rChild = z; //establish z's connections
z.p = y;
z.lChild = newLChild; //y's old right child is now z's new left child
if (newLChild != null)
{
newLChild.p = z;
}
}
else
{
var y = x.p;
var z = y.p;
var newLChild = y.rChild;
if (z.p.lChild == z)
{
y.p = z.p; //establish y's parent-child connections
z.p.lChild = y;
}
else //(z.p.rChild == z)
{
y.p = z.p; //establish y's parent-child connections
z.p.rChild = y;
}
z.p = y; //establish z's parent-child connections
y.rChild = z;
z.lChild = newLChild; //establish y's old right child as z's new left child
if (newLChild != null)
{
newLChild.p = z;
}
}
}
else //(x.p.rChild == x), rotate towards the left
{
if (x.p.p == root)
{
var y = x.p;
var z = root;
var newRChild = y.lChild;
root = y; //make y the root and give it root properties
y.p = null;
z.p = y; //establish z's connections
y.lChild = z;
z.rChild = newRChild; //make y's old left child z's new rigtht child
if (newRChild != null)
{
newRChild.p = z;
}
}
else
{
var y = x.p;
var z = y.p;
var newRChild = y.lChild;
if (z.p.rChild == z)
{
y.p = z.p; //establish y's connections
z.p.rChild = y;
}
else //(z.p.lChild == z)
{
y.p = z.p; //establish y's connections
z.p.lChild = y;
}
z.p = y; //establish z's connections
y.lChild = z;
z.rChild = newRChild; //y's old left child is z's new right child
if (newRChild != null)
{
newRChild.p = z;
}
}
}
}
/*
* Rotates around x, when the three nodes out of balance are in a zigzag
*/
public void DoubleRotate(TreeNode x)
{
if (x.p.lChild == x) //Right-Left rotation
{
if (x.p.p == root)
{
var y = x.p;
var z = root;
var xRChild = x.rChild;
var xLChild = x.lChild;
root = x;
x.p = null;
x.lChild = z;
z.p = x;
x.rChild = y;
y.p = x;
z.rChild = xLChild;
if (xLChild != null)
{
xLChild.p = z;
}
y.lChild = xRChild;
if (xRChild != null)
{
xRChild.p = y;
}
x.color = 'B';
y.color = 'R';
z.color = 'R';
}
else
{
var y = x.p;
var z = y.p;
var xLChild = x.lChild;
var xRChild = x.rChild;
if (z.p.lChild == z) //establish x's connections
{
z.p.lChild = x;
x.p = z.p;
}
else //(z.p.rChild == z)
{
z.p.rChild = x;
x.p = z.p;
}
x.lChild = z; //establish z's connection
z.p = x;
x.rChild = y; //establish y's connections
y.p = x;
z.rChild = xLChild;
if (xLChild != null)
{
xLChild.p = z;
}
y.lChild = xRChild;
if (xRChild != null)
{
xRChild.p = y;
}
x.color = 'B';
y.color = 'R';
z.color = 'R';
}
}
else //(x.p.rChild == x), Left-Right rotation
{
if (x.p.p == root)
{
var y = x.p;
var z = y.p;
var xLChild = x.lChild;
var xRChild = x.rChild;
root = x; //x is the new root, and give it root properties
x.p = null;
x.lChild = y;
y.p = x;
x.rChild = z;
z.p = x;
y.rChild = xLChild;
if (xLChild != null)
{
xLChild.p = y;
}
z.lChild = xRChild;
if (xRChild != null)
{
xRChild.p = z;
}
x.color = 'B';
y.color = 'R';
z.color = 'R';
}
else
{
var y = x.p;
var z = y.p;
var xLChild = x.lChild;
var xRChild = x.rChild;
if (z.p.lChild == z) //establish x's connections
{
x.p = z.p;
z.p.lChild = x;
}
else //(z.p.rChild == z)
{
x.p = z.p;
z.p.rChild = x;
}
y.p = x; //establish y's connections
x.lChild = y;
z.p = x; //establish z's connections
x.rChild = z;
y.rChild = xLChild; //establish old left child's connections
if (xLChild != null)
{
xLChild.p = y;
}
z.lChild = xRChild; //establish old right child's connections
if (xRChild != null)
{
xRChild.p = z;
}
x.color = 'B';
y.color = 'R';
z.color = 'R';
}
}
}
/*
* Calulates the black node height difference
*/
int BNodeDiff(TreeNode node)
{
return BNodeHeight(node.lChild) - BNodeHeight(node.rChild);
}
/*
* Does the calculation for the BNodeDiff(TreeNode node) function
*/
int BNodeHeight(TreeNode node)
{
if (node == null)
{
return 1;
}
else if (node.color == 'B')
{
return 1 + Math.Max(BNodeHeight(node.lChild), BNodeHeight(node.rChild));
}
else
{
return Math.Max(BNodeHeight(node.lChild), BNodeHeight(node.rChild));
}
}
public void PrintTree()
{
if (root == null)
{
Console.WriteLine("tree is null");
}
else
{
Console.Write("[ ");
Print(root);
Console.WriteLine("]");
}
}
/*
* This function traverses the binary search tree, using In Order Traversal
* Used in the PrintTree() function
*/
private void Print(TreeNode node)
{
if (node.lChild != null)
{
Print(node.lChild);
}
Console.Write(node.data + "(" + node.color + ") ");
if (node.rChild != null)
{
Print(node.rChild);
}
}
}
}