1 /** <plaintext> 2 * 3 * avl.h -- public types and external declarations for avl trees 4 * 5 * Created 03/01/89 by Brad Appleton 6 * 7 * ^{Mods:* } 8 * 9 * Fri Jul 14 13:54:12 1989, Rev 1.0, brad(0165) 10 * 11 **/ 12 13 #ifndef AVL_H_INCLUDED 14 #define AVL_H_INCLUDED 15 16 /* definition of traversal type */ 17 typedef enum { PREORDER, INORDER, POSTORDER } VISIT; 18 19 20 /* definition of sibling order type */ 21 typedef enum { LEFT_TO_RIGHT, RIGHT_TO_LEFT } SIBLING_ORDER; 22 23 24 /* definition of node type */ 25 typedef enum { IS_TREE, IS_LBRANCH, IS_RBRANCH, IS_LEAF, IS_NULL } NODE; 26 27 /* definition of a NULL action and a NULL tree */ 28 #define NULL_ACTION ((void(*)()) NULL) 29 #define NULL_TREE ((AVLtree) NULL) 30 31 32 /* BEGIN Internal definitions */ 33 /* Directional Definitions */ 34 typedef short DIRECTION; 35 #define LEFT 0 36 #define RIGHT 1 37 #define OPPOSITE(x) (1 - (x)) 38 39 40 /* return codes used by avl_insert(), avl_delete(), and balance() */ 41 #define HEIGHT_UNCHANGED 0 42 #define HEIGHT_CHANGED 1 43 44 45 /* Balance Definitions */ 46 #define LEFT_HEAVY -1 47 #define BALANCED 0 48 #define RIGHT_HEAVY 1 49 #define LEFT_IMBALANCE(nd) ((nd)->bal < LEFT_HEAVY) 50 #define RIGHT_IMBALANCE(nd) ((nd)->bal > RIGHT_HEAVY) 51 52 53 /* structure for a node in an AVL tree */ 54 typedef struct avl_node 55 { struct avl_node *subtree[2]; /* LEFT and RIGHT subtrees */ 56 short bal; /* balance factor */ 57 void * data[1]; /* data on my back */ 58 } AVLnode, *AVLtree; 59 60 /* End Internal definitions */ 61 62 /* structure which holds information about an AVL tree */ 63 typedef struct avl_tree 64 { AVLtree root; /* pointer to the root node of the tree */ 65 long count; /* number of nodes in the tree */ 66 /* function used to compare keys */ 67 void *client_data; /* arbitrary client data */ 68 int (*compar)(void *l, void*r, NODE type); 69 void (*destroy)(void *data); 70 void* (*alloc)(void *cdata, size_t size); 71 void (*free)(void *cdata, void* data, size_t size); 72 int isize; /* item data size */ 73 } avl_tree, *AVL_TREE; 74 75 #define AVL_ENUM_MAX 32 /* balanced tree, allows for 2**32 */ 76 /* nodes */ 77 78 typedef struct avl_enum 79 { AVL_TREE tree; 80 int current; 81 AVLtree parents[AVL_ENUM_MAX]; 82 } avl_enum; 83 84 void *avlfindfirst(AVL_TREE tree, void *key, avl_enum *e); 85 void *avlfindnext(avl_enum *e); 86 void avlfinddestroy(avl_enum *e); 87 88 /* Constructor and Destructor functions for AVL trees: 89 * avlfree is a macro for avldispose in the fashion 90 * of free(). It assumes certain default values 91 * (shown below) for the deallocation function and 92 * for the order in which children are traversed. 93 */ 94 extern AVL_TREE avlinit(AVL_TREE tree, 95 void *cdata, size_t isize, 96 int (*compare)(void *l, void*r, NODE type), 97 void (*destroy)(void *d), 98 void* (*alloc)(void *cdata, size_t bytes), 99 void (*free)(void *cdata, void *ptr, size_t size)); 100 extern void avlfree(AVL_TREE tree); 101 102 /* Routine for manipulating/accessing each data item in a tree */ 103 extern void avlwalk(AVL_TREE, 104 void (*action)(void *data, 105 SIBLING_ORDER order, 106 NODE type, 107 int level, 108 int balance), 109 SIBLING_ORDER); 110 111 112 /* Routine for obtaining the size of an AVL tree */ 113 extern int avlcount(AVL_TREE); 114 115 116 /* Routines to search for a given item */ 117 extern void *avlins(AVL_TREE tree, void *data); 118 extern int avldel(AVL_TREE tree, void *data); 119 extern void *avlfind(AVL_TREE tree, void *data); 120 121 122 /* Routines to search for the minimal item of a tree */ 123 extern int avldelmin(AVL_TREE tree, void *data); 124 extern void *avlfindmin(AVL_TREE tree); 125 126 127 /* Routines to search for the maximal item of a tree */ 128 extern int avldelmax(AVL_TREE tree, void *data); 129 extern void *avlfindmax(AVL_TREE tree); 130 131 #endif /* AVL_H_INCLUDED */ 132