Tree Class Reference

#include <elm/avl/Tree.h>

Inheritance diagram for Tree:

Classes
class	Node

Public Member Functions
virtual	~Tree (void)
bool	isEmpty (void)
int	count (void)
Node *	get (Node *node)
bool	contains (Node *node)
void	visit (Visitor *visitor)
void	search (Visitor *visitor)
void	insert (Node *node)
void	remove (Node *node)
void	clean (void)
Public Member Functions inherited from BinTree
	BinTree (void)
bool	isEmpty (void) const
bool	contains (Node *node)
int	count (void) const
Node *	root (void) const
void	setRoot (Node *node)
void	visit (Visitor *visitor) const
void	visitPreOrder (Visitor *visitor) const
void	visitPostOrder (Visitor *visitor) const
void	search (Visitor *visitor) const
void	clear (void)

Protected Member Functions
virtual int	compare (Node *node1, Node *node2)=0
virtual void	free (Node *node)

Detailed Description

Implementation of the Adelson-Velskii and Landis (AVL) tree algorithm. In order to use this class, you must make a class inheriting this class and overload the compare() protected method. Nodes inserted in the tree must also inherit from the AVLTree::AVLNode class.

Performances:

• lookup: O(Log n)
• add: O(Log n)
• removal: O(Log n)

Constructor & Destructor Documentation

~Tree()

virtual ~Tree ( void  )

virtual

Member Function Documentation

clean()

void clean ( void  )

inline

Remove all nodes from the tree.

References Tree::clean().

Referenced by Tree::clean().

compare()

int compare ( Node *  node1, Node *  node2  )

protectedpure virtual

This method is called for comparing nodes. It must be overloaded for getting an actual implementation of AVL tree.

Parameters

node1	First node to compare.
node2	Second node to compare.

Returns

0 for equality, <0 if node1 < node2, >0 else.

Referenced by Tree::get().

contains()

bool contains ( Node *  node )

inline

Test if the given node value is contained in the tree.

Returns

True if the node is contained, false else.

References Tree::get().

count()

int count ( void  )

inline

count the number of nodes in the tree.

Returns

Node count.

References elm::count().

free()

void free ( Node *  node )

protectedvirtual

Dump the content of tree. For debugging purpose, only. This method is called for freeing a node in the tree. This method may be overloaded for providing special freeing method. Not overloaded, do nothing.

Parameters

node	Node to free.

get()

Tree::Node * get

(

Node *

node

)

Get a tree node equal to the given one.

Parameters

node	Node to test for equality.

References Tree::Node::_left(), Tree::Node::_right(), and Tree::compare().

Referenced by Tree::contains().

insert()

void insert

(

Node *

node

)

Insert a new node in the tree.

Parameters

node	Node to insert.

References BinTree::setRoot().

isEmpty()

bool isEmpty ( void  )

inline

Test if the tree is empty.

Returns

True if the tree is empty, false else.

remove()

void remove

(

Node *

node

)

Remove a node from the tree.

Parameters

node	Node to remove.

References BinTree::setRoot().

search()

void search ( Visitor *  visitor )

inline

Look for a special node in the given tree.For each node, the process() method of the visitor is called. If it returns 0, search stops. If it returns, <0 traversal continue with left child else with the right child.

Parameters

visitor

Visitor to use.

visit()

void visit ( Visitor *  visitor )

inline

Visit the node of the tree.

Parameters

visitor

The method process() of this object is called with each tree node.

---

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

• include/elm/avl/Tree.h
• src/avl_Tree.cpp