TeREDBLACK::TeRBTree< NODE > Class Template Reference

Template class for Red-Black trees. More...

#include <TeRedBlackTree.h>

List of all members.

Classes
class	internal_iterator
	Iterators class for the tree. It is used to abstract walking on the tree. More...
Public Types
typedef NODE *	REDBLACKNODEPOINTER
	Export node type.
typedef NODE::TeRedBlackNodeData	TeRedBlackNodeData
	Export node data type.
typedef internal_iterator< NODE >	iterator
	Exports iterator type.
Public Member Functions
	TeRBTree ()
	Constructor.
virtual	~TeRBTree ()
	Destructor.
bool	IsEmpty (void) const
	Returns true if the tree is empty otherwise returns false.
unsigned int	Size (void) const
	Returns the number of nodes in the tree, excluding the nil_ one.
virtual void	Delete (NODE *z)
	Removes the node from the tree and do rebalancing.
virtual NODE *	Successor (NODE *x) const
	Returns the sucessor of a given node or zero if not.
virtual NODE *	Predecessor (NODE *x) const
	Returns the predecessor of a given node or zero if not.
NODE *	First (void) const
	Returns the leftmost node in the tree, or zero if not.
NODE *	Last (void) const
	Returns the rightmost node in the tree, or zero if not.
virtual bool	GetFirst (TeRedBlackNodeData &d)
	Return the first element in the tree and removes it.
void	Clear (void)
	Removes all nodes from the tree (excepty the nil node). Clear memory.
virtual void	WriteToFile (const string &fileName) const
	Write the node's data to a file. The data must implement a methos called: void ToString(void).
iterator	begin (void)
	Returns an iterator to the leftmost node of the tree.
iterator	end (void)
	Returns a reference iterator indicating the end of a tree.
void	erase (iterator &it)
	Erases a node pointed by an interator.
Protected Member Functions
virtual void	LeftRotate (NODE *x, NODE *&root)
	Left rotation.
virtual void	RightRotate (NODE *y, NODE *&root)
	Right rotation.
void	InsertFixUp (NODE *&n, NODE *&root)
	Must be called after an insert, to fix-up the tree.
void	DeleteFixUp (NODE *x, NODE *x_parent, NODE *&root)
	Must be called after a deletion, to fix-up the tree.
virtual void	WriteToFile (NODE *n, string &strRepres) const
	Only to be used by the public method, walking on the tree.
void	Erase (NODE *n)
	Removes the node and all node below it and doesn't do rebalancing. Used to free the memory.
Protected Attributes
NODE *	nil_
	Reference node.
NODE *	root_
	Tree's root.
unsigned int	nodeCount_
	Count the number of nodes in the tree (excluding nil_ node).

---

Detailed Description

template<class NODE>
class TeREDBLACK::TeRBTree< NODE >

Template class for Red-Black trees.

This class contains the common operations in a Red-Black Tree. It can be used like a framework. Extend the methods like "Insert" and "Search" to walk and to do some usefull things. You will use the methods for Rotation, Insert Propagation, Delete Propagation, Sucessor, Predecessor, IsEmpty, Clear. This tree is based on the algorithm of Cormen's book. The only difference is when a node being deleted has two children its successor node is relinked into its place, rather than copied, so that the only iterators invalidated are those referring to the deleted node. Every data used in nodes must implements a ToString() method.

---

Member Typedef Documentation

template<class NODE>

typedef internal_iterator<NODE> TeREDBLACK::TeRBTree< NODE >::iterator

Exports iterator type.

template<class NODE>

typedef NODE* TeREDBLACK::TeRBTree< NODE >::REDBLACKNODEPOINTER

Export node type.

template<class NODE>

typedef NODE::TeRedBlackNodeData TeREDBLACK::TeRBTree< NODE >::TeRedBlackNodeData

Export node data type.

---

Constructor & Destructor Documentation

template<class NODE>

TeREDBLACK::TeRBTree< NODE >::TeRBTree

(

)

[inline]

Constructor.

template<class NODE>

virtual TeREDBLACK::TeRBTree< NODE >::~TeRBTree

(

)

[inline, virtual]

Destructor.

---

Member Function Documentation

template<class NODE>

iterator TeREDBLACK::TeRBTree< NODE >::begin

