Main Page   Class Hierarchy   Compound List   Header Files   Compound Members  

ddgSplayTree Class Reference

The ddgSplay Tree Class is a semi balanced binary tree which guarantees amortized O(ln(n)) access time for insert/remove and find operations. More...

#include <ddgsplay.h>

List of all members.


Public Members

 ddgSplayTree (void)
Constructor. More...

 ~ddgSplayTree (void)
Destructor.

ddgSplayIndex clear ( ddgSplayIndex n )
Release node and all child nodes.

ddgSplayIndex find ( ddgSplayKey k, ddgSplayIndex n )
Find the node corresponding to X.

ddgSplayIndex findMin ( ddgSplayIndex n )
Find the minimum value in the tree.

ddgSplayIndex findMax ( ddgSplayIndex n )
Find the maximum value in the tree.

ddgSplayIndex insert ( ddgSplayKey k, ddgSplayIndex n )
Insert a node.

ddgSplayIndex remove ( ddgSplayKey k, ddgSplayIndex n )
Remove a node.

void clear ( void )
Release node and all child nodes.

void find ( ddgSplayKey ti )
Find the node corresponding to X.

void findMin ( void )
Find the minimum value in the tree.

void findMax ( void )
Find the maximum value in the tree.

void insert ( ddgSplayKey k )
Insert a node.

void remove ( ddgSplayKey k )
Remove a node.

void insert ( unsigned int tree, unsigned int tindex, unsigned int priority )
Insert a node.

void remove ( unsigned int tree, unsigned int tindex, unsigned int priority )
Remove a node.

ddgSplayIndex root (void)
Return the root node.

ddgSplayKeyretrieve (void)
Return the index stored by this element.

void data (ddgSplayKey k )
Set the key and value stored by this element.

ddgSplayIndex left (ddgSplayIndex si)
Get the left child node for this index.

ddgSplayIndex right (ddgSplayIndex si)
Get the right child node for this index.

void left (ddgSplayIndex si, ddgSplayIndex sil)
Set the left child node for this index.

void right (ddgSplayIndex si, ddgSplayIndex sir)
Set the right child node for this index.

ddgSplayKey key (ddgSplayIndex si)
Get the key for this index.

void key (ddgSplayIndex si, ddgSplayKey sk)
Get the key for this index.

ddgSplayKeyretrieve (ddgSplayIndex si)
Return the index stored by this element.

void data (ddgSplayKey k, ddgSplayIndex si )
Set the index and tree stored by this element.

ddgSplayIndex allocNode (void)
Allocator for ddgSplayNodes.

void freeNode (ddgSplayIndex n)
Deallocator for ddgSplayNodes.

unsigned int size (void)
Return the current tree size.

ddgSplayIndex null (void)
Return the null node.

bool isnull (ddgSplayIndex n)
Return if the given node is null.


Detailed Description

The ddgSplay Tree Class is a semi balanced binary tree which guarantees amortized O(ln(n)) access time for insert/remove and find operations.

Individual accesses may not be O(ln(n)). Operations carried out on this tree cause the requested item to become the root of the tree. This allows nearby nodes to found very quickly on subsequent accesses. There are two sets of functions, the first require acess through a specified ddgSplayNode. The second set work from the current root node.
Note: To find the minimum/maximum and to iterate over this tree without disturbing the tree, use the ddgSplayIterator class.


Member Function Documentation

ddgSplayTree::ddgSplayTree (void)

Constructor.

The number of items to be allocated in the node cache can be specified only at construction time.


The documentation for this class was generated from the following files:
Generated at Sun Sep 17 19:27:56 2000 for Digital Dawn Graphics Toolkit by doxygen 0.49-991205 written by Dimitri van Heesch, © 1997-1999