Memory allocation/deallocation for tree? Any good way?

[Dan Salomon]

In article <1991Jan7.034619.4449 at portia.Stanford.EDU> fangchin at portia.Stanford.EDU (Chin Fang) writes:
>
> The problem I had (and still having) was how to keep the program's
> memory consumption almost constant.  From what I understand, if my
> malloc(3C) and free3(C) work correctly, as long as I make sure that
> a sequence of malloced memory blocks are freed in EXACTLY the reverse 
> order, my program's memory consumption would stay constant no matter
> how many iterations it goes thru.  This has been my guideline in my
> coding.  By the way, I always do C programming on UNIX machines.  

What you can do is add an extra pointer to the binary tree nodes
to form a linked list that records the order of allocation.

Ptr-to-Head-of-Allocation-List
    |
    |
    V
-------------------------------------------------------
| Data  |  left-subtree | right-subtree | new-pointer |
-------------------------------------------------------
                                                  |
						  |
						  V
			             To node allocated just 
				     before this one.

Every time you allocate a tree node, also add it to the FRONT of the
linked list recording allocations.  Thus the linked list will
be in order of most recent allocation first, oldest allocation last.
As a result it is easy to free the nodes from front to back.

Note that each node is in two data structures simultaneously,
the tree data structure, and the allocation data structure.
Since the data structures are accessed through different
pointers, they do not interfere with each other.

-- 

Dan Salomon -- salomon at ccu.UManitoba.CA
               Dept. of Computer Science / University of Manitoba
	       Winnipeg, Manitoba, Canada  R3T 2N2 / (204) 275-6682