RedBlackTree< Data, ConfigData > Class Template Reference

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

#include <RedBlackTree.h>

Inheritance diagram for RedBlackTree< Data, ConfigData >:

List of all members.

Public Member Functions
	RedBlackTree (ACompareNodesAlgorithm< Data, ConfigData > *Compare, DeleteTreeDataEnum DeleteTreeData=NO_DELETE_TREE_ITEM, ConfigData *pConfigData=NULL)
	Constructor.
	~RedBlackTree ()
	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.
Data *	Lookup (RedBlackTreeLookup Mode, Data *NodeData)
	Search for a value according to a mode.
Data *	Delete (Data *NodeData)
	Delete a node from the tree.
Protected Member Functions
RedBlackNode< Data > *	Traverse (bool Insert, Data *NodeData, bool *NodeInserted)
	Find a data item, conditionally insert it if not found.
void	DeleteNode (RedBlackNode< Data > **Root, RedBlackNode< Data > *Node)
	Delete a node from the tree.
void	DeleteNodeFix (RedBlackNode< Data > **Root, RedBlackNode< Data > *Node)
	Rebalance the tree after a deletion.
void	LeftRotate (RedBlackNode< Data > **Root, RedBlackNode< Data > *x)
	Rotate node one node to the left.
void	RightRotate (RedBlackNode< Data > **Root, RedBlackNode< Data > *y)
	Rotate node one node to the right.
RedBlackNode< Data > *	GetSuccessor (const RedBlackNode< Data > *Node)
	Get the smallest value greater than x.
RedBlackNode< Data > *	GetPredecessor (const RedBlackNode< Data > *Node)
	Get the largest value smaller than x.
Protected Attributes
RedBlackNode< Data > *	m_Root
	Root node of the tree.

---

Detailed Description

template<class Data, class ConfigData>
class RedBlackTree< Data, ConfigData >

