Generic abstract class to manage a AVL tree. AVL tree is a self balancing data structure that keeps a binary tree almost balanced. It has the restriction that all nodes have children with, at most, one level of difference between them. This constraint is stronger than those of the red-black trees and, as such, the cost for balance maintenance is higher. It has O(log n) complexity for searches, insertions and deletions. The delete operator has a constant multiplier higher than insertions. The height of an AVL tree is strictly less than 1.44 log(n + 2) - 0.328. It is more rigidly balanced than red-black trees leading to slower insertion and removals but slightly faster searches. The nodes in this tree must be comparable. As such, a class specialization must provide gcgAVLTREE::compare() method that has the function of determining if two gcgORDEREDNODE nodes are equal, greater or smaller. Use the gcgAVLTREE::getIterator() to obtain a fast iterator to traverse the AVL nodes in ascending or descending order. More...

#include <gcg.h>

Inheritance diagram for gcgAVLTREE:

Public Member Functions
	gcgAVLTREE ()
	Constructs a valid and empty AVL tree. More...

virtual	~gcgAVLTREE ()
	Destroys the AVL tree, releasing all nodes. All entries are deleted. More...

gcgORDEREDNODE *	insert (gcgORDEREDNODE *newnode)
	Inserts a new entry newnode in the AVL tree. The tree is adjusted to keep the restriction that both children of all nodes must have heights differing of at most one level. Insertions take O(log n) operations to be finished. At most one tree rotation is performed. All nodes in the tree must be unique, i.e., they are mutually different in respect to gcgORDEREDNODE::compare() method. More...

gcgORDEREDNODE *	search (gcgORDEREDNODE *key)
	Retrieves the entry of the AVL tree that is similar to the key in respect to the gcgAVLTREE::compare() method. The gcgAVLTREE::compare() method must return zero only for an unique node of the tree. AVL searchs take O(log n) operations to be finished and are slighly more efficient than in red-black trees. More...

gcgORDEREDNODE *	remove (gcgORDEREDNODE *key)
	Removes the entry of the AVL tree that is similar to the key in respect to the gcgAVLTREE::compare() method. The gcgAVLTREE::compare() method must return zero only for an unique node of the tree. The tree is adjusted to keep the restriction that both children of all nodes must have heights differing of at most one level. Removals take O(log n) operations to be finished. More than one tree rotation can be performed, which means that this operation has generally a greater time cost in comparison with insertion and search operations. More...

uintptr_t	getCounter ()
	Returns the number of elements stored in the AVL tree. More...

virtual bool	deleteAll ()
	Deletes and removes all entries from the AVL tree. All AVL tree resources are also released. More...

gcgITERATOR *	getIterator (int traversemode=0)
	Returns an iterator for traversing the elements of the AVL tree. The traversal order is defined by the parameter traversemode. Currently, the tree nodes can be traversed in two ways: traversemode = 0, to iterate in ascending order (default); and traversemode = 1, to iterate in descending order. The AVL tree must not be changed by insertions, removals or moves while the iterator is being used. You must delete the returned iterator after use. The iterator copies a minimal information from the AVL tree. Note that deleting a iterator does not affect the nodes. More...

gcgITERATOR *	detach (int traversemode=0)
	Force the AVL tree to be empty. It has the same effect as removing all entries from the AVL tree but keeping their chaining (which will used by the returned iterator). The entries are NOT deleted. In order to retrieve the detached entries, a gcgITERATOR is returned. This is useful to process the nodes freely and without the possible restrictions of the underlying AVL tree. Thus, the gcgITERATOR returned by gcgAVLTREE::detach() MUST be used to delete all the entries or reinsert them in another data structure. The traversal order of the returned iterator is defined by the parameter traversemode. Currently, the tree nodes can be traversed in two ways: traversemode = 0, to iterate in ascending order (default); and traversemode = 1, to iterate in descending order. All resources currently used by the AVL tree are released (becomes empty) but it can be reused normally. You must delete the gcgITERATOR after its use. More...

