Skip site navigation (1)Skip section navigation (2)

FreeBSD Manual Pages


home | help
AVL(3)			   Library Functions Manual			AVL(3)

       mkavltree,  insertavl, lookupavl, deleteavl, avlwalk, avlnext, avlprev,
       endwalk - AVL tree routines

       #include	<u.h>
       #include	<libc.h>
       #include	<avl.h>
       typedef struct Avl Avl;
       struct Avl
	      Avl    *p;	   /* parent */
	      Avl    *n[2];	   /* children */
	      int    bal;	   /* balance bits */
       Avl    *avlnext(Avlwalk *walk);
       Avl    *avlprev(Avlwalk *walk);
       Avlwalk	     *avlwalk(Avltree *tree);
       void   deleteavl(Avltree	*tree, Avl *key, Avl **oldp);
       void   endwalk(Avlwalk *walk);
       void   insertavl(Avltree	*tree, Avl *new, Avl **oldp);
       Avl    *lookupavl(Avltree *tree,	Avl *key);
       Avl    *searchavl(Avltree *tree,	Avl *key, int neighbor);
       Avltree	     *mkavltree(int(*cmp)(Avl*,	Avl*));

       An AVL tree is a	self-balancing binary search tree.  These routines al-
       low creation and	maintenance of in-memory AVL trees.

       An  empty  AVL  tree  is	created	by calling mkavltree with a comparison
       function	as argument.  This function should take	two  pointers  to  Avl
       objects	and  return -1,	0 or 1 as the first is respectively less than,
       equal to, or greater than, the second.  Insertavl adds a	new tree  node
       into tree.  If oldp is non-nil upon return, it points to	storage	for an
       old node	with the same key that may now be  freed.   Lookupavl  returns
       the tree	node that matches key by tree's	comparison function, or	nil if

       Searchavl returns the tree node that matches key	by  tree's  comparison
       function,  if  it exists.  If it	does not, and neighbor is positive, it
       returns the nearest node	whose key is greater or	nil if there  is  none
       and,  if	neighbor is negative, it returns the nearest node whose	key is
       less or nil if there is none.  It is an error to	set neighbor to	values
       other than -1, 0, or +1.

       Deleteavl  removes  the node matching key from tree; oldp is handled as
       per insertavl.

       Avlwalk returns a pointer to a newly-allocated Avlwalk object.  Endwalk
       frees  such  an	object.	  Avlnext and avlprev walk the tree associated
       with walk, returning the	next (respectively, previous) tree node	in the
       comparison order	defined	by the comparison function associated with the
       tree associated with walk.

       Intended	usage seems to be to make an anonymous Avl the first member of
       the  application's  tree-node structure,	then pass these	routines tree-
       node pointers instead of	Avl*s.

	      typedef struct Node {
		     uchar  score[VtScoreSize];
		     int    type;
	      }	Node;
	      Avltree *tree;
	      Avl *res;
	      Node *np;
		     res = lookupavl(tree, np);


       G. M. Adelson-Velsky, E.	M. Landis, ``An	algorithm for the organization
       of information'', Soviet	Mathematics, Vol. 3, pp. 1256a1263.

       Functions returning pointers return nil on error.



Want to link to this manual page? Use this URL:

home | help