Java Reference
In-Depth Information
VAL SIZE
R
2
R
A
3
B
1
A
B
C
D
E
F
C
0
D
0
E
0
F
0
(A)
(B)
Figure6.12
A dynamic general tree representation with fixed-size arrays for the
child pointers. (a) The general tree. (b) The tree representation. For each node,
the first field stores the node value while the second field stores the size of the
child pointer array.
The alternative is to allocate variable space for each node. There are two basic
approaches. One is to allocate an array of child pointers as part of the node. In
essence, each node stores an array-based list of child pointers. Figure 6.12 illus-
trates the concept. This approach assumes that the number of children is known
when the node is created, which is true for some applications but not for others.
It also works best if the number of children does not change. If the number of
children does change (especially if it increases), then some special recovery mech-
anism must be provided to support a change in the size of the child pointer array.
One possibility is to allocate a new node of the correct size from free store and re-
turn the old copy of the node to free store for later reuse. This works especially well
in a language with built-in garbage collection such as Java. For example, assume
that a node M initially has two children, and that space for two child pointers is al-
located when M is created. If a third child is added to M, space for a new node with
three child pointers can be allocated, the contents of M is copied over to the new
space, and the old space is then returned to free store. As an alternative to relying
on the system's garbage collector, a memory manager for variable size storage units
can be implemented, as described in Section 12.3. Another possibility is to use a
collection of free lists, one for each array size, as described in Section 4.1.2. Note
in Figure 6.12 that the current number of children for each node is stored explicitly
in a
size
field. The child pointers are stored in an array with
size
elements.
Another approach that is more flexible, but which requires more space, is to
store a linked list of child pointers with each node as illustrated by Figure 6.13.
This implementation is essentially the same as the “list of children” implementation
of Section 6.3.1, but with dynamically allocated nodes rather than storing the nodes
in an array.
