Class RedBlackTree<T>

A red black tree implementation.

Inheritance
Object
RedBlackTree<T>
Implements
Inherited Members
Namespace: Advanced.Algorithms.DataStructures
Assembly: Advanced.Algorithms.dll
Syntax
public class RedBlackTree<T> : IEnumerable<T>, IEnumerable where T : IComparable
Type Parameters
Name Description
T

Constructors

| Improve this Doc View Source

RedBlackTree(Boolean, IEqualityComparer<T>)

Declaration
public RedBlackTree(bool enableNodeLookUp = false, IEqualityComparer<T> equalityComparer = null)
Parameters
Type Name Description
Boolean enableNodeLookUp

Enabling lookup will fasten deletion/insertion/exists operations at the cost of additional space.
IEqualityComparer<T> equalityComparer

Provide equality comparer for node lookup if enabled (required when T is not a value type).
| Improve this Doc View Source

RedBlackTree(IEnumerable<T>, Boolean, IEqualityComparer<T>)

Initialize the BST with given sorted keys optionally. Time complexity: O(n).

Declaration
public RedBlackTree(IEnumerable<T> sortedCollection, bool enableNodeLookUp = false, IEqualityComparer<T> equalityComparer = null)
Parameters
Type Name Description
IEnumerable<T> sortedCollection

The sorted initial collection.
Boolean enableNodeLookUp

Enabling lookup will fasten deletion/insertion/exists operations at the cost of additional space.
IEqualityComparer<T> equalityComparer

Provide equality comparer for node lookup if enabled (required when T is not a value type).

Properties

| Improve this Doc View Source

Count

Declaration
public int Count { get; }
Property Value
Type Description
Int32

Methods

| Improve this Doc View Source

AsEnumerableDesc()

Descending enumerable.

Declaration
public IEnumerable<T> AsEnumerableDesc()
Returns
Type Description
IEnumerable<T>
| Improve this Doc View Source

Delete(T)

Delete if value exists. Time complexity: O(log(n)) Returns the position (index) of the item if deleted; otherwise returns -1

Declaration
public int Delete(T value)
Parameters
Type Name Description
T value
Returns
Type Description
Int32
| Improve this Doc View Source

ElementAt(Int32)

Time complexity: O(log(n))

Declaration
public T ElementAt(int index)
Parameters
Type Name Description
Int32 index
Returns
Type Description
T
| Improve this Doc View Source

GetEnumerator()

Declaration
public IEnumerator<T> GetEnumerator()
Returns
Type Description
IEnumerator<T>
| Improve this Doc View Source

GetEnumeratorDesc()

Declaration
public IEnumerator<T> GetEnumeratorDesc()
Returns
Type Description
IEnumerator<T>
| Improve this Doc View Source

HasItem(T)

Time complexity: O(log(n))

Declaration
public bool HasItem(T value)
Parameters
Type Name Description
T value
Returns
Type Description
Boolean
| Improve this Doc View Source

IndexOf(T)

Time complexity: O(log(n))

Declaration
public int IndexOf(T item)
Parameters
Type Name Description
T item
Returns
Type Description
Int32
| Improve this Doc View Source

Insert(T)

Time complexity: O(log(n)). Returns the position (index) of the value in sorted order of this BST.

Declaration
public int Insert(T value)
Parameters
Type Name Description
T value
Returns
Type Description
Int32
| Improve this Doc View Source

Max()

Time complexity: O(log(n))

Declaration
public T Max()
Returns
Type Description
T
| Improve this Doc View Source

Min()

Time complexity: O(log(n))

Declaration
public T Min()
Returns
Type Description
T
| Improve this Doc View Source

NextHigher(T)

Get the next higher to given value in this BST.

Declaration
public T NextHigher(T value)
Parameters
Type Name Description
T value
Returns
Type Description
T
| Improve this Doc View Source

NextLower(T)

Get the next lower value to given value in this BST.

Declaration
public T NextLower(T value)
Parameters
Type Name Description
T value
Returns
Type Description
T
| Improve this Doc View Source

RemoveAt(Int32)

Time complexity: O(log(n))

Declaration
public T RemoveAt(int index)
Parameters
Type Name Description
Int32 index
Returns
Type Description
T

Explicit Interface Implementations

| Improve this Doc View Source

IEnumerable.GetEnumerator()

Declaration
IEnumerator IEnumerable.GetEnumerator()
Returns
Type Description
IEnumerator

Implements