virtual int	compare (gcgORDEREDNODE refnode1, gcgORDEREDNODE refnode2)=0
	Method that must be furnished by a specialization of gcgAVLTREE and is responsible for comparing two gcgORDEREDNODE nodes. This is necessary for all tree operations of insertion, retrieval and removal. It must compare the two nodes pointed by refnode1 and refnode2 and return zero if they are equal, -1 if refnode1 is smaller or precedes refnode2, or 1 if refnode1 is grater or succeeds refnode2. More...

Public Member Functions inherited from gcgCLASS
void *	operator new (size_t size)
	Defines a new operator to be used by instatiations of GCGlib classes instead the global one. More...

void *	operator new (size_t size, const std::nothrow_t &) throw ()
	Defines a new operator to be used by instantiations of GCGlib classes instead the global one. Returns a NULL pointer instead of throwing an exception if an error occurs. More...

void *	operator new[] (size_t size)
	Defines a new operator to be used by GCGlib array allocations instead the global one. More...

void *	operator new[] (size_t size, const std::nothrow_t &) throw ()
	Defines a new operator to be used by vector allocations instead the global one. More...

void	operator delete (void *p)
	Defines a delete operator to free instances of GCGlib classes instead the global one. It is designed to match the new operator. More...

void	operator delete (void *p, const std::nothrow_t &) throw ()
	Defines a delete operator to free instances of GCGlib classes instead the global one. It is designed to match the new operator. More...

void	operator delete[] (void *p)
	Defines a delete operator to free instances of arrays for GCGlib classes instead the global one. It is designed to match the new[] operator. More...

void	operator delete[] (void *p, const std::nothrow_t &) throw ()
	Defines a delete operator to free instances of arrays for GCGlib classes instead the global one. It is designed to match the new[] operator. More...

Public Attributes
gcgORDEREDNODE *	root
	Root node of the AVL tree. Read-only.

uintptr_t	counter
	Number of elements in this tree. Read-only.

Detailed Description

Generic abstract class to manage a AVL tree. AVL tree is a self balancing data structure that keeps a binary tree almost balanced. It has the restriction that all nodes have children with, at most, one level of difference between them. This constraint is stronger than those of the red-black trees and, as such, the cost for balance maintenance is higher. It has O(log n) complexity for searches, insertions and deletions. The delete operator has a constant multiplier higher than insertions. The height of an AVL tree is strictly less than 1.44 log(n + 2) - 0.328. It is more rigidly balanced than red-black trees leading to slower insertion and removals but slightly faster searches. The nodes in this tree must be comparable. As such, a class specialization must provide gcgAVLTREE::compare() method that has the function of determining if two gcgORDEREDNODE nodes are equal, greater or smaller. Use the gcgAVLTREE::getIterator() to obtain a fast iterator to traverse the AVL nodes in ascending or descending order.

Since: 0.04.179

Constructor & Destructor Documentation

◆ gcgAVLTREE()

gcgAVLTREE::gcgAVLTREE ( )

Constructs a valid and empty AVL tree.

See also: ~gcgAVLTREE

◆ ~gcgAVLTREE()

virtual gcgAVLTREE::~gcgAVLTREE ( )

virtual

Destroys the AVL tree, releasing all nodes. All entries are deleted.

See also: gcgAVLTREE

Member Function Documentation

◆ compare()

virtual int gcgAVLTREE::compare	(	gcgORDEREDNODE *	refnode1,
		gcgORDEREDNODE *	refnode2
	)

pure virtual

Method that must be furnished by a specialization of gcgAVLTREE and is responsible for comparing two gcgORDEREDNODE nodes. This is necessary for all tree operations of insertion, retrieval and removal. It must compare the two nodes pointed by refnode1 and refnode2 and return zero if they are equal, -1 if refnode1 is smaller or precedes refnode2, or 1 if refnode1 is grater or succeeds refnode2.

Parameters

