Class RedBlackTree<T>
A red black tree implementation.
Inheritance
RedBlackTree<T>
Assembly: Advanced.Algorithms.dll
Syntax
public class RedBlackTree<T> : IEnumerable<T> where T : IComparable
Type Parameters
Constructors
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).
|
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).
|
Properties
Count
Declaration
public int Count { get; }
Property Value
Methods
AsEnumerableDesc()
Declaration
public IEnumerable<T> AsEnumerableDesc()
Returns
Type |
Description |
IEnumerable<T> |
|
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
ElementAt(Int32)
Time complexity: O(log(n))
Declaration
public T ElementAt(int index)
Parameters
Type |
Name |
Description |
Int32 |
index |
|
Returns
GetEnumerator()
Declaration
public IEnumerator<T> GetEnumerator()
Returns
Type |
Description |
IEnumerator<T> |
|
GetEnumeratorDesc()
Declaration
public IEnumerator<T> GetEnumeratorDesc()
Returns
Type |
Description |
IEnumerator<T> |
|
HasItem(T)
Time complexity: O(log(n))
Declaration
public bool HasItem(T value)
Parameters
Type |
Name |
Description |
T |
value |
|
Returns
IndexOf(T)
Time complexity: O(log(n))
Declaration
public int IndexOf(T item)
Parameters
Type |
Name |
Description |
T |
item |
|
Returns
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
Max()
Time complexity: O(log(n))
Declaration
Returns
Min()
Time complexity: O(log(n))
Declaration
Returns
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
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
RemoveAt(Int32)
Time complexity: O(log(n))
Declaration
public T RemoveAt(int index)
Parameters
Type |
Name |
Description |
Int32 |
index |
|
Returns