Red-black tree definition: it is either an empty tree or a binary search tree with the following properties
1) : Each node is either red or black.
2) : The root node is black.
3) : Each leaf node (NIL) is black. (All NULL nodes are called leaf nodes and are considered black in color)
4) : If a node is red, its two children are black.
5) : For each node, all paths from this node to its descendants contain the same number of black nodes.
Red-black trees are used in associative arrays and dictionaries. The space required is smaller than the hash table. This can be used for any key value correspondence that requires dao random storage and key order.
class TreeNode<T>
{
public T Data { get; set; }
public TreeNode<T> LeftChild { get; set; }
public TreeNode<T> RightChild { get; set; }
public TreeNode<T> Parent { get; set; }
public int Color { get; set; }
public TreeNode(T data)
{
Data = data;
Parent = null;
LeftChild = null;
RightChild = null;
}
public TreeNode(T newData, TreeNode<T> parent)
{
Data = newData;
Parent = parent;
LeftChild = null;
RightChild = null; }}internal class RedBlackTree<T> where T : IComparable<T>, IEquatable<T>, new()
{
public TreeNode<T> Root { get; private set; }
public int Size { get; private set; }
public RedBlackTree()
{
Root = null;
Size = 0;
}
private static TreeNode<T> Add(TreeNode<T> to, TreeNode<T> newNode)
{
if (newNode.Data.CompareTo(to.Data) < 0)
{
if(to.LeftChild ! =null) return Add(to.LeftChild, newNode);
newNode.LeftChild = null;
newNode.RightChild = null;
to.LeftChild = newNode;
newNode.Color = 1;
newNode.Parent = to;
return newNode;
}
if(to.RightChild ! =null) return Add(to.RightChild, newNode);
newNode.LeftChild = null;
newNode.RightChild = null;
to.RightChild = newNode;
newNode.Color = 1;
newNode.Parent = to;
return newNode;
}
private void LeftTurn(TreeNode<T> node)
{
if (node.RightChild == null) return;
var child = node.RightChild;
node.RightChild = child.LeftChild;
if(child.LeftChild ! =null) child.LeftChild.Parent = node;
child.Parent = node.Parent;
if (node.Parent == null) Root = child;
else
{
if (node == node.Parent.LeftChild)
node.Parent.LeftChild = child;
else
node.Parent.RightChild = child;
}
child.LeftChild = node;
node.Parent = child;
}
private void RightTurn(TreeNode<T> node)
{
if (node.LeftChild == null) return;
var child = node.LeftChild;
node.LeftChild = child.RightChild;
if(child.RightChild ! =null) child.RightChild.Parent = node;
child.Parent = node.Parent;
if (node.Parent == null) Root = child;
else
{
if (node == node.Parent.RightChild) node.Parent.RightChild = child;
else node.Parent.LeftChild = child;
}
child.RightChild = node;
node.Parent = child;
}
public void Insert(TreeNode<T> node)
{
if (Root == null)
{
Root = node;
Root.Color = 0;
Root.LeftChild = null;
Root.RightChild = null;
Root.Parent = null;
}
else
{
var addedNode = Add(Root, node);
while(addedNode ! = Root && addedNode.Parent.Color ==1)
{
if (addedNode.Parent == addedNode.Parent.Parent.LeftChild)
{
var y = addedNode.Parent.Parent.RightChild;
if(y ! =null && y.Color == 1)
{
addedNode.Parent.Color = 0;
y.Color = 0;
addedNode.Parent.Parent.Color = 1;
addedNode = addedNode.Parent.Parent;
}
else
{
if (addedNode == addedNode.Parent.RightChild)
{
addedNode = addedNode.Parent;
LeftTurn(addedNode);
}
addedNode.Parent.Color = 0;
addedNode.Parent.Parent.Color = 1; RightTurn(addedNode.Parent.Parent); }}else
{
var y = addedNode.Parent.Parent.LeftChild;
if(y ! =null && y.Color == 1)
{
addedNode.Parent.Color = 0;
y.Color = 0;
addedNode.Parent.Parent.Color = 1;
addedNode = addedNode.Parent.Parent;
}
else
{
if (addedNode == addedNode.Parent.Parent.LeftChild)
{
addedNode = addedNode.Parent;
RightTurn(addedNode);
}
addedNode.Parent.Color = 0;
addedNode.Parent.Parent.Color = 1;
LeftTurn(addedNode.Parent.Parent);
}
}
}
}
Root.Color = 0;
}
private static TreeNode<T> Min(TreeNode<T> node)
{
while(node.LeftChild ! =null) node = node.LeftChild;
return node;
}
private static TreeNode<T> Next(TreeNode<T> node)
{
if(node.RightChild ! =null) return Min(node.RightChild);
var y = node.Parent;
while(y ! =null && node == y.RightChild)
{
node = y;
y = y.Parent;
}
return y;
}
private void FixUp(TreeNode<T> node)
{
while(node ! = Root && node.Color ==0)
{
if (node == node.Parent.LeftChild)
{
var w = node.Parent.RightChild;
if (w.Color == 1)
{
w.Color = 0;
node.Parent.Color = 1;
LeftTurn(node.Parent);
w = node.Parent.RightChild;
}
if (w.LeftChild.Color == 0 && w.RightChild.Color == 0)
{
w.Color = 1;
node = node.Parent;
}
else
{
if (w.RightChild.Color == 0)
{
w.LeftChild.Color = 0;
w.Color = 1;
RightTurn(w);
w = node.Parent.RightChild;
}
w.Color = node.Parent.Color;
node.Parent.Color = 0;
w.RightChild.Color = 0; LeftTurn(node.Parent); node = Root; }}else
{
var w = node.Parent.LeftChild;
if (w.Color == 1)
{
w.Color = 0;
node.Parent.Color = 1;
RightTurn(node.Parent);
w = node.Parent.LeftChild;
}
if (w.RightChild.Color == 0 && w.LeftChild.Color == 0)
{
w.Color = 1;
node = node.Parent;
}
else
{
if (w.LeftChild.Color == 0)
{
w.RightChild.Color = 0;
w.Color = 1;
LeftTurn(w);
w = node.Parent.LeftChild;
}
w.Color = node.Parent.Color;
node.Parent.Color = 0;
w.LeftChild.Color = 0;
RightTurn(node.Parent);
node = Root;
}
}
}
node.Color = 0;
}
public void Delete(TreeNode<T> node)
{
TreeNode<T> y;
if (node.LeftChild == null || node.RightChild == null)
y = node;
else
y = Next(node);
var x = y.LeftChild ?? y.RightChild;
if (x == null)
{
node.Data = y.Data;
if (y.Parent == null) return;
if (y.Parent.LeftChild == y) y.Parent.LeftChild = null;
else y.Parent.RightChild = null;
return;
}
x.Parent = y.Parent;
if (y.Parent == null) Root = x;
else
{
if (y == y.Parent.LeftChild) y.Parent.LeftChild = x;
else y.Parent.RightChild = x;
}
if(y ! = node) { node.Data = y.Data; }if (y.Color == 0) FixUp(x);
}
private static TreeNode<T> SearchInSubTree(TreeNode<T> topNode, T data)
{
if (data.Equals(topNode.Data))
return topNode;
if (data.CompareTo(topNode.Data) < 0&& topNode.LeftChild ! =null)
return SearchInSubTree(topNode.LeftChild, data);
if (data.CompareTo(topNode.Data) > 0&& topNode.RightChild ! =null)
return SearchInSubTree(topNode.RightChild, data);
return null;
}
public bool Search(T data)
{
returnSearchInSubTree(Root, data) ! =null;
}
public TreeNode<T> SearchNode(T data)
{
return SearchInSubTree(Root, data);
}
public IEnumerator<T> GetEnumerator()
{
if (Root == null)
yield break;
var current = Min(Root);
yield return current.Data;
while(Next(current) ! =null)
{
current = Next(current);
yield returncurrent.Data; }}public IEnumerator<TreeNode<T>> DfsEnum()
{
var verts = new Stack<TreeNode<T>>();
if (Root == null)
yield break;
verts.Push(Root);
var previous = 0;
while(verts.Count ! =0)
{
var current = verts.Peek();
if (current.LeftChild == null && current.RightChild == null)
{
verts.Pop();
yield return current;
if(current.Parent ! =null)
previous = current == current.Parent.LeftChild ? 1 : 2;
else
yield break;
continue;
}
switch (previous)
{
case 0:
if (current.LeftChild == null)
{
previous = 1;
continue;
}
verts.Push(current.LeftChild);
previous = 0;
break;
case 1:
if (current.RightChild == null)
{
verts.Pop();
yield return current;
if(current.Parent ! =null)
{
previous = current == current.Parent.LeftChild ? 1 : 2;
continue;
}
yield break;
}
verts.Push(current.RightChild);
previous = 0;
break;
case 2:
verts.Pop();
yield return current;
if(current.Parent ! =null)
previous = current == current.Parent.LeftChild ? 1 : 2;
else
yield break;
break; }}}public IEnumerator<TreeNode<T>> BfsEnum()
{
var verts = new Queue<TreeNode<T>>();
verts.Enqueue(Root);
while(verts.Count ! =0)
{
var current = verts.Dequeue();
yield return current;
if(current.LeftChild ! =null)
verts.Enqueue(current.LeftChild);
if(current.RightChild ! =null) verts.Enqueue(current.RightChild); }}}Copy the code