(elib.info)AVL tree

---

Prev: Binary tree Up: Container data types

---

Enter node , (file) or (file)node

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

     (require 'avltree)

   in your elisp source file.

   The following functions are provided by the AVL tree in the library:

`(avltree-create compare-function)'
     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.

`(avltree-p tree)'
     Return `t' if TREE is an avltree, otherwise return `nil'.

`(avltree-compare-function tree)'
     Return `compare-function' given to `avltree-create' when TREE was
     created.

`(avltree-empty tree)'
     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
     tree.

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

`(avltree-first tree)'
     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'.

`(avltree-last tree)'
     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'.

`(avltree-copy tree)'
     Return a copy of TREE.

`(avltree-flatten tree)'
     Return a sorted list containing all elements of TREE.

`(avltree-size tree)'
     Return the number of elements in TREE.

`(avltree-clear tree)'
     Clear TREE, i.e. make it totally empty.