This class is based off of Damian Ivereigh's implementation of a red-black tree written in C
The algorithm is the fairly standard red/black taken from "Introduction to Algorithms" by Cormen, Leiserson & Rivest.

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 (RBNULL 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 38 of file RedBlackTree.h.

---

Member Function Documentation

template<class Data, class ConfigData> Data * RedBlackTree< 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 386 of file RedBlackTree.h. References RedBlackTree< Data, ConfigData >::DeleteNode(), RedBlackNode< Data >::m_Data, RedBlackTree< Data, ConfigData >::m_Root, and RedBlackTree< Data, ConfigData >::Traverse(). Referenced by TestRedBlackTree().

template<class Data, class ConfigData> void RedBlackTree< Data, ConfigData >::DeleteNode (  RedBlackNode< Data > **  Root, RedBlackNode< Data > *  Node )  [protected]

Parameters: Node  is the node to be deleted. Root  is the parent node to be modified after the deletion Definition at line 405 of file RedBlackTree.h. References RedBlackTree< Data, ConfigData >::DeleteNodeFix(), RedBlackTree< Data, ConfigData >::GetSuccessor(), RedBlackNode< Data >::m_Color, RedBlackNode< Data >::m_Data, RedBlackNode< Data >::m_Left, RedBlackNode< Data >::m_Right, and RedBlackNode< Data >::m_Up. Referenced by RedBlackTree< Data, ConfigData >::Delete().

template<class Data, class ConfigData> void RedBlackTree< Data, ConfigData >::DeleteNodeFix (  RedBlackNode< Data > **  Root, RedBlackNode< Data > *  Node )  [protected]

Parameters: Node  is the node to be deleted. Root  is the parent node to be modified after the deletion Definition at line 445 of file RedBlackTree.h. References RedBlackTree< Data, ConfigData >::LeftRotate(), RedBlackNode< Data >::m_Color, RedBlackNode< Data >::m_Left, RedBlackNode< Data >::m_Right, RedBlackNode< Data >::m_Up, and RedBlackTree< Data, ConfigData >::RightRotate(). Referenced by RedBlackTree< Data, ConfigData >::DeleteNode().

template<class Data, class ConfigData> Data * RedBlackTree< 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 145 of file RedBlackTree.h. References RedBlackNode< Data >::m_Data, RedBlackTree< Data, ConfigData >::m_Root, and RedBlackTree< Data, ConfigData >::Traverse(). Referenced by TestRedBlackTree().

template<class Data, class ConfigData> RedBlackNode< Data > * RedBlackTree< Data, ConfigData >::GetPredecessor (  const RedBlackNode< Data > *  Node  )  [protected]

Parameters: Node  contains the value x Returns: A pointer to the largest key smaller than x Definition at line 653 of file RedBlackTree.h. References RedBlackNode< Data >::m_Left, RedBlackNode< Data >::m_Right, and RedBlackNode< Data >::m_Up. Referenced by RedBlackTree< Data, ConfigData >::Lookup().

template<class Data, class ConfigData> RedBlackNode< Data > * RedBlackTree< Data, ConfigData >::GetSuccessor (  const RedBlackNode< Data > *  Node  )  [protected]

Parameters: Node  contains the value x Returns: A pointer to the smallest value greater than x Definition at line 627 of file RedBlackTree.h. References RedBlackNode< Data >::m_Left, RedBlackNode< Data >::m_Right, and RedBlackNode< Data >::m_Up. Referenced by RedBlackTree< Data, ConfigData >::DeleteNode(), and RedBlackTree< Data, ConfigData >::Lookup().

template<class Data, class ConfigData> void RedBlackTree< Data, ConfigData >::LeftRotate (  RedBlackNode< Data > **  Root, RedBlackNode< Data > *  x )  [protected]

Parameters: x  is the node to be moved Root  is the parent node to be modified after the move Definition at line 540 of file RedBlackTree.h. References RedBlackNode< Data >::m_Left, RedBlackNode< Data >::m_Right, and RedBlackNode< Data >::m_Up. Referenced by RedBlackTree< Data, ConfigData >::DeleteNodeFix(), and RedBlackTree< Data, ConfigData >::Traverse().

template<class Data, class ConfigData> Data * RedBlackTree< Data, ConfigData >::Lookup (  RedBlackTreeLookup  Mode, Data *  NodeData )

Parameters: Mode  to look for value NodeData  is the value being searched for Definition at line 160 of file RedBlackTree.h. References RedBlackTree< Data, ConfigData >::GetPredecessor(), RedBlackTree< Data, ConfigData >::GetSuccessor(), AGenericTree< Data, ConfigData >::m_CompareNodes, AGenericTree< Data, ConfigData >::m_ConfigData, RedBlackNode< Data >::m_Data, RedBlackNode< Data >::m_Left, RedBlackNode< Data >::m_Right, and RedBlackTree< Data, ConfigData >::m_Root. Referenced by TestRedBlackTree().

template<class Data, class ConfigData> void RedBlackTree< Data, ConfigData >::RightRotate (  RedBlackNode< Data > **  Root, RedBlackNode< Data > *  y )  [protected]

Parameters: y  is the node to be moved Root  is the parent node to be modified after the move Definition at line 582 of file RedBlackTree.h. References RedBlackNode< Data >::m_Left, RedBlackNode< Data >::m_Right, and RedBlackNode< Data >::m_Up. Referenced by RedBlackTree< Data, ConfigData >::DeleteNodeFix(), and RedBlackTree< Data, ConfigData >::Traverse().

template<class Data, class ConfigData> Data * RedBlackTree< 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 137 of file RedBlackTree.h. References RedBlackNode< Data >::m_Data, and RedBlackTree< Data, ConfigData >::Traverse(). Referenced by TestRedBlackTree().

template<class Data, class ConfigData> RedBlackNode< Data > * RedBlackTree< Data, ConfigData >::Traverse (  bool  Insert, Data *  NodeData, bool *  NodeInserted )  [protected]

Parameters: Insert  determines whether or not to insert an unfound node. 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 or inserted Definition at line 251 of file RedBlackTree.h. References RedBlackTree< Data, ConfigData >::LeftRotate(), RedBlackNode< Data >::m_Color, AGenericTree< Data, ConfigData >::m_CompareNodes, AGenericTree< Data, ConfigData >::m_ConfigData, RedBlackNode< Data >::m_Data, RedBlackNode< Data >::m_Left, RedBlackNode< Data >::m_Right, RedBlackTree< Data, ConfigData >::m_Root, RedBlackNode< Data >::m_Up, and RedBlackTree< Data, ConfigData >::RightRotate(). Referenced by RedBlackTree< Data, ConfigData >::Delete(), RedBlackTree< Data, ConfigData >::Find(), and RedBlackTree< Data, ConfigData >::Search().

---

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

• RedBlackTree.h

---