AVL Tree

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 <class Key>

bool exists(const Key&);

template <class 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 <class Key>

iterator find<RelationalOperation>(const Key&);

template <class Key, class Comparator>

iterator find<RelationalOperation>(const Key&, const Comparator&);

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, and specified as an explicit template parameter. For example, calling this method with operations::le is analogous to std::upper_bound.

You may specify an alternative comparator object, defining a weaker key ordering. That is, for each possible pair of keys, it should return either the same result as the comparator built in the tree, or "equal".

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

void clear();

Remove all elements.

template <class Key>

iterator insert(const Key& key);

template <class Key, class 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 <class Key>

iterator insert(const iterator& pos, const Key& key);

template <class Key, class Data>

iterator insert(const iterator& pos, const Key& key, const Data& data);

Create a new element and place it before the element pointed to by pos. In contrast to the STL implementation, the iterator pos 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 in debugging mode), so it should be used only if the correct insertion is asserted by the program context.

template <class Key>

void erase(const 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 <class Key>

void push_front(const Key& key);

template <class Key, class Data>

void push_front(const Key& key, const Data& data);

template <class Key>

void push_back(const Key& key);

template <class Key, class Data>

void push_back(const Key& key, const Data& data);

Shortcuts for insert() before the first / after the last tree element. The proper key ordering is not checked unless compiled in debugging mode.

void pop_front();

void pop_back();

Shortcuts for erase() of the first/last tree element.

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