ref: a584d9eb96636f0743b4d10150f34fc81fd4bb1b
dir: /sys/man/2/avl/
.TH AVL 2 .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 /sys/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.