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

Copy

[SerializableAttribute]
public class RedBlackTree<T> : BinaryTree<RedBlackTreeNode<T>>, 
	IEnumerable

<SerializableAttribute>
Public Class RedBlackTree(Of T)
	Inherits BinaryTree(Of RedBlackTreeNode(Of T))
	Implements IEnumerable

Request Example View Source

Type Parameters

T: The type of the value to be stored.

The RedBlackTreeT type exposes the following members.

Constructors

	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.

Top

Properties

	Name	Description
	Comparer	Gets the IComparerT for this red black tree.
	Count	Gets the number of nodes contained in this red-black 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.)

Top

Methods

	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 in-order. (Overrides BinaryTreeTNodeGetEnumerator.)
	GetHashCode	Serves as the default hash function. (Inherited from Object.)
	GetNextNode	Gets the node that contains the next in-order value coming after the value contained in the given node.
	GetPreviousNode	Gets the node that contains the previous in-order 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 re-balance 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.)

Top

Extension Methods

	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.)

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:

Reference

Accord.Collections Namespace

RedBlackTreeAddLanguageSpecificTextSet("LST445140D5_0?cs=&lt;|vb=(Of |cpp=&lt;|fs=&lt;'|nu=(");TAddLanguageSpecificTextSet("LST445140D5_1?cs=&gt;|vb=)|cpp=&gt;|fs=&gt;|nu=)"); Class

Type Parameters

Reference

RedBlackTreeT Class