avl.3 (2928B)
1 .TH AVL 3 2 .SH NAME 3 mkavltree, insertavl, lookupavl, deleteavl, avlwalk, avlnext, avlprev, endwalk - AVL tree routines 4 .SH SYNOPSIS 5 .\" .ta 0.75i 1.5i 2.25i 3i 3.75i 4.5i 6 .ta 0.7i +0.7i +0.7i +0.7i +0.7i +0.7i +0.7i 7 .EX 8 #include <u.h> 9 #include <libc.h> 10 #include <avl.h> 11 .sp 0.3v 12 typedef struct Avl Avl; 13 struct Avl 14 { 15 Avl *p; /* parent */ 16 Avl *n[2]; /* children */ 17 int bal; /* balance bits */ 18 }; 19 .sp 0.3v 20 Avl *avlnext(Avlwalk *walk); 21 Avl *avlprev(Avlwalk *walk); 22 Avlwalk *avlwalk(Avltree *tree); 23 void deleteavl(Avltree *tree, Avl *key, Avl **oldp); 24 void endwalk(Avlwalk *walk); 25 void insertavl(Avltree *tree, Avl *new, Avl **oldp); 26 Avl *lookupavl(Avltree *tree, Avl *key); 27 Avl *searchavl(Avltree *tree, Avl *key, int neighbor); 28 Avltree *mkavltree(int(*cmp)(Avl*, Avl*)); 29 .EE 30 .SH DESCRIPTION 31 An AVL tree is a self-balancing binary search tree. 32 These routines allow creation and maintenance of in-memory AVL trees. 33 .PP 34 An empty AVL tree is created by calling 35 .I mkavltree 36 with a comparison function as argument. 37 This function should take two pointers to 38 .B Avl 39 objects and return -1, 0 or 1 as the first is 40 respectively less than, 41 equal to, or greater than, 42 the second. 43 .I Insertavl 44 adds a 45 .I new 46 tree node into 47 .IR tree . 48 If 49 .I oldp 50 is non-nil upon return, 51 it points to storage for an old node 52 with the same key that may now be freed. 53 .I Lookupavl 54 returns the 55 .I tree 56 node that matches 57 .I key 58 by 59 .IR tree 's 60 comparison function, 61 or 62 .B nil 63 if none. 64 .PP 65 .I Searchavl 66 returns the 67 .I tree 68 node that matches 69 .I key 70 by 71 .IR tree 's 72 comparison function, if it exists. 73 If it does not, and 74 .I neighbor 75 is positive, it returns the nearest node whose 76 .I key 77 is greater or 78 .B nil 79 if there is none and, if 80 .I neighbor 81 is negative, it returns the nearest node whose 82 .I key 83 is less or 84 .B nil 85 if there is none. 86 It is an error to set 87 .I neighbor 88 to values other than \-1, 0, or +1. 89 .PP 90 .I Deleteavl 91 removes the node matching 92 .I key 93 from 94 .IR tree ; 95 .I oldp 96 is handled as per 97 .IR insertavl . 98 .PP 99 .I Avlwalk 100 returns a pointer to a newly-allocated 101 .B Avlwalk 102 object. 103 .I Endwalk 104 frees such an object. 105 .I Avlnext 106 and 107 .I avlprev 108 walk the tree associated with 109 .IR walk , 110 returning the next 111 (respectively, previous) 112 tree node in the comparison order 113 defined by the comparison function 114 associated with the tree associated with 115 .IR walk . 116 .SH EXAMPLES 117 Intended usage seems to be to make an anonymous 118 .B Avl 119 the first member of the application's tree-node structure, 120 then pass these routines tree-node pointers instead of 121 .BR Avl* s. 122 .IP 123 .EX 124 typedef struct Node { 125 Avl; 126 uchar score[VtScoreSize]; 127 int type; 128 } Node; 129 .sp 0.3v 130 Avltree *tree; 131 Avl *res; 132 Node *np; 133 \fI\&...\fP 134 res = lookupavl(tree, np); 135 .EE 136 .SH SOURCE 137 .B \*9/src/libavl 138 .SH SEE ALSO 139 G. M. Adelson-Velsky, 140 E. M. Landis, 141 ``An algorithm for the organization of information'', 142 .IR "Soviet Mathematics" , 143 Vol. 3, pp. 1256—1263. 144 .SH DIAGNOSTICS 145 Functions returning pointers return 146 .B nil 147 on error.