Click or drag to resize
Accord.NET (logo)

RedBlackTreeT Class

Red-black tree.
Inheritance Hierarchy
SystemObject
  Accord.CollectionsBinaryTreeRedBlackTreeNodeT
    Accord.CollectionsRedBlackTreeT
      Accord.CollectionsRedBlackTreeTKey, TValue

Namespace:  Accord.Collections
Assembly:  Accord (in Accord.dll) Version: 3.8.0
Syntax
[SerializableAttribute]
public class RedBlackTree<T> : BinaryTree<RedBlackTreeNode<T>>, 
	IEnumerable
Request Example View Source

Type Parameters

T
The type of the value to be stored.

The RedBlackTreeT type exposes the following members.

Constructors
  NameDescription
Public methodRedBlackTreeT
Constructs a new RedBlackTreeT using the default IComparerT for type T.
Public methodRedBlackTreeT(Boolean)
Constructs a new RedBlackTreeT using the default IComparerT for type T.
Public methodRedBlackTreeT(IComparerT)
Constructs a new RedBlackTreeT using the provided IComparerT implementation.
Public methodRedBlackTreeT(IComparerT, Boolean)
Constructs a new RedBlackTreeT using the provided IComparerT implementation.
Top
Properties
  NameDescription
Public propertyComparer
Gets the IComparerT for this red black tree.
Public propertyCount
Gets the number of nodes contained in this red-black tree.
Public propertyIsReadOnly
Gets a value indicating whether this instance is read only. In a RedBlackTreeT, this returns false.
Public propertyRoot
Gets the root node of this tree.
(Inherited from BinaryTreeTNode.)
Top
Methods
  NameDescription
Public methodAdd(T)
Adds a new item to the tree. If the element already belongs to this tree, no new element will be added.
Public methodAdd(RedBlackTreeNodeT)
Adds a new item to the tree. If the element already belongs to this tree, no new element will be added.
Public methodClear
Removes all nodes from the tree.
Public methodContains(T)
Determines whether this tree contains the specified item.
Public methodContains(RedBlackTreeNodeT)
Determines whether this tree contains the specified item.
Public methodCopyTo(T, Int32)
Copies the elements of this tree to an array, starting at a particular arrayIndex.
Public methodCopyTo(RedBlackTreeNodeT, Int32)
Copies the nodes of this tree to an array, starting at a particular arrayIndex.
Public methodEquals
Determines whether the specified object is equal to the current object.
(Inherited from Object.)
Protected methodFinalize
Allows an object to try to free resources and perform other cleanup operations before it is reclaimed by garbage collection.
(Inherited from Object.)
Public methodFind
Attempts to find a node that contains the specified key.
Public methodFindGreaterThan(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.
Public methodFindGreaterThan(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.
Public methodFindLessThan(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.
Public methodFindLessThan(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.
Public methodFindLessThanOrEqualTo(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.
Public methodFindLessThanOrEqualTo(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.
Public methodGetEnumerator
Returns an enumerator that iterates through this tree in-order.
(Overrides BinaryTreeTNodeGetEnumerator.)
Public methodGetHashCode
Serves as the default hash function.
(Inherited from Object.)
Public methodGetNextNode
Gets the node that contains the next in-order value coming after the value contained in the given node.
Public methodGetPreviousNode
Gets the node that contains the previous in-order value coming before the value contained in the given node.
Public methodGetType
Gets the Type of the current instance.
(Inherited from Object.)
Public methodMax
Finds the maximum element stored in the tree.
Protected methodMemberwiseClone
Creates a shallow copy of the current Object.
(Inherited from Object.)
Public methodMin
Finds the minimum element stored in the tree.
Public methodRemove(T)
Removes a node from the tree.
Public methodRemove(RedBlackTreeNodeT)
Removes a node from the tree.
Public methodResort
Forces a re-balance of the tree by removing and inserting the same node.
Public methodToString
Returns a string that represents the current object.
(Inherited from Object.)
Public methodTraverse
Traverse the tree using a tree traversal method. Can be iterated with a foreach loop.
(Inherited from BinaryTreeTNode.)
Top
Extension Methods
  NameDescription
Public Extension MethodHasMethod
Checks whether an object implements a method with the given name.
(Defined by ExtensionMethods.)
Public Extension MethodIsEqual
Compares two objects for equality, performing an elementwise comparison if the elements are vectors or matrices.
(Defined by Matrix.)
Public Extension MethodSetEqualsT(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.)
Public Extension MethodSetEqualsRedBlackTreeNodeT(IEnumerableRedBlackTreeNodeT)Overloaded. (Defined by Matrix.)
Public Extension MethodTo(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.)
Public Extension MethodToTOverloaded.
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.)
Top
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:

See Also