| TerraLib 4.1

- Main Page
- Related Pages
- Modules
- Namespaces
- Classes
- Files
- Examples

- Class List
- Class Index
- Class Hierarchy
- Class Members

Classes | Public Types | Public Member Functions | Protected Member Functions | Protected Attributes
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

All Classes Namespaces Files Functions Variables Typedefs Enumerations Enumerator Friends Defines