Class RedBlackTree<T>

Red-black tree.

Inheritance

System.Object

BinaryTree<RedBlackTreeNode<T>>

RedBlackTree<T>

RedBlackTree<TKey, TValue>

Implements

ICollection<RedBlackTreeNode<T>>

ICollection<T>

Inherited Members

BinaryTree<RedBlackTreeNode<T>>.Root

BinaryTree<RedBlackTreeNode<T>>.Traverse(BinaryTraversalMethod<RedBlackTreeNode<T>>)

Namespace: ISynergy.Framework.Core.Collections

Assembly: ISynergy.Framework.Core.dll

Syntax

public class RedBlackTree<T> : BinaryTree<RedBlackTreeNode<T>>

Type Parameters

Name	Description
T	The type of the value to be stored.

Remarks

A red–black tree is a data structure which is a type of self-balancing 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:

• Steven G. Johnson, The NLopt nonlinear-optimization package, http://ab-initio.mit.edu/nlopt
• Wikipedia, The Free Encyclopedia. Red-black tree. Available on: http://en.wikipedia.org/wiki/Red%E2%80%93black_tree

Constructors

RedBlackTree()

Constructs a new RedBlackTree<T> using the default for type T.

Declaration

public RedBlackTree()

RedBlackTree(IComparer<T>)

Constructs a new RedBlackTree<T> using the provided implementation.

Declaration

public RedBlackTree(IComparer<T> comparer)

Parameters

Type	Name	Description
IComparer<T>	comparer	The element comparer to be used to order elements in the tree.

RedBlackTree(IComparer<T>, Boolean)

Constructs a new RedBlackTree<T> using the provided implementation.

Declaration

public RedBlackTree(IComparer<T> comparer, bool allowDuplicates)

Parameters

Type	Name	Description
IComparer<T>	comparer	The element comparer to be used to order elements in the tree.
System.Boolean	allowDuplicates	Pass true to allow duplicate elements in the tree; false otherwise.

RedBlackTree(Boolean)

Constructs a new RedBlackTree<T> using the default for type T.

Declaration

public RedBlackTree(bool allowDuplicates)

Parameters

Type	Name	Description
System.Boolean	allowDuplicates	Pass true to allow duplicate elements in the tree; false otherwise.

Properties

Comparer

Gets the for this red black tree.

Declaration

public IComparer<T> Comparer { get; }

Property Value

Type	Description
IComparer<T>

Count

Gets the number of nodes contained in this red-black tree.

Declaration

public int Count { get; }

Property Value

Type	Description
System.Int32

IsReadOnly

Gets a value indicating whether this instance is read only. In a RedBlackTree<T>, this returns false.

Declaration

public bool IsReadOnly { get; }

Property Value

Type	Description
System.Boolean	Returns false.

Methods

Add(T)

Adds a new item to the tree. If the element already belongs to this tree, no new element will be added.

Declaration

public RedBlackTreeNode<T> Add(T item)

Parameters

Type	Name	Description
T	item	The item to be added.

Returns

Type	Description
RedBlackTreeNode<T>	The node containing the added item.

Add(RedBlackTreeNode<T>)

Adds a new item to the tree. If the element already belongs to this tree, no new element will be added.

Declaration

public void Add(RedBlackTreeNode<T> item)

Parameters

Type	Name	Description
RedBlackTreeNode<T>	item	The node to be added to the tree.

Clear()

Removes all nodes from the tree.

Declaration

public void Clear()

Contains(T)

Determines whether this tree contains the specified item.

Declaration

public bool Contains(T item)

Parameters

Type	Name	Description
T	item	The item to be looked for.

Returns

Type	Description
System.Boolean	true if the element was found inside the tree; otherwise, false.

Contains(RedBlackTreeNode<T>)

Determines whether this tree contains the specified item.

Declaration

public bool Contains(RedBlackTreeNode<T> item)

Parameters

Type	Name	Description
RedBlackTreeNode<T>	item	The item to be looked for.

