123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245 |
- /* $Id$ */
- #include <alloc.h>
- /* Implementation of AVL-trees: trees in which the difference in depth
- of the left branch and the right branch is at most one.
- The difference in depth is indicated by a "balance" flag in each node:
- this flag has one of three values:
- . indicating that the left branch has the same depth as the right branch,
- + indicating that the right branch is deeper,
- - indicating that the left branch is deeper.
- So, a node has the following structure:
- */
- struct avl_node {
- struct avl_node
- *left,
- *right; /* the left and right branches */
- char *info; /* pointer to information in this node */
- char balance; /* balance information described above */
- };
- /* create definitions for new_avl_node() and free_avl_node() */
- /* STATICALLOCDEF "avl_node" 10 */
- /* There is also a tree header, which contains the root of the tree and
- the address of a user-supplied comparison routine:
- */
- struct avl_tree {
- struct avl_node
- *root; /* root of the avl tree */
- int (*cmp)(); /* address of comparison routine */
- };
- /* create definitions for new_avl_tree() and free_avl_tree() */
- /* STATICALLOCDEF "avl_tree" 2 */
- /* The next routine adds a node to an avl tree. It returns 1 if the
- tree got deeper.
- */
- static int
- balance_add(ppsc, n, cmp)
- struct avl_node **ppsc; /* address of root */
- register char *n; /* user-supplied information */
- int (*cmp)(); /* user-supplied comparison routine */
- {
- register struct avl_node *psc = *ppsc, *qsc, *ssc;
- if (! psc) {
- *ppsc = new_avl_node();
- (*ppsc)->balance = '.';
- (*ppsc)->info = n;
- return 1;
- }
- if ((*cmp)(n, psc->info) < 0) {
- if (balance_add(&(psc->left), n, cmp)) {
- /* left hand side got deeper */
- if (psc->balance == '+') {
- /* but the right hand side was deeper */
- psc->balance = '.';
- return 0;
- }
- if (psc->balance == '.') {
- /* but the right hand side was as deep */
- psc->balance = '-';
- return 1;
- }
- /* left hand side already was one deeper; re-organize */
- qsc = psc->left;
- if (qsc->balance == '-') {
- /* if left-hand side of left node was deeper,
- this node becomes the new root
- */
- psc->balance = '.';
- qsc->balance = '.';
- psc->left = qsc->right;
- qsc->right = psc;
- *ppsc = qsc;
- return 0;
- }
- /* else the right node of the left node becomes the new root */
- ssc = qsc->right;
- psc->left = ssc->right;
- qsc->right = ssc->left;
- ssc->left = qsc;
- ssc->right = psc;
- *ppsc = ssc;
- if (ssc->balance == '.') {
- psc->balance = '.';
- qsc->balance = '.';
- return 0;
- }
- if (ssc->balance == '-') {
- psc->balance = '+';
- qsc->balance = '.';
- ssc->balance = '.';
- return 0;
- }
- psc->balance = '.';
- qsc->balance = '-';
- }
- return 0;
- }
- if (balance_add(&(psc->right), n, cmp)) {
- /* right hand side got deeper */
- if (psc->balance == '-') {
- /* but the left hand side was deeper */
- psc->balance = '.';
- return 0;
- }
- if (psc->balance == '.') {
- /* but the left hand side as deep */
- psc->balance = '+';
- return 1;
- }
- /* right hand side already was one deeper; re-organize */
- qsc = psc->right;
- if (qsc->balance == '+') {
- /* if right-hand side of left node was deeper,
- this node becomes the new root
- */
- psc->balance = '.';
- qsc->balance = '.';
- psc->right = qsc->left;
- qsc->left = psc;
- *ppsc = qsc;
- return 0;
- }
- /* else the left node of the right node becomes the new root */
- ssc = qsc->left;
- psc->right = ssc->left;
- qsc->left = ssc->right;
- ssc->right = qsc;
- ssc->left = psc;
- *ppsc = ssc;
- if (ssc->balance == '.') {
- psc->balance = '.';
- qsc->balance = '.';
- return 0;
- }
- if (ssc->balance == '+') {
- psc->balance = '-';
- qsc->balance = '.';
- ssc->balance = '.';
- return 0;
- }
- psc->balance = '.';
- qsc->balance = '+';
- }
- return 0;
- }
- /* extern struct avl_tree *create_avl_tree(int (*cmp)());
- Returns a fresh avl_tree structure.
- */
- struct avl_tree *
- create_avl_tree(cmp)
- int (*cmp)(); /* comparison routine */
- {
- register struct avl_tree *p = new_avl_tree();
- p->cmp = cmp;
- return p;
- }
- /* extern add_to_avl_tree(struct avl_tree *tree, char *n);
- Adds the information indicated by 'n' to the avl_tree indicated by 'tree'
- */
- add_to_avl_tree(tree, n)
- struct avl_tree *tree; /* tree to be added to */
- char *n; /* information */
- {
- (void) balance_add(&(tree->root), n, tree->cmp);
- }
- /* extern char *find_ngt(struct avl_tree *tree, char *n);
- Returns the information in the largest node that still compares <= to 'n',
- or 0 if not present.
- */
- char *
- find_ngt(tree, n)
- struct avl_tree *tree; /* tree to be searched in */
- char *n; /* information to be compared with */
- {
- register struct avl_node *nd = tree->root, *lastnd = 0;
- for (;;) {
- while (nd && (*tree->cmp)(nd->info, n) > 0) {
- nd = nd->left;
- }
- while (nd && (*tree->cmp)(nd->info, n) <= 0) {
- lastnd = nd;
- nd = nd->right;
- }
- if (! nd) break;
- }
- return lastnd ? lastnd->info : (char *) 0;
- }
- /* extern char *find_nlt(struct avl_tree *tree, char *n);
- Returns the information in the largest node that still compares >= to 'n',
- or 0 if not present.
- */
- char *
- find_nlt(tree, n)
- struct avl_tree *tree; /* tree to be searched in */
- char *n; /* information to be compared with */
- {
- register struct avl_node *nd = tree->root, *lastnd = 0;
- for (;;) {
- while (nd && (*tree->cmp)(nd->info, n) < 0) {
- nd = nd->right;
- }
- while (nd && (*tree->cmp)(nd->info, n) >= 0) {
- lastnd = nd;
- nd = nd->left;
- }
- if (! nd) break;
- }
- return lastnd ? lastnd->info : (char *) 0;
- }
- /* extern char *find_eq(struct avl_tree *tree, char *n);
- Returns the information in the node that compares equal to 'n',
- or 0 if not present.
- */
- char *
- find_eq(tree, n)
- struct avl_tree *tree; /* tree to be searched in */
- char *n; /* information to be compared with */
- {
- register struct avl_node *nd = tree->root;
- for (;;) {
- while (nd && (*tree->cmp)(nd->info, n) < 0) {
- nd = nd->right;
- }
- while (nd && (*tree->cmp)(nd->info, n) > 0) {
- nd = nd->left;
- }
- if (! nd) break;
- }
- return nd ? nd->info : (char *) 0;
- }
|