AVLTree< Key, Data > Class Template Reference

A very fast AVL tree implementation. More...

#include <avltree.h>

List of all members.

Public Member Functions
	AVLTree ()
	The default constructor.
virtual	~AVLTree ()
	The destructor.
bool	insert (Key const &_key, Data const &_data)
	Inserts data into the tree.
bool	erase (Key const &_key)
	Deletes a node from the tree, specified by the node's key.
bool	erase (Key const &_key, Data const &_data)
	Deletes a node from the tree, specified by the node's key and data.
bool	find (Key const &_key, Data &_data) const
	Finds a node in the tree and copies the data from that node to a specified location.
Data	find (Key const &_key) const
	Finds a node in the tree and returns the data at that node.
bool	exists (Key const &_key) const
	Tests whether a key is in the tree or not.
void	empty ()
	Empties the entire tree.
size_t	size () const
	Indicates the size of the tree.
bool	replace (Key const &_key, Data const &_data)
	Change the data at the given node.
DArray< Data > *	ConvertToDArray () const
	Converts the tree data into a linearized DArray.
DArray< Key > *	ConvertIndexToDArray () const
	Converts the tree keys into a linearized DArray.
size_t	mem_usage () const
	Returns the overhead caused by the data structure.
Protected Types
enum	Result { OK, BALANCE, INVALID }
	Result of tree operation. More...
Protected Member Functions
void	rotateLeft (AVLNode< Key, Data > **_node)
	Rotate tree left.
void	rotateRight (AVLNode< Key, Data > **_node)
	Rotate tree right.
Result	balanceLeftGrown (AVLNode< Key, Data > **_node)
	Rebalance tree.
Result	balanceRightGrown (AVLNode< Key, Data > **_node)
	Rebalance tree.
Result	balanceLeftShrunk (AVLNode< Key, Data > **_node)
	Rebalance tree.
Result	balanceRightShrunk (AVLNode< Key, Data > **_node)
	Rebalance tree.
bool	replaceWithHighest (AVLNode< Key, Data > *_target, AVLNode< Key, Data > **_subtree, Result *_result)
	Replace node.
bool	replaceWithLowest (AVLNode< Key, Data > *_target, AVLNode< Key, Data > **_subtree, Result *_result)
	Replace node.
Result	insert (AVLNode< Key, Data > **_parent, AVLNode< Key, Data > **_node, Key const &_key, Data const &_data)
	Add object.
Result	erase (AVLNode< Key, Data > **_node, Key const &_key)
	Remove object.
Result	erase (AVLNode< Key, Data > **_node, Key const &_key, Data const &_data)
	Remove object.
AVLNode< Key, Data > *	findNode (Key const &_key) const
	Find a node in the tree.
void	RecursiveConvertIndexToDArray (DArray< Key > *_darray, AVLNode< Key, Data > *_btree) const
	Recursively convert the tree's keys into a DArray.
void	RecursiveConvertToDArray (DArray< Data > *_darray, AVLNode< Key, Data > *_btree) const
	Recursively convert the tree's data into a DArray.
bool	valid (const AVLNode< Key, Data > *_node) const
	Verifies that a node is valid.
Protected Attributes
AVLNode< Key, Data > *	m_root
	The root node.
size_t	m_size
	The current tree size.
Private Member Functions
	AVLTree (const AVLTree< Key, Data > &)
	Private copy constructor.
AVLTree< Key, Data > &	operator= (const AVLTree< Key, Data > &)
	Private assignment operator.

---

Detailed Description

template<class Key, class Data>
class CrissCross::Data::AVLTree< Key, Data >

A very fast AVL tree implementation.

AVL trees are quite useful for tasks that require very fast and well-balanced trees. Due to the ruleset implemented internally, AVL trees enforce a maximum height of 1.44*log(n).

---

Member Enumeration Documentation

enum Result [protected]

Result of tree operation.

Enumerator:

OK	None of the subtrees has grown in height, entire tree is still balanced.
BALANCE	One of the branches has grown/shrunk in height, tree might need rebalancing.
INVALID	Error.

---

Constructor & Destructor Documentation

AVLTree

(

const AVLTree< Key, Data > &

)

