Class RBTreeBase<T, N, P>

Base class for the tree. Based on the Damian Ivereigh implementation Support for the multi-trees has been added. Do not use this class directly. Use RBTree, RBMultiTree, RBOrderedTree and RBOrderedMultiTree classes

Inheritance
System.Object
RBTreeBase<T, N, P>
RBMultiTree<T>
RBOrderedTreeBase<T>
RBTree<T>
Inherited Members
System.Object.ToString()
System.Object.Equals(System.Object)
System.Object.Equals(System.Object, System.Object)
System.Object.ReferenceEquals(System.Object, System.Object)
System.Object.GetHashCode()
System.Object.GetType()
System.Object.MemberwiseClone()
Namespace: Telerik.Collections.Generic
Assembly: Telerik.WinControls.dll

Syntax

public abstract class RBTreeBase<T, N, P> : ISortedTree<T>, ITree<T>, IEnumerable<N>, IEnumerable where N : RBTreeNodeBase<T, P>, new()
Type Parameters
T

Key type
N

Node type
P

Node parameter type

Constructors

RBTreeBase(Boolean)

Tree constructor

Declaration
public RBTreeBase(bool unique)
Parameters
System.Boolean unique

RBTreeBase(IComparer<T>, Boolean)

Tree constructor with comparer

Declaration
public RBTreeBase(IComparer<T> aComparer, bool unique)
Parameters
System.Collections.Generic.IComparer<T> aComparer

System.Boolean unique

Fields

mCount

Declaration
protected int mCount
Field Value
System.Int32

mRoot

Declaration
protected RBTreeNodeBase<T, P> mRoot
Field Value
RBTreeNodeBase<T, P>

mSyncRoot

Declaration
protected object mSyncRoot
Field Value
System.Object

Properties

Collection

Get collection object for this

Declaration
public IList<T> Collection { get; }
Property Value
System.Collections.Generic.IList<T>

Count

Number of nodes in the tree

Declaration
public int Count { get; }
Property Value
System.Int32

Implements

Root

Root of the tree

Declaration
public N Root { get; }
Property Value
N

SyncRoot

Object can be used for synchronization

Declaration
public object SyncRoot { get; }
Property Value
System.Object

Implements

Unique

Is tree unique

Declaration
public bool Unique { get; }
Property Value
System.Boolean

Methods

Add(T)

Add new key into the tree

This operation is O(logN) operation

Declaration
public N Add(T aKey)
Parameters
T aKey

Returns
N

Exceptions
System.ArgumentException

In case the key is already in the tree

AddOrGet(T)

Add new key into the tree or get existing node This operation is O(logN) operation

Declaration
public N AddOrGet(T aKey)
Parameters
T aKey

Returns
N

Balance(RBTreeNodeBase<T, P>)

Balance tree past inserting

Declaration
protected void Balance(RBTreeNodeBase<T, P> z)
Parameters
RBTreeNodeBase<T, P> z

Clear()

Remove all items

Declaration
public void Clear()

Delete(RBTreeNodeBase<T, P>)

Delete the node z, and free up the space

Declaration
protected virtual void Delete(RBTreeNodeBase<T, P> z)
Parameters
RBTreeNodeBase<T, P> z

DeleteFix(RBTreeNodeBase<T, P>)

Restore the reb-black properties after a delete

Declaration
protected void DeleteFix(RBTreeNodeBase<T, P> x)
Parameters
RBTreeNodeBase<T, P> x

Find(T)

Find key in the dictionary This operation is O(logN) operation

Declaration
public N Find(T aKey)
Parameters
T aKey

Returns
N

First()

Get first node This operation is O(logN) operation

Declaration
public N First()
Returns
N

Last()

Get last node This operation is O(logN) operation

Declaration
public N Last()
Returns
N

LeftRotate(RBTreeNodeBase<T, P>)

Rotate our tree Left

X rb_left_rotate(X)---> Y / \ / \ A Y X C / \ / \ B C A B

N.B. This does not change the ordering.

We assume that neither X or Y is NULL

Declaration
protected void LeftRotate(RBTreeNodeBase<T, P> x)
Parameters
RBTreeNodeBase<T, P> x

NewNode()

Create new node

