| .TH AVL 3 |
| .SH NAME |
| mkavltree, insertavl, lookupavl, deleteavl, avlwalk, avlnext, avlprev, endwalk - AVL tree routines |
| .SH SYNOPSIS |
| .\" .ta 0.75i 1.5i 2.25i 3i 3.75i 4.5i |
| .ta 0.7i +0.7i +0.7i +0.7i +0.7i +0.7i +0.7i |
| .EX |
| #include <u.h> |
| #include <libc.h> |
| #include <avl.h> |
| .sp 0.3v |
| typedef struct Avl Avl; |
| struct Avl |
| { |
| Avl *p; /* parent */ |
| Avl *n[2]; /* children */ |
| int bal; /* balance bits */ |
| }; |
| .sp 0.3v |
| 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*)); |
| .EE |
| .SH DESCRIPTION |
| An AVL tree is a self-balancing binary search tree. |
| These routines allow creation and maintenance of in-memory AVL trees. |
| .PP |
| An empty AVL tree is created by calling |
| .I mkavltree |
| with a comparison function as argument. |
| This function should take two pointers to |
| .B Avl |
| objects and return -1, 0 or 1 as the first is |
| respectively less than, |
| equal to, or greater than, |
| the second. |
| .I Insertavl |
| adds a |
| .I new |
| tree node into |
| .IR tree . |
| If |
| .I oldp |
| is non-nil upon return, |
| it points to storage for an old node |
| with the same key that may now be freed. |
| .I Lookupavl |
| returns the |
| .I tree |
| node that matches |
| .I key |
| by |
| .IR tree 's |
| comparison function, |
| or |
| .B nil |
| if none. |
| .PP |
| .I Searchavl |
| returns the |
| .I tree |
| node that matches |
| .I key |
| by |
| .IR tree 's |
| comparison function, if it exists. |
| If it does not, and |
| .I neighbor |
| is positive, it returns the nearest node whose |
| .I key |
| is greater or |
| .B nil |
| if there is none and, if |
| .I neighbor |
| is negative, it returns the nearest node whose |
| .I key |
| is less or |
| .B nil |
| if there is none. |
| It is an error to set |
| .I neighbor |
| to values other than \-1, 0, or +1. |
| .PP |
| .I Deleteavl |
| removes the node matching |
| .I key |
| from |
| .IR tree ; |
| .I oldp |
| is handled as per |
| .IR insertavl . |
| .PP |
| .I Avlwalk |
| returns a pointer to a newly-allocated |
| .B Avlwalk |
| object. |
| .I Endwalk |
| frees such an object. |
| .I Avlnext |
| and |
| .I avlprev |
| walk the tree associated with |
| .IR walk , |
| returning the next |
| (respectively, previous) |
| tree node in the comparison order |
| defined by the comparison function |
| associated with the tree associated with |
| .IR walk . |
| .SH EXAMPLES |
| Intended usage seems to be to make an anonymous |
| .B Avl |
| the first member of the application's tree-node structure, |
| then pass these routines tree-node pointers instead of |
| .BR Avl* s. |
| .IP |
| .EX |
| typedef struct Node { |
| Avl; |
| uchar score[VtScoreSize]; |
| int type; |
| } Node; |
| .sp 0.3v |
| Avltree *tree; |
| Avl *res; |
| Node *np; |
| \fI\&...\fP |
| res = lookupavl(tree, np); |
| .EE |
| .SH SOURCE |
| .B \*9/src/libavl |
| .SH SEE ALSO |
| G. M. Adelson-Velsky, |
| E. M. Landis, |
| ``An algorithm for the organization of information'', |
| .IR "Soviet Mathematics" , |
| Vol. 3, pp. 1256—1263. |
| .SH DIAGNOSTICS |
| Functions returning pointers return |
| .B nil |
| on error. |