avl man page on Plan9

Man page or keyword search:  
man Server   549 pages
apropos Keyword Search (all sections)
Output format
Plan9 logo
[printable version]

AVL(2)									AVL(2)

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

SYNOPSIS
       #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*));

DESCRIPTION
       An AVL tree is a self-balancing binary  search  tree.   These  routines
       allow 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
       none.

       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.

EXAMPLES
       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 {
		     Avl;
		     uchar  score[VtScoreSize];
		     int    type;
	      } Node;
	      Avltree *tree;
	      Avl *res;
	      Node *np;
	      ...
		     res = lookupavl(tree, np);

SOURCE
       /sys/src/libavl

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

DIAGNOSTICS
       Functions returning pointers return nil on error.

									AVL(2)
[top]
                             _         _         _ 
                            | |       | |       | |     
                            | |       | |       | |     
                         __ | | __ __ | | __ __ | | __  
                         \ \| |/ / \ \| |/ / \ \| |/ /  
                          \ \ / /   \ \ / /   \ \ / /   
                           \   /     \   /     \   /    
                            \_/       \_/       \_/ 
More information is available in HTML format for server Plan9

List of man pages available for Plan9

Copyright (c) for man pages and the logo by the respective OS vendor.

For those who want to learn more, the polarhome community provides shell access and support.

[legal] [privacy] [GNU] [policy] [cookies] [netiquette] [sponsors] [FAQ]
Tweet
Polarhome, production since 1999.
Member of Polarhome portal.
Based on Fawad Halim's script.
....................................................................
Vote for polarhome
Free Shell Accounts :: the biggest list on the net