RedBlackTreeT Class 
Namespace: Accord.Collections
[SerializableAttribute] public class RedBlackTree<T> : BinaryTree<RedBlackTreeNode<T>>, IEnumerable
The RedBlackTreeT type exposes the following members.
Name  Description  

RedBlackTreeT 
Constructs a new RedBlackTreeT using the
default IComparerT for type T.
 
RedBlackTreeT(Boolean) 
Constructs a new RedBlackTreeT using the
default IComparerT for type T.
 
RedBlackTreeT(IComparerT) 
Constructs a new RedBlackTreeT using
the provided IComparerT implementation.
 
RedBlackTreeT(IComparerT, Boolean) 
Constructs a new RedBlackTreeT using
the provided IComparerT implementation.

Name  Description  

Comparer 
Gets the IComparerT for this red black tree.
 
Count 
Gets the number of nodes contained in this redblack tree.
 
IsReadOnly 
Gets a value indicating whether this instance is read only.
In a RedBlackTreeT, this returns false.
 
Root 
Gets the root node of this tree.
(Inherited from BinaryTreeTNode.) 
Name  Description  

Add(T) 
Adds a new item to the tree. If the element already
belongs to this tree, no new element will be added.
 
Add(RedBlackTreeNodeT) 
Adds a new item to the tree. If the element already
belongs to this tree, no new element will be added.
 
Clear 
Removes all nodes from the tree.
 
Contains(T) 
Determines whether this tree contains the specified item.
 
Contains(RedBlackTreeNodeT) 
Determines whether this tree contains the specified item.
 
CopyTo(T, Int32) 
Copies the elements of this tree to an array, starting at a
particular arrayIndex.
 
CopyTo(RedBlackTreeNodeT, Int32) 
Copies the nodes of this tree to an array, starting at a
particular arrayIndex.
 
Equals  Determines whether the specified object is equal to the current object. (Inherited from Object.)  
Finalize  Allows an object to try to free resources and perform other cleanup operations before it is reclaimed by garbage collection. (Inherited from Object.)  
Find 
Attempts to find a node that contains the specified key.
 
FindGreaterThan(T) 
Finds the smallest point in the in the
tree that is greater than (>) k. In other words, finds a
number stored in the tree that is immediately above k.
 
FindGreaterThan(RedBlackTreeNodeT, T) 
Finds the smallest point in the subtree rooted at node
that is greater than (>) k. In other words, finds a number stored in
the tree that is immediately above k.
 
FindLessThan(T) 
Finds the greatest point in the
tree that is less than (<) k. In other words, finds
a number stored in the tree that is immediately below k.
 
FindLessThan(RedBlackTreeNodeT, T) 
Finds the greatest point in the subtree rooted at node
that is less than (<) k. In other words, finds a number stored in
the tree that is immediately below k.
 
FindLessThanOrEqualTo(T) 
Finds the greatest point in the
tree that is less than or equal to (<=) k.
In other words, finds either k or a number immediately
below it.
 
FindLessThanOrEqualTo(RedBlackTreeNodeT, T) 
Finds the greatest point in the subtree rooted at node
that is less than or equal to (<=) k. In other words, finds either
k or a number immediately below it.
 
GetEnumerator 
Returns an enumerator that iterates through this tree inorder.
(Overrides BinaryTreeTNodeGetEnumerator.)  
GetHashCode  Serves as the default hash function. (Inherited from Object.)  
GetNextNode 
Gets the node that contains the next inorder value coming
after the value contained in the given node.
 
GetPreviousNode 
Gets the node that contains the previous inorder value coming
before the value contained in the given node.
 
GetType  Gets the Type of the current instance. (Inherited from Object.)  
Max 
Finds the maximum element stored in the tree.
 
MemberwiseClone  Creates a shallow copy of the current Object. (Inherited from Object.)  
Min 
Finds the minimum element stored in the tree.
 
Remove(T) 
Removes a node from the tree.
 
Remove(RedBlackTreeNodeT) 
Removes a node from the tree.
 
Resort 
Forces a rebalance of the tree by removing and inserting the same node.
 
ToString  Returns a string that represents the current object. (Inherited from Object.)  
Traverse 
Traverse the tree using a tree traversal
method. Can be iterated with a foreach loop.
(Inherited from BinaryTreeTNode.) 
Name  Description  

HasMethod 
Checks whether an object implements a method with the given name.
(Defined by ExtensionMethods.)  
IsEqual 
Compares two objects for equality, performing an elementwise
comparison if the elements are vectors or matrices.
(Defined by Matrix.)  
SetEqualsT(IEnumerableT)  Overloaded.
Compares two enumerables for set equality. Two
enumerables are set equal if they contain the
same elements, but not necessarily in the same
order.
(Defined by Matrix.)  
SetEqualsRedBlackTreeNodeT(IEnumerableRedBlackTreeNodeT)  Overloaded. (Defined by Matrix.)  
To(Type)  Overloaded.
Converts an object into another type, irrespective of whether
the conversion can be done at compile time or not. This can be
used to convert generic types to numeric types during runtime.
(Defined by ExtensionMethods.)  
ToT  Overloaded.
Converts an object into another type, irrespective of whether
the conversion can be done at compile time or not. This can be
used to convert generic types to numeric types during runtime.
(Defined by ExtensionMethods.) 
A red–black tree is a data structure which is a type of selfbalancing binary search tree. Balance is preserved by painting each node of the tree with one of two colors (typically called 'red' and 'black') in a way that satisfies certain properties, which collectively constrain how unbalanced the tree can become in the worst case. When the tree is modified, the new tree is subsequently rearranged and repainted to restore the coloring properties. The properties are designed in such a way that this rearranging and recoloring can be performed efficiently.
The balancing of the tree is not perfect but it is good enough to allow it to guarantee searching in O(log n) time, where n is the total number of elements in the tree. The insertion and deletion operations, along with the tree rearrangement and recoloring, are also performed in O(log n) time.
Tracking the color of each node requires only 1 bit of information per node because there are only two colors. The tree does not contain any other data specific to its being a red–black tree so its memory footprint is almost identical to a classic (uncolored) binary search tree.
References: