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.

Go to the first, previous, next, last section, table of contents.