415 lines
9.8 KiB
C
415 lines
9.8 KiB
C
/*
|
|
* 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 (*) (void *, void *), int (*) (void *));
|
|
static int avldelete (tree **, int (*) (void *, void *), char *, int (*) (void *), int *, int *);
|
|
static void del (tree **, int *, tree **, int (*) (void *), int *);
|
|
static void balanceL (tree **, int *);
|
|
static void balanceR (tree **, int *);
|
|
|
|
|
|
void tree_init (tree ** ppr_tree)
|
|
{
|
|
*ppr_tree = NULL;
|
|
return;
|
|
}
|
|
|
|
|
|
char *tree_srch(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(tree **ppr_tree, int (*pfi_compare) (void *, void *), char *pc_user, int (*pfi_delete) (void *)){
|
|
int i_balance = 0;
|
|
|
|
sprout(ppr_tree, pc_user, &i_balance, pfi_compare, pfi_delete);
|
|
return;
|
|
}
|
|
|
|
|
|
static void sprout(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(tree **ppr_p, int (*pfi_compare) (void *, void *), char *pc_user, int (*pfi_uar) (void *)){
|
|
int i_balance = 0, i_uar_called = 0;
|
|
|
|
return avldelete(ppr_p, pfi_compare, pc_user, pfi_uar,
|
|
&i_balance, &i_uar_called);
|
|
}
|
|
|
|
|
|
static int avldelete(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 = avldelete(&(*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 = avldelete(&(*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(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(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(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;
|
|
}
|