[in]	refnode1	pointer to a gcgORDEREDNODE, generally specialized, object that must be compared with refnode2.
[in]	refnode2	pointer to a gcgORDEREDNODE, generally specialized, object that must be compared with refnode1.

Returns: It must compare the two nodes pointed by refnode1 and refnode2 and return zero if they are equal, a negative integer if refnode1 is smaller or precedes refnode2, or a positive integer if refnode1 is grater or succeeds refnode2.

See also: insert(); remove(); search()

◆ deleteAll()

virtual bool gcgAVLTREE::deleteAll ( )

virtual

Deletes and removes all entries from the AVL tree. All AVL tree resources are also released.

Returns: Returns true if all entries were deleted and removed. If it returns false, check GCG_REPORT_MESSAGE(gcgGetReport()) for knowing the problem.

See also: detach()

Implements gcgDATASTRUCTURE.

◆ detach()

gcgITERATOR* gcgAVLTREE::detach ( int traversemode = 0 )

virtual

Force the AVL tree to be empty. It has the same effect as removing all entries from the AVL tree but keeping their chaining (which will used by the returned iterator). The entries are NOT deleted. In order to retrieve the detached entries, a gcgITERATOR is returned. This is useful to process the nodes freely and without the possible restrictions of the underlying AVL tree. Thus, the gcgITERATOR returned by gcgAVLTREE::detach() MUST be used to delete all the entries or reinsert them in another data structure. The traversal order of the returned iterator is defined by the parameter traversemode. Currently, the tree nodes can be traversed in two ways: traversemode = 0, to iterate in ascending order (default); and traversemode = 1, to iterate in descending order. All resources currently used by the AVL tree are released (becomes empty) but it can be reused normally. You must delete the gcgITERATOR after its use.

Parameters

traversemode Specifies the order that the available elements in the AVL tree must be traversed by the returned iterator. Currently, the tree nodes can be traversed in two ways: traversemode = 0, to iterate in ascending order (default); and traversemode = 1, to iterate in descending order.

Returns: Returns an iterator for traversing the elements that were detached from the AVL tree. The AVL tree becomes empty and can be reused. You MUST delete the returned gcgITERATOR object after use. If it returns NULL, check GCG_REPORT_MESSAGE(gcgGetReport()) for knowing the problem.

See also: deleteAll(); getIterator()

Implements gcgDATASTRUCTURE.

◆ getCounter()

uintptr_t gcgAVLTREE::getCounter ( )

virtual

Returns the number of elements stored in the AVL tree.

Returns: Returns the number of elements currently stored in the AVL tree.

See also: insert(); remove()

Implements gcgDATASTRUCTURE.

◆ getIterator()

gcgITERATOR* gcgAVLTREE::getIterator ( int traversemode = 0 )

virtual

Returns an iterator for traversing the elements of the AVL tree. The traversal order is defined by the parameter traversemode. Currently, the tree nodes can be traversed in two ways: traversemode = 0, to iterate in ascending order (default); and traversemode = 1, to iterate in descending order. The AVL tree must not be changed by insertions, removals or moves while the iterator is being used. You must delete the returned iterator after use. The iterator copies a minimal information from the AVL tree. Note that deleting a iterator does not affect the nodes.

Parameters

traversemode Specifies the order that the available elements in the AVL tree must be traversed. Currently, the tree nodes can be traversed in two ways: traversemode = 0, to iterate in ascending order (default); and traversemode = 1, to iterate in descending order.

Returns: Returns an iterator for traversing the tree in the order specified by traversemode. The AVL tree must not be changed by insertions, removals or moves while the iterator is being used. You MUST delete the returned gcgITERATOR object after use. If it returns NULL, check GCG_REPORT_MESSAGE(gcgGetReport()) for knowing the problem.

See also: detach()

Implements gcgDATASTRUCTURE.

◆ insert()

gcgORDEREDNODE* gcgAVLTREE::insert ( gcgORDEREDNODE * newnode )

