Java Reference
In-Depth Information
Figure 6.13. How do the two implementations compare in space and time
efficiency and ease of implementation?
6.3 Write classes that implement the general tree class declarations of Figure 6.2
using the linked general tree implementation with child pointer arrays of Fig-
ure 6.12. Your implementation must be able to support changes in the num-
ber of children for a node. When created, a node should be allocated with
only enough space to store its initial set of children. Whenever a new child is
added to a node such that the array overflows, allocate a new array from free
store that can store twice as many children.
6.4 Implement a BST file archiver. Your program should take a BST created in
main memory using the implementation of Figure 5.14 and write it out to
disk using one of the sequential representations of Section 6.5. It should also
be able to read in disk files using your sequential representation and create
the equivalent main memory representation.
6.5 Use the UNION/FIND algorithm to implement a solution to the following
problem. Given a set of points represented by their xy-coordinates, assign
the points to clusters. Any two points are defined to be in the same cluster if
they are within a specified distance d of each other. For the purpose of this
problem, clustering is an equivalence relationship. In other words, points A,
B, and C are defined to be in the same cluster if the distance between A and B
is less than d and the distance between A and C is also less than d, even if the
distance between B and C is greater than d. To solve the problem, compute
the distance between each pair of points, using the equivalence processing
algorithm to merge clusters whenever two points are within the specified
distance. What is the asymptotic complexity of this algorithm? Where is the
bottleneck in processing?
6.6 In this project, you will run some empirical tests to determine if some vari-
ations on path compression in the UNION/FIND algorithm will lead to im-
proved performance.
You should compare the following five implementa-
tions:
(a) Standard UNION/FIND with path compression and weighted union.
(b) Path compression and weighted union, except that path compression is
done after the UNION, instead of during the FIND operation. That is,
make all nodes along the paths traversed in both trees point directly to
the root of the larger tree.
(c) Weighted union and path halving as described in Exercise 6.10.
(d) Weighted union and a simplified form of path compression. At the end
of every FIND operation, make the node point to its tree's root (but
don't change the pointers for other nodes along the path).
(e) Weighted union and a simplified form of path compression. Both nodes
in the equivalence will be set to point directly to the root of the larger
