(elib.info)Binary tree

---

Next: AVL tree Prev: Doubly Linked List Up: Container data types

---

Enter node , (file) or (file)node

2.4 The Binary Tree Data Type
=============================

The binary tree is sometimes an efficient way to store data.  When a
binary tree is created a compare function is given to the create
function (`bintree-create').  This function is used throughout all data
entry and deletions into and out of the tree.

   To use the binary tree in Elib you must put the line

     (require 'bintree)

   in your elisp source file.

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

`(bintree-create compare-function)'
     Create a new empty binary 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.

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

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

`(bintree-empty tree)'
     Return `t' if TREE is empty, otherwise return `nil'.

`(bintree-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
     `bintree-create', the new element will replace the old one in the
     tree.

`(bintree-delete tree data)'
     Delete the element which is considered equal to DATA by
     `compare-function' given to `bintree-create'.  If there is no
     matching element within the tree, nothing is done to the tree.

`(bintree-member tree data)'
     Return the element in TREE which is considered equal to DATA by
     `compare-function' given to `bintree-create'.  If there is no such
     element in the tree, return `nil'.

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

`(bintree-first tree)'
     Return the first element of TREE, i.e. the one who is considered
     first by `compare-function' given to `bintree-create'.  If the
     tree is empty, return `nil'.

`(bintree-last tree)'
     Return the last element of TREE, i.e. the one who is considered
     last by `compare-function' given to `bintree-create'.  If the tree
     is empty, return `nil'.

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

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

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

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