pm::AVL::tree< Traits > Class Template Reference

balanced binary search tree More...

List of all members.

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)
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

template<typename Traits>
class pm::AVL::tree< Traits >

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

template<typename Traits>

pm::AVL::tree< Traits >::tree

(

const tree< Traits > &

t

)

[inline]

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

---

Member Function Documentation

template<typename Traits>

Node* pm::AVL::tree< Traits >::insert_node

(

Node *

n

)

[inline]

Insert a given node in the tree corresponding to the value of its key field. The tree should not already contain a node with the equal key.

template<typename Traits>

template<typename Key_or_Iterator>

void pm::AVL::tree< Traits >::erase

(

const Key_or_Iterator &

k_or_it

)

[inline]

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

template<typename Traits>

Node* pm::AVL::tree< Traits >::remove_node

(

Node *

n

)

[inline]

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

Returns:

address of the removed node

template<typename Traits>

void pm::AVL::tree< Traits >::init

(

)

[inline]

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

---

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

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