jeenglis@nunki.usc.edu (Joe English) (11/30/89)
kminor@ms.uky.edu (Kevin R. Minor) writes: >I am attempting to implement an AVL tree. I have the insertion >and deletion routines. I'm using pointers to access the nodes of >the tree. > >Here's my question. Is there a way to free up the entire memory >without having to deallocate each node? If I can free the entire tree >structure in one step, it will dramatically save in run-time. Either way, >I'd like to know for my paper. Don't malloc() each node individually; instead allocate a big chunk of nodes and use them one at a time. When you want to destroy the tree, just free the big chunks. Something like this should do what you want: (Note: I just typed this in, so test it before you try it.) /* Blocks of nodes are mallocked and stored in a linked list; The function allocate_node() returns the next available node in the current block. */ #define NODEBLOCKSIZE some_big_number struct nodeblock { struct nodeblock *prevblock; /* last block allocated */ struct node *nextavail; /* ptr. to next available AVL node */ int nodesleft; /* #nodes left in block */ struct node block[NODEBLOCKSIZE]; /* actual storage */ }; static nodeblock *base = 0; struct node *allocate_node() { if (!base || !base->nodesleft) { /* need to get another block */ struct nodeblock *old = base; base = malloc(sizeof(struct nodeblock)); if (!base) return (struct node *)0; base->prevblock = old; base->nodesleft = NODEBLOCKSIZE; base->nextavail = base->block; } base->nodesleft--; return base->nextavail++; } void free_all_nodes() { struct nodeblock *prev; while (base) { prev = base->prevblock; free(base); base = prev; } } You might want to maintain a free list of deleted nodes too. You save on malloc() overhead as well with this approach. Hope this helps, --Joe English jeenglis@nunki.usc.edu