Back to all docs
API Reference / Telerik.Collections.Generic / RBTreeBase<T, N, P>

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

Definition

Namespace:Telerik.Collections.Generic

Assembly:Telerik.WinControls.dll

Type Parameters:

T

Key type

N

Node type

P

Node parameter type

Syntax:
cs-api-definition
public abstract class RBTreeBase<T, N, P> : ISortedTree<T>, ITree<T>, IEnumerable where N : RBTreeNodeBase<T, P>, new()

Inheritance: objectRBTreeBase<T, N, P>

Derived Classes: RBMultiTree<T>RBOrderedTreeBase<T>RBTree<T>

Implements: IEnumerableISortedTree<T>ITree<T>

Constructors

RBTreeBase(IComparer<T>, bool)

Tree constructor with comparer

Declaration

cs-api-definition
public RBTreeBase(IComparer<T> aComparer, bool unique)

Parameters

aComparer

IComparer<T>

unique

bool

RBTreeBase(bool)

Tree constructor

Declaration

cs-api-definition
public RBTreeBase(bool unique)

Parameters

unique

bool

Fields

mCount

Declaration

cs-api-definition
protected int mCount

Field Value

int

mRoot

Declaration

cs-api-definition
protected RBTreeNodeBase<T, P> mRoot

Field Value

RBTreeNodeBase<T, P>

mSyncRoot

Declaration

cs-api-definition
protected object mSyncRoot

Field Value

object

Properties

Collection

Get collection object for this

Declaration

cs-api-definition
public IList<T> Collection { get; }

Property Value

IList<T>

Count

Number of nodes in the tree

Declaration

cs-api-definition
public int Count { get; }

Property Value

int

Implements ISortedTree<T>.Count

Root

Root of the tree

Declaration

cs-api-definition
public N Root { get; }

Property Value

N

SyncRoot

Object can be used for synchronization

Declaration

cs-api-definition
public object SyncRoot { get; }

Property Value

object

Implements ITree<T>.SyncRoot

Unique

Is tree unique

Declaration

cs-api-definition
public bool Unique { get; }

Property Value

bool

Methods

Add(T)

Add new key into the tree

This operation is O(logN) operation

Declaration

cs-api-definition
public N Add(T aKey)

Parameters

aKey

T

Returns

N

Exceptions

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

cs-api-definition
public N AddOrGet(T aKey)

Parameters

aKey

T

Returns

N

Balance(RBTreeNodeBase<T, P>)

Balance tree past inserting

Declaration

cs-api-definition
protected void Balance(RBTreeNodeBase<T, P> z)

Parameters

z

RBTreeNodeBase<T, P>

Clear()

Remove all items

Declaration

cs-api-definition
public void Clear()

Delete(RBTreeNodeBase<T, P>)

Delete the node z, and free up the space

Declaration

cs-api-definition
protected virtual void Delete(RBTreeNodeBase<T, P> z)

Parameters

z

RBTreeNodeBase<T, P>

DeleteFix(RBTreeNodeBase<T, P>)

Restore the reb-black properties after a delete

Declaration

cs-api-definition
protected void DeleteFix(RBTreeNodeBase<T, P> x)

Parameters

x

RBTreeNodeBase<T, P>

Find(T)

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

Declaration

cs-api-definition
public N Find(T aKey)

Parameters

aKey

T

Returns

N

First()

Get first node This operation is O(logN) operation

Declaration

cs-api-definition
public N First()

Returns

N

Last()

Get last node This operation is O(logN) operation

Declaration

cs-api-definition
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

cs-api-definition
protected void LeftRotate(RBTreeNodeBase<T, P> x)

Parameters

x

RBTreeNodeBase<T, P>

NewNode()

Create new node

Declaration

cs-api-definition
protected abstract RBTreeNodeBase<T, P> NewNode()

Returns

RBTreeNodeBase<T, P>

Next(N)

Get next node This operation is O(logN) operation

Declaration

cs-api-definition
public N Next(N aNode)

Parameters

aNode

N

Returns

N

Predecessor(RBTreeNodeBase<T, P>)

Return a pointer to the largest key smaller than x

Declaration

cs-api-definition
protected RBTreeNodeBase<T, P> Predecessor(RBTreeNodeBase<T, P> x)

Parameters

x

RBTreeNodeBase<T, P>

Returns

RBTreeNodeBase<T, P>

Previous(N)

Get previous node This operation is O(logN) operation

Declaration

cs-api-definition
public N Previous(N aNode)

Parameters

aNode

N

Returns

N

Remove(N)

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

Declaration

cs-api-definition
public bool Remove(N aNode)

Parameters

aNode

N

Returns

bool

Remove(T)

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

Declaration

cs-api-definition
public bool Remove(T aKey)

Parameters

aKey

T

Returns

bool

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

cs-api-definition
protected void RightRotate(RBTreeNodeBase<T, P> y)

Parameters

y

RBTreeNodeBase<T, P>

Successor(RBTreeNodeBase<T, P>)

Return a pointer to the smallest key greater than x

Declaration

cs-api-definition
protected RBTreeNodeBase<T, P> Successor(RBTreeNodeBase<T, P> x)

Parameters

x

RBTreeNodeBase<T, P>

Returns

RBTreeNodeBase<T, P>

In this article
DefinitionConstructorsRBTreeBase(IComparer<T>, bool)RBTreeBase(bool)FieldsmCountmRootmSyncRootPropertiesCollectionCountRootSyncRootUniqueMethodsAdd(T)AddOrGet(T)Balance(RBTreeNodeBase<T, P>)Clear()Delete(RBTreeNodeBase<T, P>)DeleteFix(RBTreeNodeBase<T, P>)Find(T)First()Last()LeftRotate(RBTreeNodeBase<T, P>)NewNode()Next(N)Predecessor(RBTreeNodeBase<T, P>)Previous(N)Remove(N)Remove(T)RightRotate(RBTreeNodeBase<T, P>)Successor(RBTreeNodeBase<T, P>)
Not finding the help you need?
Contact Support