This data structure features fast (O(log N))
insertion, removal, and retrieval of records,
provided that there is a sorting relation over
their keys and there are no entries with equal
keys. The AVL tree is an explicit binary searching
tree, where left children of each vertex are less
or equal, while right children are greater or
equal than the vertex itself. In addition, the
tree is balanced so that the difference between
the depths of the two subtrees of each vertex is
at most one.
