#include <elm/avl/Tree.h>

Inheritance diagram for elm::avl::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 elm::inhstruct::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

virtual elm::avl::Tree::~Tree ( void )

virtual

Member Function Documentation

void elm::avl::Tree::clean ( void )

Remove all nodes from the tree.

References clean().

Referenced by clean().

int elm::avl::Tree::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 get().

bool elm::avl::Tree::contains ( Node * node )

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

Returns: True if the node is contained, false else.

int elm::avl::Tree::count ( void )

count the number of nodes in the tree.

Returns: Node count.

void elm::avl::Tree::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.

Tree::Node * elm::avl::Tree::get ( Node * node )

Get a tree node equal to the given one.

Parameters

node	Node to test for equality.

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

void elm::avl::Tree::insert ( Node * node )

Insert a new node in the tree.

Parameters

node	Node to insert.

References elm::inhstruct::BinTree::setRoot().

bool elm::avl::Tree::isEmpty ( void )

Test if the tree is empty.

Returns: True if the tree is empty, false else.

void elm::avl::Tree::remove ( Node * node )

Remove a node from the tree.

Parameters

node	Node to remove.

References elm::inhstruct::BinTree::setRoot().

void elm::avl::Tree::search ( Visitor * visitor )

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.

void elm::avl::Tree::visit ( Visitor * visitor )

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

Classes

Public Member Functions

Protected Member Functions

Detailed Description

Constructor & Destructor Documentation

Member Function Documentation