(

void

)

[inline]

Returns an iterator to the leftmost node of the tree.

template<class NODE>

void TeREDBLACK::TeRBTree< NODE >::Clear

(

void

)

[inline]

Removes all nodes from the tree (excepty the nil node). Clear memory.

template<class NODE>

virtual void TeREDBLACK::TeRBTree< NODE >::Delete

(

NODE *

z

)

[inline, virtual]

Removes the node from the tree and do rebalancing.

template<class NODE>

void TeREDBLACK::TeRBTree< NODE >::DeleteFixUp	(	NODE *	x,
		NODE *	x_parent,
		NODE *&	root
	)		[inline, protected]

Must be called after a deletion, to fix-up the tree.

template<class NODE>

iterator TeREDBLACK::TeRBTree< NODE >::end

(

void

)

[inline]

Returns a reference iterator indicating the end of a tree.

template<class NODE>

void TeREDBLACK::TeRBTree< NODE >::Erase

(

NODE *

n

)

[inline, protected]

Removes the node and all node below it and doesn't do rebalancing. Used to free the memory.

template<class NODE>

void TeREDBLACK::TeRBTree< NODE >::erase

(

iterator &

it

)

[inline]

Erases a node pointed by an interator.

template<class NODE>

NODE* TeREDBLACK::TeRBTree< NODE >::First

(

void

)

const [inline]

Returns the leftmost node in the tree, or zero if not.

template<class NODE>

virtual bool TeREDBLACK::TeRBTree< NODE >::GetFirst

(

TeRedBlackNodeData &

d

)

[inline, virtual]

Return the first element in the tree and removes it.

template<class NODE>

void TeREDBLACK::TeRBTree< NODE >::InsertFixUp	(	NODE *&	n,
		NODE *&	root
	)		[inline, protected]

Must be called after an insert, to fix-up the tree.

template<class NODE>

bool TeREDBLACK::TeRBTree< NODE >::IsEmpty

(

void

)

const [inline]

Returns true if the tree is empty otherwise returns false.

template<class NODE>

NODE* TeREDBLACK::TeRBTree< NODE >::Last

(

void

)

const [inline]

Returns the rightmost node in the tree, or zero if not.

template<class NODE>

virtual void TeREDBLACK::TeRBTree< NODE >::LeftRotate	(	NODE *	x,
		NODE *&	root
	)		[inline, protected, virtual]

Left rotation.

template<class NODE>

virtual NODE* TeREDBLACK::TeRBTree< NODE >::Predecessor

(

NODE *

x

)

const [inline, virtual]

Returns the predecessor of a given node or zero if not.

template<class NODE>

virtual void TeREDBLACK::TeRBTree< NODE >::RightRotate	(	NODE *	y,
		NODE *&	root
	)		[inline, protected, virtual]

Right rotation.

template<class NODE>

unsigned int TeREDBLACK::TeRBTree< NODE >::Size

(

void

)

const [inline]

Returns the number of nodes in the tree, excluding the nil_ one.

template<class NODE>

virtual NODE* TeREDBLACK::TeRBTree< NODE >::Successor

(

NODE *

x

)

const [inline, virtual]

Returns the sucessor of a given node or zero if not.

template<class NODE>

virtual void TeREDBLACK::TeRBTree< NODE >::WriteToFile

(

const string &

fileName

)

const [inline, virtual]

Write the node's data to a file. The data must implement a methos called: void ToString(void).

template<class NODE>

virtual void TeREDBLACK::TeRBTree< NODE >::WriteToFile	(	NODE *	n,
		string &	strRepres
	)		const [inline, protected, virtual]

Only to be used by the public method, walking on the tree.

---

Member Data Documentation

template<class NODE>

NODE* TeREDBLACK::TeRBTree< NODE >::nil_ [protected]

Reference node.

template<class NODE>

unsigned int TeREDBLACK::TeRBTree< NODE >::nodeCount_ [protected]

Count the number of nodes in the tree (excluding nil_ node).

template<class NODE>

NODE* TeREDBLACK::TeRBTree< NODE >::root_ [protected]

Tree's root.

---

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

• E:/Projetos_Primeiro_Semestre_2012/TerraView/terralib/src/terralib/kernel/TeRedBlackTree.h