AVLRedBlackTree< Data, ConfigData > Class Template Reference

A templated red-black tree class. More...

#include <AVLRedBlackTree.h>

Inheritance diagram for AVLRedBlackTree< Data, ConfigData >:

List of all members.

Public Member Functions
	AVLRedBlackTree (ACompareNodesAlgorithm< Data, ConfigData > *Compare, DeleteTreeDataEnum DeleteTreeData=NO_DELETE_TREE_ITEM, ConfigData *pConfigData=NULL)
	Constructor.
virtual	~AVLRedBlackTree ()
	Destructor.
AVLRedBlackTree< Data, ConfigData > *	Copy ()
	Make a copy of the tree (creates new nodes).
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.
Data *	Traverse (TraverseNode< Data > *TravNode)
	Walks the tree in inorder, looking for a data item. If not found, return NULL.
Data *	FindClose (const Data *NodeData)
	Search tree for a data item close to the value of Item, and return it.
Data *	Delete (const Data *NodeData)
	Delete a node from the tree.
void	Verify (bool *IsDone)
	Verify the validity of the tree.
bool	Compare (AVLRedBlackTree< Data, ConfigData > *Tree)
	Compares two AVLRedBlackTrees.
bool	CompareNodes (AVLRedBlackNode< Data > *Node1, AVLRedBlackNode< Data > *Node2)
	Compares two nodes and their children.
Private Attributes
AVLRedBlackNode< Data > *	m_Root
	Root node of the tree.
int	m_Count
	Number of nodes in the tree.

---

Detailed Description

template<class Data, class ConfigData>
class AVLRedBlackTree< Data, ConfigData >

This class is based off of Ben Pfaff's <pfaffben@pilot.msu.edu> AVL implementation of a red-black tree written in C

Basically a red/black balanced tree has the following properties:-*
1) Every node is either red or black (color is RED or BLACK)
2) A leaf (NULL pointer) is considered black
3) If a node is red then its children are black
4) Every path from a node to a leaf contains the same no of black nodes

3) & 4) above guarantee that the longest path (alternating red and black nodes) is only twice as long as the shortest path (all black nodes). Thus the tree remains fairly balanced.

Definition at line 60 of file AVLRedBlackTree.h.

---

Constructor & Destructor Documentation

template<class Data, class ConfigData> AVLRedBlackTree< Data, ConfigData >::~AVLRedBlackTree (   )  [virtual]

going Right; Definition at line 149 of file AVLRedBlackTree.h. References AVLRedBlackNode< Data >::m_Left, AVLRedBlackNode< Data >::m_Right, AVLRedBlackTree< Data, ConfigData >::m_Root, and RB_MAX_HEIGHT.

---

Member Function Documentation

template<class Data, class ConfigData> bool AVLRedBlackTree< Data, ConfigData >::Compare (  AVLRedBlackTree< Data, ConfigData > *  Tree  )

Parameters: Tree  Tree to compare with Returns: True if equal, False if not equal Definition at line 271 of file AVLRedBlackTree.h. References AVLRedBlackTree< Data, ConfigData >::CompareNodes(), AGenericTree< Data, ConfigData >::m_CompareNodes, AGenericTree< Data, ConfigData >::m_ConfigData, and AVLRedBlackTree< Data, ConfigData >::m_Root. Referenced by AVLRedBlackTree< Data, ConfigData >::CompareNodes(), and TestAVLRedBlackTree().

template<class Data, class ConfigData> bool AVLRedBlackTree< Data, ConfigData >::CompareNodes (  AVLRedBlackNode< Data > *  Node1, AVLRedBlackNode< Data > *  Node2 )

Parameters: Node1  The first node Node2  The second node Returns: True if equal, False if not equal Definition at line 769 of file AVLRedBlackTree.h. References AVLRedBlackTree< Data, ConfigData >::Compare(), AVLRedBlackNode< Data >::m_Color, AVLRedBlackNode< Data >::m_Data, AVLRedBlackNode< Data >::m_Left, and AVLRedBlackNode< Data >::m_Right. Referenced by AVLRedBlackTree< Data, ConfigData >::Compare().

template<class Data, class ConfigData> AVLRedBlackTree< Data, ConfigData > * AVLRedBlackTree< Data, ConfigData >::Copy (   )

