Polymake Template Library (PTL) 4.12
|
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) | |
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:
std::less
, achieving the acceleration by 1.5 times in average for non-trivial key types.
|
inline |
Create a copy of another tree. The current form (list or tree) is also inherited.
|
inline |
Delete an element if it exists. Delete the element the iterator points to.
|
inline |
Makes the tree look like empty. Nodes are not destroyed.
|
inline |
Insert a given node in the tree corresponding to the value of its key field.
|
inline |
Remove the node with a given address. The Node object is not destroyed.
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.