Returns

Type	Description
System.Boolean	true if the element was found inside the tree; otherwise, false.

CopyTo(T[], Int32)

Copies the elements of this tree to an array, starting at a particular arrayIndex.

Declaration

public void CopyTo(T[] array, int arrayIndex)

Parameters

Type	Name	Description
T[]	array	The one-dimensional array that is the destination of the elements copied from this tree. The array must have zero-based indexing.
System.Int32	arrayIndex	The zero-based index in array at which copying begins.

CopyTo(RedBlackTreeNode<T>[], Int32)

Copies the nodes of this tree to an array, starting at a particular arrayIndex.

Declaration

public void CopyTo(RedBlackTreeNode<T>[] array, int arrayIndex)

Parameters

Type	Name	Description
RedBlackTreeNode<T>[]	array	The one-dimensional array that is the destination of the elements copied from this tree. The array must have zero-based indexing.
System.Int32	arrayIndex	The zero-based index in array at which copying begins.

Find(T)

Attempts to find a node that contains the specified key.

Declaration

public RedBlackTreeNode<T> Find(T item)

Parameters

Type	Name	Description
T	item	The key whose node is to be found.

Returns

Type	Description
RedBlackTreeNode<T>	A RedBlackTreeNode<T> containing the desired item if it is present in the dictionary; otherwise, returns null.

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.

Declaration

public RedBlackTreeNode<T> FindGreaterThan(T value)

Parameters

Type	Name	Description
T	value	A reference value to be found.

Returns

Type	Description
RedBlackTreeNode<T>	The node containing an element that is immediately below value.