Returns: Pointer to the new tree Definition at line 196 of file AVLRedBlackTree.h. References AVLRedBlackNode< Data >::m_Color, AGenericTree< Data, ConfigData >::m_CompareNodes, AGenericTree< Data, ConfigData >::m_ConfigData, AVLRedBlackTree< Data, ConfigData >::m_Count, AVLRedBlackNode< Data >::m_Data, AGenericTree< Data, ConfigData >::m_DeleteTreeData, AVLRedBlackNode< Data >::m_Left, AVLRedBlackNode< Data >::m_Right, AVLRedBlackTree< Data, ConfigData >::m_Root, and RB_MAX_HEIGHT. Referenced by TestAVLRedBlackTree().

template<class Data, class ConfigData> Data * AVLRedBlackTree< Data, ConfigData >::Delete (  const 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 527 of file AVLRedBlackTree.h. References AVLRedBlackNode< Data >::m_Color, AGenericTree< Data, ConfigData >::m_CompareNodes, AGenericTree< Data, ConfigData >::m_ConfigData, AVLRedBlackTree< Data, ConfigData >::m_Count, AVLRedBlackNode< Data >::m_Data, AVLRedBlackNode< Data >::m_Left, AVLRedBlackNode< Data >::m_Right, AVLRedBlackTree< Data, ConfigData >::m_Root, and RB_MAX_HEIGHT. Referenced by TestAVLRedBlackTree().

template<class Data, class ConfigData> Data * AVLRedBlackTree< 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 478 of file AVLRedBlackTree.h. References AGenericTree< Data, ConfigData >::m_CompareNodes, AGenericTree< Data, ConfigData >::m_ConfigData, AVLRedBlackNode< Data >::m_Data, AVLRedBlackNode< Data >::m_Left, AVLRedBlackNode< Data >::m_Right, and AVLRedBlackTree< Data, ConfigData >::m_Root.

template<class Data, class ConfigData> Data * AVLRedBlackTree< Data, ConfigData >::FindClose (  const Data *  NodeData  )

Search tree for an item close to the value of Item, and return it. This function will return a null pointer only if tree is empty. Parameters: NodeData  is the data being searched for. Returns: A pointer to the data found. This function will return a null pointer only if tree is empty. Definition at line 497 of file AVLRedBlackTree.h. References AGenericTree< Data, ConfigData >::m_CompareNodes, AGenericTree< Data, ConfigData >::m_ConfigData, AVLRedBlackNode< Data >::m_Data, AVLRedBlackNode< Data >::m_Left, AVLRedBlackNode< Data >::m_Right, and AVLRedBlackTree< Data, ConfigData >::m_Root.

template<class Data, class ConfigData> Data * AVLRedBlackTree< 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 324 of file AVLRedBlackTree.h. References AVLRedBlackNode< Data >::m_Color, AGenericTree< Data, ConfigData >::m_CompareNodes, AGenericTree< Data, ConfigData >::m_ConfigData, AVLRedBlackTree< Data, ConfigData >::m_Count, AVLRedBlackNode< Data >::m_Data, AGenericTree< Data, ConfigData >::m_DeleteTreeData, AVLRedBlackNode< Data >::m_Left, AVLRedBlackNode< Data >::m_Right, AVLRedBlackTree< Data, ConfigData >::m_Root, and RB_MAX_HEIGHT. Referenced by TestAVLRedBlackTree().

template<class Data, class ConfigData> Data * AVLRedBlackTree< Data, ConfigData >::Traverse (  TraverseNode< Data > *  TravNode  )

Parameters: TraverseNode  used to walk the tree Returns: A pointer to the data found. NULL if data isn't found. Definition at line 284 of file AVLRedBlackTree.h. References TraverseNode< Data >::m_Initialize, TraverseNode< Data >::m_Node, AVLRedBlackTree< Data, ConfigData >::m_Root, TraverseNode< Data >::m_Stack, and TraverseNode< Data >::m_TopOfStack.

template<class Data, class ConfigData> void AVLRedBlackTree< Data, ConfigData >::Verify (  bool *  IsDone  )

The tree is verified by the number of nodes in the tree matching m_Count Returns: Whether or not the tree finished counting. Definition at line 808 of file AVLRedBlackTree.h. References AVLRedBlackTree< Data, ConfigData >::m_Count, AVLRedBlackTree< Data, ConfigData >::m_Root, and RecurseTree().

---

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

• AVLRedBlackTree.h

---