Polymake Template Library (PTL) 4.12
Public Member Functions | List of all members
pm::AVL::tree< Traits > Class Template Reference

balanced binary search tree More...

#include <AVL.h>

Inherits Traits.

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

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:

Constructor & Destructor Documentation

◆ tree()

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

◆ erase()

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.

◆ init()

template<typename Traits >
void pm::AVL::tree< Traits >::init ( )
inline

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

◆ insert_node()

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.

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

◆ remove_node()

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

◆ update_node()

template<typename Traits >
void pm::AVL::tree< Traits >::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: