AVLTree< Data, ConfigData > Class Template Reference

A templated balanced tree class. More...

#include <AVLTree.h>

Inheritance diagram for AVLTree< Data, ConfigData >:

List of all members.

Public Member Functions
	AVLTree (ACompareNodesAlgorithm< Data, ConfigData > *Compare, DeleteTreeDataEnum DeleteTreeData=NO_DELETE_TREE_ITEM, ConfigData *pConfigData=NULL)
	Constructor.
virtual	~AVLTree ()
	Destructor.
virtual Data *	Search (Data *NodeData, bool *NodeInserted)
	Find a data item. If not found, insert it.
virtual Data *	Find (Data *NodeData)
	Find a data item. If not found, return NULL.
virtual void	DeleteTree ()
	This tree can't destory itself with a destructor, use this function instead.
Data *	Delete (Data *NodeData)
	Delete a node from the tree.
Data *	DeleteRoot ()
	Delete the root node of the tree.
Protected Member Functions
Data *	Insert (AVLTree< Data, ConfigData > *Tree, Data *NodeData, bool &HasTreeGrown)
	Recursively search for the correct place for a node and insert it.
Data *	Find (AVLTree< Data, ConfigData > *Tree, Data *NodeData)
	Recursively search for data on an AVLTree.
AVLNode< Data > *	Remove (AVLTree< Data, ConfigData > *Tree, Data *NodeData, bool &HasTreeShrunk)
	Recursively search for a node and delete it.
AVLNode< Data > *	RemoveRoot (AVLTree< Data, ConfigData > *Tree, bool &HasTreeShrunk)
	Remove the root node of an AVL tree.
void	SwingLeft (AVLNode< Data > **Root)
	Swing node to the left, NO BALANCE MAINTAINANCE!!!
void	SwingRight (AVLNode< Data > **Root)
	Swing node to the right, NO BALANCE MAINTAINANCE!!!
void	BalanceAfterNastySwing (AVLNode< Data > *Root)
	Clean up after swings. This is what does the balance maintainance.
Protected Attributes
AVLNode< Data > *	m_Root
	Root node of the tree.

---

Detailed Description

template<class Data, class ConfigData>
class AVLTree< Data, ConfigData >

This class is based off of Daniel Nagy's AVL implementation of a balanced tree written in C

Definition at line 20 of file AVLTree.h.

---

Member Function Documentation

template<class Data, class ConfigData> void AVLTree< Data, ConfigData >::BalanceAfterNastySwing (  AVLNode< Data > *  Root  )  [protected]

Parameters: Root  is the node that will be the base of the balance Definition at line 335 of file AVLTree.h. References AVLNode< Data >::m_Balance, AVLNode< Data >::m_Left, and AVLNode< Data >::m_Right. Referenced by AVLTree< Data, ConfigData >::Insert(), and AVLTree< Data, ConfigData >::Remove().

template<class Data, class ConfigData> Data * AVLTree< Data, ConfigData >::Delete (  Data *  NodeData  )

Parameters: NodeData  is the data of the node to be deleted. Returns: Data of the deleted node. NULL if node isn't found. Definition at line 130 of file AVLTree.h. References AVLNode< Data >::m_Data, and AVLTree< Data, ConfigData >::Remove(). Referenced by TestAVLTree().

template<class Data, class ConfigData> Data * AVLTree< Data, ConfigData >::DeleteRoot (   )

Returns: Data of the deleted node. NULL if there aren't any nodes. Definition at line 244 of file AVLTree.h. References AVLNode< Data >::m_Data, and AVLTree< Data, ConfigData >::RemoveRoot().

template<class Data, class ConfigData> Data * AVLTree< Data, ConfigData >::Find (  AVLTree< Data, ConfigData > *  Tree, Data *  NodeData )  [protected]

Parameters: Tree  is the AVLTree being searched NodeData  is the data being searched for Returns: Pointer to the data found Definition at line 363 of file AVLTree.h. References AVLTree< Data, ConfigData >::Find(), AGenericTree< Data, ConfigData >::m_CompareNodes, AGenericTree< Data, ConfigData >::m_ConfigData, AGenericTree< Data, ConfigData >::m_DeleteTreeData, and AVLTree< Data, ConfigData >::m_Root.

template<class Data, class ConfigData> Data * AVLTree< Data, ConfigData >::Find (  Data *  NodeData  )  [virtual]

