2.5 The AVL Tree Data Type
The AVL tree data types provides a balanced binary tree. The tree will
remain balanced throughout its entire life time, regardless of in which
order elements are entered into or deleted from the tree.
Although an AVL tree is not perfectly balanced, it has almost the
same performance as if it was. The definition of an AVL tree is that
the difference in depth of the two branches of a particular node is at
most 1. This criterium is enough to make the performance of searching
in an AVL tree very close to a perfectly balanced tree, but will
simplify the entering and deleting of data significantly.
All data that is entered into an AVL tree should be of the same type.
If they are not, there are no way to compare two elements and this is
essential for entering and deleting data from the tree. When a tree is
created, a compare function is given to the create function. This
function is used throughout the life of the tree in all subsequent
insertions and deletions.
To use the Elib AVL tree, you must put the line
in your elisp source file.
The following functions are provided by the AVL tree in the library:
Create a new empty AVL tree. The argument COMPARE-FUNCTION is a
function which compares two instances of the data type which is to
be entered into the tree. The call `(compare-function data1
data2)' should return non-`nil' if `data1' is less than `data2',
and `nil' otherwise.
Return `t' if TREE is an avltree, otherwise return `nil'.
Return `compare-function' given to `avltree-create' when TREE was
Return `t' if TREE is empty, otherwise return `nil'.
`(avltree-enter tree data)'
Enter DATA into TREE. If there already is a data element which is
considered equal to DATA by `compare-function' given to
`avltree-create', the new element will replace the old one in the
`(avltree-delete tree data)'
Delete the element which is considered equal to DATA by
`compare-function' given to `avltree-create'. If there is no
matching element within the tree, nothing is done to the tree.
`(avltree-member tree data)'
Return the element in TREE which is considered equal to DATA by
`compare-function' given to `avltree-create'. If there is no such
element in the tree, return `nil'.
`(avltree-map map-function tree)'
Apply MAP-FUNCTION to all elements in TREE. The function is
applied in the order in which the tree is sorted.
Return the first element of TREE, i.e. the one who is considered
first by `compare-function' given to `avltree-create'. If the
tree is empty, return `nil'.
Return the last element of TREE, i.e. the one who is considered
last by `compare-function' given to `avltree-create'. If the tree
is empty, return `nil'.
Return a copy of TREE.
Return a sorted list containing all elements of TREE.
Return the number of elements in TREE.
Clear TREE, i.e. make it totally empty.
automatically generated by info2www version 220.127.116.11