FindGreaterThan(RedBlackTreeNode<T>, 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.

Declaration

public RedBlackTreeNode<T> FindGreaterThan(RedBlackTreeNode<T> node, T value)

Parameters

Type	Name	Description
RedBlackTreeNode<T>	node	The subtree where search will take place.
T	value	A reference value to be found.

Returns

Type	Description
RedBlackTreeNode<T>	The node containing an element that is immediately below value.

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.

Declaration

public RedBlackTreeNode<T> FindLessThan(T value)

Parameters

Type	Name	Description
T	value	A reference value to be found.

Returns

Type	Description
RedBlackTreeNode<T>	The node containing an element that is immediately below value.

FindLessThan(RedBlackTreeNode<T>, 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.

Declaration

public RedBlackTreeNode<T> FindLessThan(RedBlackTreeNode<T> node, T value)

Parameters

Type	Name	Description
RedBlackTreeNode<T>	node	The subtree where search will take place.
T	value	A reference value to be found.

Returns

Type	Description
RedBlackTreeNode<T>	The node containing an element that is immediately below value.

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.

Declaration

public RedBlackTreeNode<T> FindLessThanOrEqualTo(T value)

Parameters

Type	Name	Description
T	value	A reference for the value to be found.

Returns

Type	Description
RedBlackTreeNode<T>	The node containing the given value value or its immediately smaller neighboring number present in the tree.

FindLessThanOrEqualTo(RedBlackTreeNode<T>, 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.

Declaration

public RedBlackTreeNode<T> FindLessThanOrEqualTo(RedBlackTreeNode<T> node, T value)

Parameters

Type	Name	Description
RedBlackTreeNode<T>	node	The subtree where search will take place.
T	value	A reference value to be found.

Returns

Type	Description
RedBlackTreeNode<T>	The node containing the given value value or its immediately smaller neighboring number present in the tree.

GetEnumerator()

Returns an enumerator that iterates through this tree in-order.

Declaration

public override IEnumerator<RedBlackTreeNode<T>> GetEnumerator()

Returns

Type	Description
IEnumerator<RedBlackTreeNode<T>>	An System.Collections.IEnumerator object that can be used to traverse through this tree using in-order traversal.

Overrides

ISynergy.Framework.Core.Collections.BinaryTree<ISynergy.Framework.Core.Collections.RedBlackTreeNode<T>>.GetEnumerator()

GetNextNode(RedBlackTreeNode<T>)

Gets the node that contains the next in-order value coming after the value contained in the given node.

Declaration

public RedBlackTreeNode<T> GetNextNode(RedBlackTreeNode<T> node)

Parameters

Type	Name	Description
RedBlackTreeNode<T>	node	The current node.

Returns

Type	Description
RedBlackTreeNode<T>	The node that contains a value that is immediately greater than the current value contained in the given node.

GetPreviousNode(RedBlackTreeNode<T>)

Gets the node that contains the previous in-order value coming before the value contained in the given node.

Declaration

public RedBlackTreeNode<T> GetPreviousNode(RedBlackTreeNode<T> node)

Parameters

Type	Name	Description
RedBlackTreeNode<T>	node	The current node.

Returns

Type	Description
RedBlackTreeNode<T>	The node that contains a value that is immediately less than the current value contained in the given node.

Max()

Finds the maximum element stored in the tree.

Declaration

public RedBlackTreeNode<T> Max()

Returns

Type	Description
RedBlackTreeNode<T>	The RedBlackTreeNode<T> that holds the maximum element in the tree.

Min()

Finds the minimum element stored in the tree.

Declaration

public RedBlackTreeNode<T> Min()

Returns

Type	Description
RedBlackTreeNode<T>	The RedBlackTreeNode<T> that holds the minimum element in the tree.

Remove(T)

Removes a node from the tree.

Declaration

public RedBlackTreeNode<T> Remove(T item)

Parameters

Type	Name	Description
T	item	The key of the node to be removed.

Returns

Type	Description
RedBlackTreeNode<T>	A reference to the removed node, if the item was in the tree; otherwise, null.

Remove(RedBlackTreeNode<T>)

Removes a node from the tree.

Declaration

public RedBlackTreeNode<T> Remove(RedBlackTreeNode<T> node)

Parameters

Type	Name	Description
RedBlackTreeNode<T>	node	The node to be removed.

Returns

Type	Description
RedBlackTreeNode<T>	A reference to the removed node.

Resort(RedBlackTreeNode<T>)

Forces a re-balance of the tree by removing and inserting the same node.

Declaration

public RedBlackTreeNode<T> Resort(RedBlackTreeNode<T> node)

Parameters

Type	Name	Description
RedBlackTreeNode<T>	node	The node to be re-balanced.

Returns

Type	Description
RedBlackTreeNode<T>	The same node, or a new one if it had to be recreated.

Implements

ICollection<>

ICollection<>

Extension Methods

Matrix.Replace<T>(T, Object, Object)

Matrix.IsEqual(Object, Object, Decimal, Decimal)

EntityBaseExtensions.HasProperty(Object, String)

ArrayExtensions.Concatenate<T>(T, T[])

CollectionExtensions.FromHierarchy<TSource>(TSource, Func<TSource, TSource>, Func<TSource, Boolean>)

CollectionExtensions.FromHierarchy<TSource>(TSource, Func<TSource, TSource>)

ObjectExtensions.Clone<T>(T)

ObjectExtensions.To<T>(Object)

ObjectExtensions.To(Object, Type)

ObjectExtensions.HasMethod(Object, String)

ObjectExtensions.AddressOf<T>(T)

ReflectionExtensions.GetIdentityValue<T>(T)

ReflectionExtensions.GetIdentityValue<T, TResult>(T)

ReflectionExtensions.GetIdentityProperty<T>(T)

ReflectionExtensions.HasIdentityProperty<T>(T)

ReflectionExtensions.GetPropertyValue<T, TResult>(T, String, TResult)

ReflectionExtensions.GetPropertyInfo<T, TValue>(T, Expression<Func<T, TValue>>)

ReflectionExtensions.GetTitleValue<T>(T)

ReflectionExtensions.HasParentIdentityProperty<T>(T)

ReflectionExtensions.GetParentIdentityProperty<T>(T)

ReflectionExtensions.IsFreeApplication<T>(T)