Declaration
protected abstract RBTreeNodeBase<T, P> NewNode()
Returns
RBTreeNodeBase<T, P>

Next(N)

Get next node This operation is O(logN) operation

Declaration
public N Next(N aNode)
Parameters
N aNode

Returns
N

Predecessor(RBTreeNodeBase<T, P>)

Return a pointer to the largest key smaller than x

Declaration
protected RBTreeNodeBase<T, P> Predecessor(RBTreeNodeBase<T, P> x)
Parameters
RBTreeNodeBase<T, P> x

Returns
RBTreeNodeBase<T, P>

Previous(N)

Get previous node This operation is O(logN) operation

Declaration
public N Previous(N aNode)
Parameters
N aNode

Returns
N

Remove(T)

Remove key from the dictionary This operation is O(logN) operation

Declaration
public bool Remove(T aKey)
Parameters
T aKey

Returns
System.Boolean

Remove(N)

Remove node from the dictionary This operation is O(1) operation

Declaration
public bool Remove(N aNode)
Parameters
N aNode

Returns
System.Boolean

RightRotate(RBTreeNodeBase<T, P>)

Rotate our tree Right

X Y / \ / \ A Y leftArrow--rb_right_rotate(Y) X C / \ / \ B C A B

N.B. This does not change the ordering.

We assume that neither X or Y is NULL

Declaration
protected void RightRotate(RBTreeNodeBase<T, P> y)
Parameters
RBTreeNodeBase<T, P> y

Successor(RBTreeNodeBase<T, P>)

Return a pointer to the smallest key greater than x

Declaration
protected RBTreeNodeBase<T, P> Successor(RBTreeNodeBase<T, P> x)
Parameters
RBTreeNodeBase<T, P> x

Returns
RBTreeNodeBase<T, P>

Explicit Interface Implementations

IEnumerable<N>.GetEnumerator()

Get enumerator

Declaration
IEnumerator<N> IEnumerable<N>.GetEnumerator()
Returns
System.Collections.Generic.IEnumerator<N>

Implements
System.Collections.Generic.IEnumerable<T>.GetEnumerator()

IEnumerable.GetEnumerator()

Get enumerator

Declaration
IEnumerator IEnumerable.GetEnumerator()
Returns
System.Collections.IEnumerator

Implements
System.Collections.IEnumerable.GetEnumerator()

ISortedTree<T>.First()

Get first node

Declaration
ITreeNode<T> ISortedTree<T>.First()
Returns
ITreeNode<T>

Implements

ISortedTree<T>.Last()

Get last node

Declaration
ITreeNode<T> ISortedTree<T>.Last()
Returns
ITreeNode<T>

Implements

ISortedTree<T>.Next(ITreeNode<T>)

Get prior node

Declaration
ITreeNode<T> ISortedTree<T>.Next(ITreeNode<T> node)
Parameters
ITreeNode<T> node

Returns
ITreeNode<T>

Implements

ISortedTree<T>.Previous(ITreeNode<T>)

Get next node

Declaration
ITreeNode<T> ISortedTree<T>.Previous(ITreeNode<T> node)
Parameters
ITreeNode<T> node

Returns
ITreeNode<T>

Implements

ITree<T>.Add(T)

Add item

Declaration
ITreeNode<T> ITree<T>.Add(T item)
Parameters
T item

Returns
ITreeNode<T>

Implements

ITree<T>.AddOrGet(T)

Add or get item

Declaration
ITreeNode<T> ITree<T>.AddOrGet(T item)
Parameters
T item

Returns
ITreeNode<T>

Implements

ITree<T>.Clear()

Clear

Declaration
void ITree<T>.Clear()
Implements

ITree<T>.Find(T)

Find item

Declaration
ITreeNode<T> ITree<T>.Find(T item)
Parameters
T item

Returns
ITreeNode<T>

Implements

ITree<T>.Remove(T)

Delete item by key

Declaration
bool ITree<T>.Remove(T item)
Parameters
T item

Returns
System.Boolean

Implements

ITree<T>.Remove(ITreeNode<T>)

Delete item by key

Declaration
void ITree<T>.Remove(ITreeNode<T> node)
Parameters
ITreeNode<T> node

Implements

Extension Methods