Java Reference
In-Depth Information
child value B, and right child value A. Make the algorithm as efficient as you
can. Analyze your algorithm's running time. How much harder would it be
to make this algorithm work on a general tree?
6.3 Write a postorder traversal function for general trees, similar to the preorder
traversal function named
preorder
given in Section 6.1.2.
6.4 Write a function that takes as input a general tree and returns the number of
nodes in that tree. Write your function to use the
GenTree
and
GTNode
ADTs of Figure 6.2.
6.5 Describe how to implement the weighted union rule efficiently. In particular,
describe what information must be stored with each node and how this infor-
mation is updated when two trees are merged. Modify the implementation of
Figure 6.4 to support the weighted union rule.
6.6 A potential alternative to the weighted union rule for combining two trees is
the height union rule. The height union rule requires that the root of the tree
with greater height become the root of the union. Explain why the height
union rule can lead to worse average time behavior than the weighted union
rule.
6.7 Using the weighted union rule and path compression, show the array for
the parent pointer implementation that results from the following series of
equivalences on a set of objects indexed by the values 0 through 15. Initially,
each element in the set should be in a separate equivalence class. When two
trees to be merged are the same size, make the root with greater index value
be the child of the root with lesser index value.
(0, 2) (1, 2) (3, 4) (3, 1) (3, 5) (9, 11) (12, 14) (3, 9) (4, 14) (6, 7) (8, 10) (8, 7)
(7, 0) (10, 15) (10, 13)
6.8 Using the weighted union rule and path compression, show the array for
the parent pointer implementation that results from the following series of
equivalences on a set of objects indexed by the values 0 through 15. Initially,
each element in the set should be in a separate equivalence class. When two
trees to be merged are the same size, make the root with greater index value
be the child of the root with lesser index value.
(2, 3) (4, 5) (6, 5) (3, 5) (1, 0) (7, 8) (1, 8) (3, 8) (9, 10) (11, 14) (11, 10)
(12, 13) (11, 13) (14, 1)
6.9 Devise a series of equivalence statements for a collection of sixteen items
that yields a tree of height 5 when both the weighted union rule and path
compression are used. What is the total number of parent pointers followed
to perform this series?
6.10 One alternative to path compression that gives similar performance gains
is called path halving. In path halving, when the path is traversed from
the node to the root, we make the grandparent of every other node i on the