Inserts a new entry newnode in the AVL tree. The tree is adjusted to keep the restriction that both children of all nodes must have heights differing of at most one level. Insertions take O(log n) operations to be finished. At most one tree rotation is performed. All nodes in the tree must be unique, i.e., they are mutually different in respect to gcgORDEREDNODE::compare() method.

Parameters

[in] newnode a pointer to a comparable node (gcgORDEREDNODE) to be inserted in the AVL tree. It is generally an object of a specialization of gcgORDEREDNODE that carries the node information. If a similar node is already in the tree (the gcgAVLTREE::compare() method returns zero for an existing node), it returns the pointer of the node in the tree. The insertion operation might call the gcgAVLTREE::compare() method several times to correctly position the new node.

Returns: if newnode is similar to an existing node of the tree (the gcgAVLTREE::compare() method returns zero for an existing node), the method returns the pointer of that node. If newnode is correctly inserted, it returns the pointer newnode. If it returns NULL, check GCG_REPORT_MESSAGE(gcgGetReport()) for knowing the problem.

See also: compare(); remove(); search()

◆ remove()

gcgORDEREDNODE* gcgAVLTREE::remove ( gcgORDEREDNODE * key )

Removes the entry of the AVL tree that is similar to the key in respect to the gcgAVLTREE::compare() method. The gcgAVLTREE::compare() method must return zero only for an unique node of the tree. The tree is adjusted to keep the restriction that both children of all nodes must have heights differing of at most one level. Removals take O(log n) operations to be finished. More than one tree rotation can be performed, which means that this operation has generally a greater time cost in comparison with insertion and search operations.

Parameters

[in] key a pointer to a comparable node (gcgORDEREDNODE) that carries the information to be found and removed from the AVL tree. It is generally an object of a specialization of gcgORDEREDNODE that carries the information to be removed. If a similar node is in the tree (the gcgAVLTREE::compare() method returns zero for an existing node), that node is removed from the AVL tree and returned. The removed node is NOT deleted. The remove operation might call the gcgAVLTREE::compare() method several times to find the node before its removal.

Returns: if newnode is similar to an existing node of the tree (the gcgAVLTREE::compare() method returns zero for an existing node), the method removes that node from the AVL tree and returns its pointer. The node is NOT deleted by the method. If a similar node was not found or an error occurred, it returns NULL. Check GCG_REPORT_MESSAGE(gcgGetReport()) for knowing the problem.

See also: insert(); search(); compare()

◆ search()

gcgORDEREDNODE* gcgAVLTREE::search ( gcgORDEREDNODE * key )

Retrieves the entry of the AVL tree that is similar to the key in respect to the gcgAVLTREE::compare() method. The gcgAVLTREE::compare() method must return zero only for an unique node of the tree. AVL searchs take O(log n) operations to be finished and are slighly more efficient than in red-black trees.

Parameters

[in] key a pointer to a comparable node (gcgORDEREDNODE) that carries the information to be searched in the AVL tree. It is generally an object of a specialization of gcgORDEREDNODE that carries the requested information. If a similar node is in the tree (the gcgAVLTREE::compare() method returns zero for an existing node), it returns the pointer of that node. The search operation might call the gcgAVLTREE::compare() method several times to retrieve the node.

Returns: if key is similar to an existing node of the tree (the gcgAVLTREE::compare() method returns zero for an existing node), the method returns the pointer of that node. If a similar node was not found or an error occurred, it returns NULL. Check GCG_REPORT_MESSAGE(gcgGetReport()) for knowing the problem, if any.

See also: insert(); remove(); compare()

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

M:/Documentos/Projetos/Projetos/GCGlib/src/gcg.h

Public Member Functions

Public Attributes

Detailed Description

Constructor & Destructor Documentation

◆ gcgAVLTREE()

◆ ~gcgAVLTREE()

Member Function Documentation

◆ compare()

◆ deleteAll()

◆ detach()

◆ getCounter()

◆ getIterator()

◆ insert()

◆ remove()

◆ search()