Java Reference
In-Depth Information
path the new parent of i. Write a version of
FIND
that implements path
halving. Your
FIND
operation should work as you move up the tree, rather
than require the two passes needed by path compression.
6.11 Analyze the fraction of overhead required by the “list of children” imple-
mentation, the “left-child/right-sibling” implementation, and the two linked
implementations of Section 6.3.3. How do these implementations compare
in space efficiency?
6.12 Using the general tree ADT of Figure 6.2, write a function that takes as input
the root of a general tree and returns a binary tree generated by the conversion
process illustrated by Figure 6.14.
6.13 Use mathematical induction to prove that the number of leaves in a non-
empty full K-ary tree is (K 1)n + 1, where n is the number of internal
nodes.
6.14 Derive the formulas for computing the relatives of a non-empty complete
K-ary tree node stored in the complete tree representation of Section 5.3.3.
6.15 Find the overhead fraction for a full K-ary tree implementation with space
requirements as follows:
(a) All nodes store data, K child pointers, and a parent pointer. The data
field requires four bytes and each pointer requires four bytes.
(b) All nodes store data and K child pointers. The data field requires six-
teen bytes and each pointer requires four bytes.
(c) All nodes store data and a parent pointer, and internal nodes store K
child pointers. The data field requires eight bytes and each pointer re-
quires four bytes.
(d) Only leaf nodes store data; only internal nodes store K child pointers.
The data field requires four bytes and each pointer requires two bytes.
6.16 (a) Write out the sequential representation for Figure 6.18 using the coding
illustrated by Example 6.5.
(b) Write out the sequential representation for Figure 6.18 using the coding
illustrated by Example 6.6.
6.17 Draw the binary tree representing the following sequential representation for
binary trees illustrated by Example 6.5:
ABD==E==C=F==
6.18 Draw the binary tree representing the following sequential representation for
binary trees illustrated by Example 6.6:
A
0
=B
0
=C
0
D
0
G=E
Show the bit vector for leaf and internal nodes (as illustrated by Example 6.7)
for this tree.
