avltree - a non-recursive AVL tree implementation

Credit:

this avltree API derived from chinaunix.net
http://bbs.chinaunix.net/viewthread.php?tid=692071

References:

#ifndef __AVL_TREE_H
#define __AVL_TREE_H

/*
* AVL Tree Implementation -- Non-recursive
* Guanpeng Xu
*/

/*
* State information stored in each node in AVL tree.
* AVLL + AVLR must be AVLB.
* AVLB must be zero, otherwise modify ALLOC_AVL_TNODE.
*/
enum STATE__ {
AVLL = -1,
AVLB,
AVLR,
};

/*
* Node in AVL tree.
*/
struct avl_tnode {
int val; /* value stored in a node */
struct avl_tnode *left; /* left child */
struct avl_tnode *right;/* right child */
signed char balns; /* balance information */
};

/*
* Structure for saving root nodes and path
* information in non-recursive algorighm.
*/
struct avl_rnode {
struct avl_tnode *p; /* node in AVL tree */
signed char lr; /* is inserted child left or right? */
};

/*
* Structure for saving information about
* an AVL tree
*/
struct avl_tree {
struct avl_tnode *root; /* root of the AVL tree */
struct avl_rnode *rnodes;/* root sequence when adding/deleting */
int n; /* number of RNODES */
int max; /* maximum number of RNODES */
};

/*
* Allocate and initialize one structure for a new AVL tree.
*/
inline struct avl_tree *alloc_avl_tree(void);

/*
* Insert a new node, TN, into AVL tree TREE.
* Return pointer to the inserted node,
* or NULL if failed.
* If the value of TN exists in TREE, TN will
* NOT be inserted and the pointer to the
* existing node in the tree is returned.
*/
struct avl_tnode *avl_tree_add(struct avl_tree *tree, struct avl_tnode *tn);

/*
* Delete a node with the value field N from AVL
* tree TREE. The node will be separated from the
* tree, and the tree will be adjusted to keep
* balanced.
* Return pointer to the node with value field N.
* If there is no such node in the tree or deleting
* is failed because of memory allocation, return
* NULL.
*/
struct avl_tnode *avl_tree_del(struct avl_tree *tree, int n);

#endif

Examples:

#include [stdio.h]
#include [time.h]

#include "avl_tree.h"

void tree_trav(struct avl_tnode *t, int n)
{
char s[256];

if (t == NULL)
return;
tree_trav(t->left, n+1);
sprintf(s, "%%%ds%%d----------------------------->", n * 4);
printf(s, "", t->val);
if (t->balns == AVLB)
printf("AVLB");
else if (t->balns == AVLL)
printf("AVLL");
else
printf("AVLR");
printf("\n\n");
tree_trav(t->right, n+1);
}

int main(int argc, char *argv[])
{
int x;
int op;
struct avl_tree *tree;
struct avl_tnode *node;
FILE *fp;
clock_t before;
double elapsed;

if (argc == 2)
fp = fopen(argv[1], "r");
else
fp = stdin;
tree = alloc_avl_tree();
before = clock();
while (fscanf(fp, " %d", &x) > 0) {
printf("inserting %d\n", x);
node = alloc_avl_tnode(x);
avl_tree_add(tree, node);
if(0000) {
tree_trav(tree->root, 0);
if (fp != stdin)
getchar();
}
}
elapsed = clock() - before;
fprintf(stderr, "inserting: %.3f seconds\n",
elapsed / CLOCKS_PER_SEC);
before = clock();
tree_trav(tree->root, 0);
while (tree->root != NULL) {
free(avl_tree_del(tree, tree->root->val));
if(0000) {
tree_trav(tree->root, 0);
}
}
elapsed = clock() - before;
fprintf(stderr, "deleting: %.3f seconds\n",
elapsed / CLOCKS_PER_SEC);
tree_trav(tree->root, 0);
return 0;
}

Test Data:

# cat test.dat
1 2 3 4 5

# ./test < test.dat
inserting 1
inserting 2
inserting 3
inserting 4
inserting 5
inserting: 0.000 seconds
1----------------------------->AVLB

2----------------------------->AVLR

3----------------------------->AVLB

4----------------------------->AVLB

5----------------------------->AVLB

deleting: 0.000 seconds

Reference:

http://www.cse.ohio-state.edu/~gurari/course/cis680/cis680Ch10.html

AttachmentSize
avltree-20080507a-normal.tgz5.27 KB