/* * avltree.c * * This program text was created by Paul Vixie using examples from the book: * "Algorithms & Data Structures," Niklaus Wirth, Prentice-Hall, 1986, ISBN * 0-13-022005-1. This code and associated documentation is hereby placed * in the public domain. */ /********************************* README ********************************* AVL Trees V1.0 24-July-1987 Paul Vixie This library and test program are useful for creating and using balanced binary trees (AVL trees). The tree is held in memory, using malloc(3) to allocate storage. A better version would allow file-based trees in addition; once memory mapped files hit the UNIX(tm) community, this will be much easier to do. In the meanwhile, these routines have been very useful to be for symbol tables and the like. (Yes, I'm sure hashing is better in some way, but I've used this for symbol tables, just the same.) I cannot take credit for the algorithms. See "Algorithms & Data Structures," Niklaus Wirth, Prentice-Hall 1986, ISBN 0-13-022005-1. This is an update of Wirth's previous book, titled "Algorythms + Data Structures = Programs," which used Pascal as the language for examples. This later book uses the newer Modula-2 for it's examples; this tree code was created using the Modula-2 examples as guidelines. At the time I typed this stuff in (about a year ago, in July 1987), I understood how it all worked. Today, well... This code is hereby placed in the public domain, unless restrictions apply from Prentice-Hall on the algorithms themselves. If you use or redistribute this code, please leave my name (and Wirth's) in the comments. **************************************************************************/ #include "std.h" #include "avltree.h" /* * Prototypes for local functions */ static void sprout (tree **, char *, int *, int (*) (), int (*) ()); static int delete (tree **, int (*) (), char *, int (*) (), int *, int *); static void del (tree **, int *, tree **, int (*) (), int *); static void balanceL (tree **, int *); static void balanceR (tree **, int *); void tree_init (tree ** ppr_tree) { *ppr_tree = NULL; return; } char *tree_srch(ppr_tree, pfi_compare, pc_user) tree *ppr_tree; int (*pfi_compare) (void *, void *); char *pc_user; { register int i_comp; while (ppr_tree) { i_comp = (*pfi_compare) (pc_user, ppr_tree->tree_p); if (i_comp > 0) { ppr_tree = ppr_tree->tree_r; continue; } if (i_comp < 0) { ppr_tree = ppr_tree->tree_l; continue; } /* * not higher, not lower... this must be the one. */ return ppr_tree->tree_p; } /* * grounded. NOT found. */ return NULL; } void tree_add(ppr_tree, pfi_compare, pc_user, pfi_delete) tree **ppr_tree; int (*pfi_compare) (); char *pc_user; int (*pfi_delete) (); { int i_balance = 0; sprout(ppr_tree, pc_user, &i_balance, pfi_compare, pfi_delete); return; } static void sprout(ppr, pc_data, pi_balance, pfi_compare, pfi_delete) tree **ppr; char *pc_data; int *pi_balance; int (*pfi_compare) (void *, void *); int (*pfi_delete) (void *); { tree *p1, *p2; int cmp; /* * are we grounded? if so, add the node "here" and set the rebalance * flag, then exit. */ if (!*ppr) { *ppr = ALLOCATE(tree, TAG_UID, "sprout"); (*ppr)->tree_l = NULL; (*ppr)->tree_r = NULL; (*ppr)->tree_b = 0; (*ppr)->tree_p = pc_data; *pi_balance = 1; return; } /* * compare the data using routine passed by caller. */ cmp = (*pfi_compare) (pc_data, (*ppr)->tree_p); /* * if LESS, prepare to move to the left. */ if (cmp < 0) { sprout(&(*ppr)->tree_l, pc_data, pi_balance, pfi_compare, pfi_delete); if (*pi_balance) { /* left branch has grown longer */ switch ((*ppr)->tree_b) { case 1: /* right branch WAS longer; balance is ok now */ (*ppr)->tree_b = 0; *pi_balance = 0; break; case 0: /* balance WAS okay; now left branch longer */ (*ppr)->tree_b = -1; break; case -1: /* left branch was already too long. rebalnce */ p1 = (*ppr)->tree_l; if (p1->tree_b == -1) { /* LL */ (*ppr)->tree_l = p1->tree_r; p1->tree_r = *ppr; (*ppr)->tree_b = 0; *ppr = p1; } else { /* double LR */ p2 = p1->tree_r; p1->tree_r = p2->tree_l; p2->tree_l = p1; (*ppr)->tree_l = p2->tree_r; p2->tree_r = *ppr; if (p2->tree_b == -1) (*ppr)->tree_b = 1; else (*ppr)->tree_b = 0; if (p2->tree_b == 1) p1->tree_b = -1; else p1->tree_b = 0; *ppr = p2; } /* else */ (*ppr)->tree_b = 0; *pi_balance = 0; } /* switch */ } /* if */ return; } /* if */ /* * if MORE, prepare to move to the right. */ if (cmp > 0) { sprout(&(*ppr)->tree_r, pc_data, pi_balance, pfi_compare, pfi_delete); if (*pi_balance) { /* right branch has grown longer */ switch ((*ppr)->tree_b) { case -1: (*ppr)->tree_b = 0; *pi_balance = 0; break; case 0: (*ppr)->tree_b = 1; break; case 1: p1 = (*ppr)->tree_r; if (p1->tree_b == 1) { /* RR */ (*ppr)->tree_r = p1->tree_l; p1->tree_l = *ppr; (*ppr)->tree_b = 0; *ppr = p1; } else { /* double RL */ p2 = p1->tree_l; p1->tree_l = p2->tree_r; p2->tree_r = p1; (*ppr)->tree_r = p2->tree_l; p2->tree_l = *ppr; if (p2->tree_b == 1) (*ppr)->tree_b = -1; else (*ppr)->tree_b = 0; if (p2->tree_b == -1) p1->tree_b = 1; else p1->tree_b = 0; *ppr = p2; } /* else */ (*ppr)->tree_b = 0; *pi_balance = 0; } /* switch */ } /* if */ return; } /* if */ /* * not less, not more: this is the same key! replace... */ *pi_balance = 0; if (pfi_delete) (*pfi_delete) ((*ppr)->tree_p); (*ppr)->tree_p = pc_data; return; } int tree_delete(ppr_p, pfi_compare, pc_user, pfi_uar) tree **ppr_p; int (*pfi_compare) (); char *pc_user; int (*pfi_uar) (); { int i_balance = 0, i_uar_called = 0; return delete(ppr_p, pfi_compare, pc_user, pfi_uar, &i_balance, &i_uar_called); } static int delete(ppr_p, pfi_compare, pc_user, pfi_uar, pi_balance, pi_uar_called) tree **ppr_p; int (*pfi_compare) (void *, void *); char *pc_user; int (*pfi_uar) (void *); int *pi_balance; int *pi_uar_called; { tree *pr_q; int i_comp, i_ret; if (*ppr_p == NULL) { return 0; } i_comp = (*pfi_compare) ((*ppr_p)->tree_p, pc_user); if (i_comp > 0) { i_ret = delete(&(*ppr_p)->tree_l, pfi_compare, pc_user, pfi_uar, pi_balance, pi_uar_called); if (*pi_balance) balanceL(ppr_p, pi_balance); } else if (i_comp < 0) { i_ret = delete(&(*ppr_p)->tree_r, pfi_compare, pc_user, pfi_uar, pi_balance, pi_uar_called); if (*pi_balance) balanceR(ppr_p, pi_balance); } else { pr_q = *ppr_p; if (pr_q->tree_r == NULL) { *ppr_p = pr_q->tree_l; *pi_balance = 1; } else if (pr_q->tree_l == NULL) { *ppr_p = pr_q->tree_r; *pi_balance = 1; } else { del(&pr_q->tree_l, pi_balance, &pr_q, pfi_uar, pi_uar_called); if (*pi_balance) balanceL(ppr_p, pi_balance); } FREE(pr_q); if (!*pi_uar_called && pfi_uar) (*pfi_uar) (pr_q->tree_p); i_ret = 1; } return i_ret; } static void del(ppr_r, pi_balance, ppr_q, pfi_uar, pi_uar_called) tree **ppr_r; int *pi_balance; tree **ppr_q; int (*pfi_uar) (void *); int *pi_uar_called; { if ((*ppr_r)->tree_r != NULL) { del(&(*ppr_r)->tree_r, pi_balance, ppr_q, pfi_uar, pi_uar_called); if (*pi_balance) balanceR(ppr_r, pi_balance); } else { if (pfi_uar) (*pfi_uar) ((*ppr_q)->tree_p); *pi_uar_called = 1; (*ppr_q)->tree_p = (*ppr_r)->tree_p; *ppr_q = *ppr_r; *ppr_r = (*ppr_r)->tree_l; *pi_balance = 1; } return; } static void balanceL (tree ** ppr_p, int * pi_balance) { tree *p1, *p2; int b1, b2; switch ((*ppr_p)->tree_b) { case -1: (*ppr_p)->tree_b = 0; break; case 0: (*ppr_p)->tree_b = 1; *pi_balance = 0; break; case 1: p1 = (*ppr_p)->tree_r; b1 = p1->tree_b; if (b1 >= 0) { (*ppr_p)->tree_r = p1->tree_l; p1->tree_l = *ppr_p; if (b1 == 0) { (*ppr_p)->tree_b = 1; p1->tree_b = -1; *pi_balance = 0; } else { (*ppr_p)->tree_b = 0; p1->tree_b = 0; } *ppr_p = p1; } else { p2 = p1->tree_l; b2 = p2->tree_b; p1->tree_l = p2->tree_r; p2->tree_r = p1; (*ppr_p)->tree_r = p2->tree_l; p2->tree_l = *ppr_p; if (b2 == 1) (*ppr_p)->tree_b = -1; else (*ppr_p)->tree_b = 0; if (b2 == -1) p1->tree_b = 1; else p1->tree_b = 0; *ppr_p = p2; p2->tree_b = 0; } } return; } static void balanceR (tree ** ppr_p, int * pi_balance) { tree *p1, *p2; int b1, b2; switch ((*ppr_p)->tree_b) { case 1: (*ppr_p)->tree_b = 0; break; case 0: (*ppr_p)->tree_b = -1; *pi_balance = 0; break; case -1: p1 = (*ppr_p)->tree_l; b1 = p1->tree_b; if (b1 <= 0) { (*ppr_p)->tree_l = p1->tree_r; p1->tree_r = *ppr_p; if (b1 == 0) { (*ppr_p)->tree_b = -1; p1->tree_b = 1; *pi_balance = 0; } else { (*ppr_p)->tree_b = 0; p1->tree_b = 0; } *ppr_p = p1; } else { p2 = p1->tree_r; b2 = p2->tree_b; p1->tree_r = p2->tree_l; p2->tree_l = p1; (*ppr_p)->tree_l = p2->tree_r; p2->tree_r = *ppr_p; if (b2 == -1) (*ppr_p)->tree_b = 1; else (*ppr_p)->tree_b = 0; if (b2 == 1) p1->tree_b = -1; else p1->tree_b = 0; *ppr_p = p2; p2->tree_b = 0; } } return; } int tree_trav(ppr_tree, pfi_uar) tree **ppr_tree; int (*pfi_uar) (void *); { if (!*ppr_tree) return 1; if (!tree_trav(&(**ppr_tree).tree_l, pfi_uar)) return 0; if (!(*pfi_uar) ((**ppr_tree).tree_p)) return 0; if (!tree_trav(&(**ppr_tree).tree_r, pfi_uar)) return 0; return 1; } void tree_mung(ppr_tree, pfi_uar) tree **ppr_tree; int (*pfi_uar) (void *); { if (*ppr_tree) { tree_mung(&(**ppr_tree).tree_l, pfi_uar); tree_mung(&(**ppr_tree).tree_r, pfi_uar); if (pfi_uar) (*pfi_uar) ((**ppr_tree).tree_p); FREE(*ppr_tree); *ppr_tree = NULL; } return; }