DREAM: DREAM::AVLTree< key_type, item_type

List of all members.


Public Types
typedef Iterator< AVLTreeNode< key_type, item_type > >	iterator
	iterator class for convenience.
typedef Const_Iterator< AVLTreeNode< key_type, item_type > >	const_iterator
	const_iterator class for convenience.
Public Member Functions
	AVLTree ()
	Constructor.
	~AVLTree ()
	Destructor.
void	assign (const AVLTreeNode< key_type, item_type > begin_node, const AVLTreeNode< key_type, item_type > end_node)
	Assign operator.
void	assign (Iterator< AVLTreeNode< key_type, item_type > > &begin_iter, Iterator< AVLTreeNode< key_type, item_type > > &end_iter)
	Assign operator.
void	assign (Const_Iterator< AVLTreeNode< key_type, item_type > > &begin_iter, Const_Iterator< AVLTreeNode< key_type, item_type > > &end_iter)
	Assign operator.
AVLTreeNode< key_type, item_type > *	begin ()
	Returns a pointer to the smallest element in the AVLTree.
const AVLTreeNode< key_type, item_type > *	begin () const
	Returns a pointer to the smallest element in the AVLTree.
void	clear ()
	Erases elements in the AVLTree.
void	destroy ()
	Erases elements in the AVLTree, and calls delete on the item_type.
bool	empty ()
	Returns true if the AVLTree is empty.
bool	empty () const
	Returns true if the AVLTree is empty.
AVLTreeNode< key_type, item_type > *	end ()
	Returns NULL.
const AVLTreeNode< key_type, item_type > *	end () const
	Returns NULL.
void	erase (Iterator< AVLTreeNode< key_type, item_type > > &iter)
	Erase a node from the AVLTree.
void	erase (key_type key)
	Erase a node from the AVLTree.
AVLTreeNode< key_type, item_type > *	find (const key_type &key)
	Finds an AVLTree node in the AVLTree.
const AVLTreeNode< key_type, item_type > *	find (const key_type &key) const
	Finds an AVLTree node in the AVLTree.
void	insert (key_type key, item_type item)
	Inserts an AVLTree node in the AVLTree.
AVLTreeNode< key_type, item_type > *	last ()
	Returns an iterator to the last element of the AVLTree.
const AVLTreeNode< key_type, item_type > *	last () const
	Returns an iterator to the last element of the AVLTree.
item_type &	operator[] (uint i)
	operator [].
const item_type &	operator[] (uint i) const
	operator [].
uint	size () const
	Return the number of items in the AVLTree.
Protected Member Functions
void	balance (AVLTreeNode< key_type, item_type > *node_ptr)
	Balances the AVLTree from the given node if necessary.
void	balance_left (AVLTreeNode< key_type, item_type > *node_ptr)
	Balances the AVLTree to the right from the given node.
void	balance_right (AVLTreeNode< key_type, item_type > *node_ptr)
	Balances the AVLTree to the right from the given node.
AVLTreeNode< key_type, item_type > *	get_smaller_node (AVLTreeNode< key_type, item_type > node_ptr, AVLTreeNode< key_type, item_type > left_ptr, AVLTreeNode< key_type, item_type > *right_ptr)
	Finds the next smaller node in the subtree of node_ptr, removes it, and reconstructs the tree.
AVLTreeNode< key_type, item_type > *	get_larger_node (AVLTreeNode< key_type, item_type > node_ptr, AVLTreeNode< key_type, item_type > left_ptr, AVLTreeNode< key_type, item_type > *right_ptr)
	Finds the next larger node in the subtree of node_ptr, removes it, and reconstructs the tree.
void	erase_leaf (AVLTreeNode< key_type, item_type > node_ptr, AVLTreeNode< key_type, item_type > parent_ptr)
	Erase a leaf from the AVLTree.
void	erase_left_child (AVLTreeNode< key_type, item_type > node_ptr, AVLTreeNode< key_type, item_type > parent_ptr, AVLTreeNode< key_type, item_type > *left_ptr)
	Erase a node with only a left child from the AVLTree.
void	erase_right_child (AVLTreeNode< key_type, item_type > node_ptr, AVLTreeNode< key_type, item_type > parent_ptr, AVLTreeNode< key_type, item_type > *right_ptr)
	Erase a node with only a right child from the AVLTree.
void	erase (AVLTreeNode< key_type, item_type > node_ptr, AVLTreeNode< key_type, item_type > parent_ptr, AVLTreeNode< key_type, item_type > left_ptr, AVLTreeNode< key_type, item_type > right_ptr)
	Erase a node with both children present from the AVLTree.
Protected Attributes
AVLTreeNode< key_type, item_type > *	root_ptr_
	Pointer to the root of the tree.
AVLTreeNode< key_type, item_type > *	last_ptr_
	Pointer to the last element of the tree.
uint	size_
	Stores the number of items in the AVLTree.
Friends
class	Iterator< AVLTreeNode< key_type, item_type > >
	Allow iterators to manipulate protected members.
class	Const_Iterator< AVLTreeNode< key_type, item_type > >
	Allow iterators to manipulate protected members.

Detailed Description

template<class key_type, class item_type>
class DREAM::AVLTree< key_type, item_type >

This is necessary since we want random access to elements in the tree, which requires a mix of STL maps and vectors. We prefer faster find and insert operations, therefore the underlying data structure is an AVL tree as it allows for the easy and efficient implementation of all these operators.

Member Typedef Documentation