[private]

Private copy constructor.

If your code needs to invoke the copy constructor, you've probably written the code wrong. A tree copy is generally unnecessary, and in cases that it is, it can be achieved by other means.

---

Member Function Documentation

Result balanceLeftGrown

(

AVLNode< Key, Data > **

_node

)

[inline, protected]

Rebalance tree.

Rebalance tree after left side has grown

Parameters:

_node

Pointer to current node pointer to balance

Returns:

OK if tree is balanced (entire tree is valid), BALANCE if local tree is balanced but has grown in height (entire tree not guaranteed to be valid)

Result balanceLeftShrunk

(

AVLNode< Key, Data > **

_node

)

[inline, protected]

Rebalance tree.

Rebalance tree after left side has shrunk

Parameters:

_node

Pointer to current node pointer to balance

Returns:

OK if tree is balanced (entire tree is valid), BALANCE if local tree is balanced but has shrunk in height (entire tree not guaranteed to be valid)

Result balanceRightGrown

(

AVLNode< Key, Data > **

_node

)

[inline, protected]

Rebalance tree.

Rebalance tree after right side has grown

Parameters:

_node

Pointer to current node pointer to balance

Returns:

OK if tree is balanced (entire tree is valid), BALANCE if local tree is balanced but has grown in height (entire tree not guaranteed to be valid)

Result balanceRightShrunk

(

AVLNode< Key, Data > **

_node

)

[inline, protected]

Rebalance tree.

Rebalance tree after right side has shrunk

Parameters:

_node

Pointer to current node pointer to balance

Returns:

OK if tree is balanced (entire tree is valid), BALANCE if local tree is balanced but has shrunk in height (entire tree not guaranteed to be valid)

DArray<Key>* ConvertIndexToDArray

(

)

const

Converts the tree keys into a linearized DArray.

Returns:

A DArray containing the keys in the tree.

Warning:

Delete the returned DArray when done with it.

DArray<Data>* ConvertToDArray

(

)

const

Converts the tree data into a linearized DArray.

Returns:

A DArray containing the data of the tree.

Warning:

Delete the returned DArray when done with it.

void empty

(

)

[inline]

Empties the entire tree.

Warning:

This won't free the memory occupied by the data, so the data must be freed separately. The preferred way to do this is to serialize the data into a DArray with ConvertToDArray() and then iterate through it to delete the data in whatever way is proper.

References AVLTree< Key, Data >::m_root, and AVLTree< Key, Data >::m_size.

bool erase	(	Key const &	_key,
		Data const &	_data
	)

Deletes a node from the tree, specified by the node's key and data.

Warning:

This won't free the memory occupied by the data, so the data must be freed separately.

Parameters:

	_key	The key of the node to delete.
	_data	The data of the node to delete.

Returns:

True on success, false on failure.

bool erase

(

Key const &

_key

)

Deletes a node from the tree, specified by the node's key.

Warning:

This won't free the memory occupied by the data, so the data must be freed separately.

Parameters:

_key

The key of the node to delete.

Returns:

True on success, false on failure

Result erase	(	AVLNode< Key, Data > **	_node,
		Key const &	_key,
		Data const &	_data
	)			[protected]

Remove object.

Remove object from tree and rebalance, taking the key and data into account

Parameters:

	_node	Pointer to current node pointer
	_key	Identifier of node to remove
	_data	Data identifier of node to remove

Returns:

Result of removal (OK if subtree is balanced, BALANCE if tree is heavy on either side)

Result erase	(	AVLNode< Key, Data > **	_node,
		Key const &	_key
	)			[protected]

Remove object.

Remove object from tree and rebalance

Parameters:

	_node	Pointer to current node pointer
	_key	Identifier of node to remove

Returns:

Result of removal (OK if subtree is balanced, BALANCE if tree is heavy on either side)

bool exists

(

Key const &

_key

)

const

Tests whether a key is in the tree or not.

Parameters:

_key

The key of the node to find.

Returns:

True if the key is in the tree, false if not.

Data find

(

Key const &

_key

)

const

Finds a node in the tree and returns the data at that node.

Parameters:

_key

The key of the node to find.

Returns:

The data at the node. NULL if not found.

