pm::AVL::tree Class Reference

balanced binary search tree More...

Public Member Functions
bool	tree_form () const
	true if object is really a tree (and not a list)
Node *	insert_node (Node *n)
template<typename Key_or_Iterator >
void	erase (const Key_or_Iterator &k_or_it)
Node *	remove_node (Node *n)
void	update_node (Node *n)
Int	size () const
	Return the current number of nodes.
void	init ()
void	clear ()
	Make the tree empty, destroy the nodes.
	tree ()
	Creates an empty tree.
	tree (const tree &t)

Detailed Description

balanced binary search tree

An AVL tree is a kind of balanced binary search tree, allowing for logarithmic time element find, insert, and delete operations. AVL trees are thoroughly discussed in D.E. Knuth's The Art of Computer Programming, Vol. III, 6.2.3, pp 465ff; http://www-cs-staff.stanford.edu/~knuth/taocp.html

AVL trees play the same role in the polymake library that the red-black trees have in STL: a basis for the associative container classes. The current implementation differs from the red-black trees in following details:

• In the leaf nodes so called thread pointers to the lexicographically next and previous tree nodes are maintained. This reduces the amortized tree traversal time by approximately 50%.
• The key lookup procedure uses the comparator functor operations::cmp instead of std::less, achieving the acceleration by 1.5 times in average for non-trivial key types.
• A tree created from a preordered key sequence is kept as a double-linked list up to the first random access operation (key search). Since some container objects are accessed only in sequential traversal loops during all their lifetime, this eliminates the overhead of rebalancing the tree at its creation stage. The list-to-tree conversion takes linear time and don't involve rebalancing at all.

Constructor & Destructor Documentation

tree()

pm::AVL::tree::tree ( const tree &  t )

inline

Create a copy of another tree. The current form (list or tree) is also inherited.

Member Function Documentation

erase()

template<typename Key_or_Iterator >

void pm::AVL::tree::erase ( const Key_or_Iterator &  k_or_it )

inline

Delete an element if it exists. Delete the element the iterator points to.

init()

void pm::AVL::tree::init ( )

inline

Makes the tree look like empty. Nodes are not destroyed.

insert_node()

Node* pm::AVL::tree::insert_node ( Node *  n )

inline

Insert a given node in the tree corresponding to the value of its key field.

Returns

NULL if the key of the given node already occurs in the tree, //n// otherwise.

remove_node()

Node* pm::AVL::tree::remove_node ( Node *  n )

inline

Remove the node with a given address. The Node object is not destroyed.

Returns

address of the removed node

update_node()

void pm::AVL::tree::update_node

(

Node *

n

)

The key of the node has been changed: move it to the proper position. The new key must not violate the uniqueness requirement.

---

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

• lib/core/include/internal/AVL.h