New to Telerik UI for WinForms? Start a free 30-day trial

RBTreeBase<T, N, P>

Class

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:

Key type

Node type

Node parameter type

Syntax:

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(bool)

Tree constructor

public RBTreeBase(bool unique)

Parameters:uniquebool

RBTreeBase(IComparer<T>, bool)

Tree constructor with comparer

public RBTreeBase(IComparer<T> aComparer, bool unique)

Parameters:aComparerIComparer<T>uniquebool

Fields

mCount

int

protected int mCount

mRoot

RBTreeNodeBase<T, P>

protected RBTreeNodeBase<T, P> mRoot

mSyncRoot

object

protected object mSyncRoot

Properties

Collection

IList<T>

Get collection object for this

public IList<T> Collection { get; }

Count

int

Number of nodes in the tree

public int Count { get; }

Implements: ISortedTree<T>.Count

Root

Root of the tree

public N Root { get; }

SyncRoot

object

Object can be used for synchronization

public object SyncRoot { get; }

Implements: ITree<T>.SyncRoot

Unique

bool

Is tree unique

public bool Unique { get; }

Methods

Add(T)

Add new key into the tree

This operation is O(logN) operation

public N Add(T aKey)

Parameters:aKeyTReturns:

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

public N AddOrGet(T aKey)

Parameters:aKeyTReturns:

Balance(RBTreeNodeBase<T, P>)

Balance tree past inserting

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

Parameters:zRBTreeNodeBase<T, P>

Clear()

Remove all items

public void Clear()

Delete(RBTreeNodeBase<T, P>)

Delete the node z, and free up the space

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

Parameters:zRBTreeNodeBase<T, P>

DeleteFix(RBTreeNodeBase<T, P>)

Restore the reb-black properties after a delete

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

Parameters:xRBTreeNodeBase<T, P>

Find(T)

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

public N Find(T aKey)

Parameters:aKeyTReturns:

First()

Get first node This operation is O(logN) operation

public N First()

Returns:

Last()

Get last node This operation is O(logN) operation

public N Last()

Returns:

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

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

Parameters:xRBTreeNodeBase<T, P>

NewNode()

Create new node

protected abstract RBTreeNodeBase<T, P> NewNode()

Returns:

RBTreeNodeBase<T, P>

Next(N)

Get next node This operation is O(logN) operation

public N Next(N aNode)

Parameters:aNodeNReturns:

Predecessor(RBTreeNodeBase<T, P>)

Return a pointer to the largest key smaller than x

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

Parameters:xRBTreeNodeBase<T, P>Returns:

RBTreeNodeBase<T, P>

Previous(N)

Get previous node This operation is O(logN) operation

public N Previous(N aNode)

Parameters:aNodeNReturns:

Remove(N)

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

public bool Remove(N aNode)

Parameters:aNodeNReturns:

bool

Remove(T)

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

public bool Remove(T aKey)

Parameters:aKeyTReturns:

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

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

Parameters:yRBTreeNodeBase<T, P>

Successor(RBTreeNodeBase<T, P>)

Return a pointer to the smallest key greater than x

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

Parameters:xRBTreeNodeBase<T, P>Returns:

RBTreeNodeBase<T, P>