---

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.
		ddgSplayKey*	retrieve (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.
		ddgSplayKey*	retrieve (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:

• ddgsplay.h
• ddgsplay.cpp

---