Deprecated:

The return value of this function could be unpredictable if the contents of the table was anything but pointers or integers.

See also:

find

bool find	(	Key const &	_key,
		Data &	_data
	)			const

Finds a node in the tree and copies the data from that node to a specified location.

Parameters:

	_key	The key of the node to find.
	_data	On return, will contain the data at the node. If not found, _data does not change.

Returns:

True on success, false on failure.

AVLNode<Key, Data>* findNode

(

Key const &

_key

)

const [protected]

Find a node in the tree.

Get a pointer to a node with the specified key value

Parameters:

_key

Identifier of node to remove

Returns:

Address of the node. If not found, returns NULL.

bool insert	(	Key const &	_key,
		Data const &	_data
	)

Inserts data into the tree.

Parameters:

	_key	The key of the data.
	_data	The data to insert.

Returns:

True on success, false on failure.

Result insert	(	AVLNode< Key, Data > **	_parent,
		AVLNode< Key, Data > **	_node,
		Key const &	_key,
		Data const &	_data
	)			[protected]

Add object.

Insert object in tree and rebalance

Parameters:

	_parent	Pointer to parent node pointer
	_node	Pointer to current node pointer
	_key	Key to insert
	_data	Data to insert

Returns:

Result of addition (OK if subtree is balanced, BALANCE if tree is heavy on either side)

size_t mem_usage

(

)

const

Returns the overhead caused by the data structure.

Returns:

Memory usage in bytes.

AVLTree<Key, Data>& operator=

(

const AVLTree< Key, Data > &

)

[private]

Private assignment operator.

If your code needs to invoke the assignment operator, you've probably written the code wrong. A tree copy is generally unnecessary, and in cases that it is, it can be achieved by other means.

void RecursiveConvertIndexToDArray	(	DArray< Key > *	_darray,
		AVLNode< Key, Data > *	_btree
	)			const [protected]

Recursively convert the tree's keys into a DArray.

Parameters:

	_darray	Array to insert keys into
	_btree	The node being traversed

void RecursiveConvertToDArray	(	DArray< Data > *	_darray,
		AVLNode< Key, Data > *	_btree
	)			const [protected]

Recursively convert the tree's data into a DArray.

Parameters:

	_darray	Array to insert data into
	_btree	The node being traversed

bool replace	(	Key const &	_key,
		Data const &	_data
	)

Change the data at the given node.

Parameters:

	_key	The key of the node to be modified.
	_data	The data to insert.

Returns:

True on success, false on failure.

bool replaceWithHighest	(	AVLNode< Key, Data > *	_target,
		AVLNode< Key, Data > **	_subtree,
		Result *	_result
	)			[inline, protected]

Replace node.

Replace a node with the highest-ranking item in subtree

Parameters:

	_target	Pointer to node to be replaced
	_subtree	Pointer to subtree pointer to search
	_result	Pointer to result variable to tell caller if further checks are needed

Returns:

true if node found, false if not

bool replaceWithLowest	(	AVLNode< Key, Data > *	_target,
		AVLNode< Key, Data > **	_subtree,
		Result *	_result
	)			[inline, protected]

Replace node.

Replace a node with the lowest-ranking item in subtree

Parameters:

	_target	Pointer to node to be replaced
	_subtree	Pointer to subtree pointer to search
	_result	Pointer to result variable to tell caller if further checks are needed

Returns:

true if node found, false if not

void rotateLeft

(

AVLNode< Key, Data > **

_node

)

[inline, protected]

Rotate tree left.

Rotate tree left around the given node

Parameters:

_node

Pointer to current node pointer to rotate

void rotateRight

(

AVLNode< Key, Data > **

_node

)

[inline, protected]

Rotate tree right.

Rotate tree right around the given node

Parameters:

_node

Pointer to current node pointer to rotate

size_t size

(

)

const [inline]

Indicates the size of the tree.

Returns:

Size of the tree.

References AVLTree< Key, Data >::m_size.

bool valid

(

const AVLNode< Key, Data > *

_node

)

const [inline, protected]

Verifies that a node is valid.

Parameters:

_node

A node pointer.

Returns:

True if the node is a valid node, false otherwise.