红黑树定义：它或者是一颗空树，或者是具有一下性质的二叉查找树
1）：每个节点或是红的，或是黑的。
2）：根节点是黑的。
3）：每个叶节点（NIL）是黑的。（所有NULL结点称为叶子节点，且认为颜色为黑）
4）：如果一个节点是红的，则他的两个子节点是黑的。
5）：对每个节点，从该节点到其子孙节点的所有路径上包含相同数目的黑节点。
红黑树用在关联数组、字典的实现上。需du要的空间zhi比散列表小。 任何键值对应,需要dao随机存储和键有序的情况都可以用。
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) { return SearchInSubTree(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 return current.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); } } }
