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