Either a functor class satisfying the extended requirements for binary operations, or an untyped template of such a class wrapped into BuildBinary or BuildBinaryIt (preferably expressed via the convenience typedef from namespace polymake::operations.
This assertion is checked only in the AVL_CHECKS compilation mode.
Either a functor class satisfying the extended requirements for unary operations, or an untyped template of such a class wrapped into BuildUnary or BuildUnaryIt (preferably expressed via the convenience typedef from namespace polymake::operations.

AVL tree is a kind of balanced binary search trees, 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.

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 detals:

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

### Element access

All top-level container classes based on AVL trees implement the Reversible Container STL interface. Besides this, following methods are defined:

template <typename Key> bool exists(const Key&); template <typename Key> iterator find(const Key&);
Look for an element with a given key. Return a boolean answer, or an iterator pointing to it or end() if not found.
Note that the type of the search key is not necessarily the same as of the tree elements. It suffices that both are comparable with each other.
template <typename Key, typename Comparator> iterator find(const Key&, const Comparator&);
Look for an element, using an alternative key comparator. For each possible pair of keys, the given comparator is required to obtain either the same result as the container's built-in comparator, or zero, signaling a 'fuzzy match'.
template <typename Key, typename RelationalOperation> iterator find_nearest(const Key&, const RelationalOperation& relop); template <typename Key, typename RelationalOperation, typename Comparator> iterator find_nearest(const Key&, const RelationalOperation& relop, const Comparator& cmp);
Find the element nearest to the given search key among those elements whose keys satisfy the relational operation. The latter should be chosen from operations::lt(), operations::le(), operations::gt(), and operations::gt().
The alternative comparator object allows to perform 'fuzzy search', as above.
Calling these methods with operations::le() or operations::ge() is equivalent to std::upper_bound or std::lower_bound correspondingly (but much more efficient).

Each find method has also a const analogon, returning a const_iterator.

void clear();
Remove all elements.
template <typename Key> iterator insert(const Key& key); template <typename Key, typename Data> iterator insert(const Key& key, const Data& data);
Find an element with the given key or create it at the right position. Store data in the associated data field of the tree element (applicable to Map, SparseVector, rows and columns of a SparseMatrix, and other associative containers.)
Return an iterator pointing to the found/created element.
template <typename Key> iterator insert(const iterator& where, const Key& key); template <typename Key, typename Data> iterator insert(const iterator& where, const Key& key, const Data& data);
Create a new element and place it before the element pointed to by where. In contrast to the STL implementation, the iterator where is not just a hint where to look up for an appropriate insertion position. Instead, this operation does not perform any key comparisons (unless compiled with debugging enabled), so it should be used only if the correct insertion is asserted by the program context.
template <typename Key> void erase(const Key& key);
Find an element with a given key and delete it, or do nothing if not found.
void erase(const iterator& pos);
Delete an element the iterator is pointing to. After this operation the iterator become invalid (it can't be dereferenced nor moved to the next/previous element), unless post-incremented or post-decremented within the method call expression.
template <typename Key> void push_front(const Key& key); template <typename Key, typename Data> void push_front(const Key& key, const Data data); template <typename Key> void push_back(const Key& key); template <typename Key, typename Data> void push_back(const Key& key, const Data& data);
Shortcuts for insert() before the first / after the last tree element. The key must be greater than all other keys in the tree.
void pop_front(); void pop_back();
Shortcuts for erase() of the first/last tree element.
template <typename Key> iterator toggle(const Key& key);
A combined insert-erase operation: If an element with the given key exists, delete it and return an end() iterator; otherwise create a new element with this key and return an iterator pointing to it.