Parameters: NodeData  is the value being searched for. Returns: A pointer to the data found. NULL if data isn't found. Implements AGenericTree< Data, ConfigData >. Definition at line 357 of file AVLTree.h. Referenced by AVLTree< Data, ConfigData >::Find(), and AVLTree< Data, ConfigData >::Search().

template<class Data, class ConfigData> Data * AVLTree< Data, ConfigData >::Insert (  AVLTree< Data, ConfigData > *  Tree, Data *  NodeData, bool &  HasTreeGrown )  [protected]

Parameters: Tree  is the AVLTree to be searched NodeData  is the data of the node to be inserted HasTreeGrown  determines whether the tree needs to be rebalanced Returns: Pointer to the data added Definition at line 408 of file AVLTree.h. References AVLTree< Data, ConfigData >::BalanceAfterNastySwing(), AGenericTree< Data, ConfigData >::m_CompareNodes, AVLTree< Data, ConfigData >::m_Root, AVLTree< Data, ConfigData >::SwingLeft(), and AVLTree< Data, ConfigData >::SwingRight(). Referenced by AVLTree< Data, ConfigData >::Search().

template<class Data, class ConfigData> AVLNode< Data > * AVLTree< Data, ConfigData >::Remove (  AVLTree< Data, ConfigData > *  Tree, Data *  NodeData, bool &  HasTreeShrunk )  [protected]

Parameters: Tree  is the AVLTree to be searched NodeData  is the data of the node to be removed (but not deleted). HasTreeShrunk  determines whether the tree needs to be rebalanced Returns: Removed node. User is responsible to delete it. NULL if node isn't found. Definition at line 143 of file AVLTree.h. References AVLTree< Data, ConfigData >::BalanceAfterNastySwing(), AGenericTree< Data, ConfigData >::m_CompareNodes, AGenericTree< Data, ConfigData >::m_ConfigData, AGenericTree< Data, ConfigData >::m_DeleteTreeData, AVLTree< Data, ConfigData >::m_Root, AVLTree< Data, ConfigData >::RemoveRoot(), AVLTree< Data, ConfigData >::SwingLeft(), and AVLTree< Data, ConfigData >::SwingRight(). Referenced by AVLTree< Data, ConfigData >::Delete(), and AVLTree< Data, ConfigData >::RemoveRoot().

template<class Data, class ConfigData> AVLNode< Data > * AVLTree< Data, ConfigData >::RemoveRoot (  AVLTree< Data, ConfigData > *  Tree, bool &  HasTreeShrunk )  [protected]

Parameters: Tree  is the AVLTree to be searched HasTreeShrunk  determines whether the tree needs to be rebalanced Returns: Removed node. User is responsible to delete it. NULL if no root node. Definition at line 257 of file AVLTree.h. References AVLNode< Data >::m_Balance, AVLNode< Data >::m_Data, AVLNode< Data >::m_Left, AVLNode< Data >::m_Right, AVLTree< Data, ConfigData >::m_Root, and AVLTree< Data, ConfigData >::Remove(). Referenced by AVLTree< Data, ConfigData >::DeleteRoot(), and AVLTree< Data, ConfigData >::Remove().

template<class Data, class ConfigData> Data * AVLTree< Data, ConfigData >::Search (  Data *  NodeData, bool *  NodeInserted )  [virtual]

Parameters: NodeData  is the value being searched for. NodeInserted  is a flag to determine if the data was inserted Returns: A pointer to the data found. NULL if data is inserted Implements AGenericTree< Data, ConfigData >. Definition at line 392 of file AVLTree.h. References AVLTree< Data, ConfigData >::Find(), and AVLTree< Data, ConfigData >::Insert(). Referenced by TestAVLTree().

template<class Data, class ConfigData> void AVLTree< Data, ConfigData >::SwingLeft (  AVLNode< Data > **  Root  )  [protected]

Parameters: Root  is the node that the tree will rotate around Definition at line 315 of file AVLTree.h. References AVLNode< Data >::m_Left, and AVLNode< Data >::m_Right. Referenced by AVLTree< Data, ConfigData >::Insert(), and AVLTree< Data, ConfigData >::Remove().

template<class Data, class ConfigData> void AVLTree< Data, ConfigData >::SwingRight (  AVLNode< Data > **  Root  )  [protected]

Parameters: Root  is the node that the tree will rotate around Definition at line 325 of file AVLTree.h. References AVLNode< Data >::m_Left, and AVLNode< Data >::m_Right. Referenced by AVLTree< Data, ConfigData >::Insert(), and AVLTree< Data, ConfigData >::Remove().

---

The documentation for this class was generated from the following file:

• AVLTree.h

---