Java Reference
In-Depth Information
(c) What is the average number of bits required by a character using the
Huffman code for this alphabet?
5.32 You must keep track of some data. Your options are:
(1) A linked-list maintained in sorted order.
(2) A linked-list of unsorted records.
(3) A binary search tree.
(4) An array-based list maintained in sorted order.
(5) An array-based list of unsorted records.
For each of the following scenarios, which of these choices would be best?
Explain your answer.
(a) The records are guaranteed to arrive already sorted from lowest to high-
est (i.e., whenever a record is inserted, its key value will always be
greater than that of the last record inserted). A total of 1000 inserts will
be interspersed with 1000 searches.
(b) The records arrive with values having a uniform random distribution
(so the BST is likely to be well balanced).
1,000,000 insertions are
performed, followed by 10 searches.
(c) The records arrive with values having a uniform random distribution (so
the BST is likely to be well balanced). 1000 insertions are interspersed
with 1000 searches.
(d) The records arrive with values having a uniform random distribution (so
the BST is likely to be well balanced). 1000 insertions are performed,
followed by 1,000,000 searches.
5.9
Projects
5.1 Re-implement the composite design for the binary tree node class of Fig-
ure 5.11 using a flyweight in place of
null
pointers to empty nodes.
5.2 One way to deal with the “problem” of
null
pointers in binary trees is to
use that space for some other purpose. One example is the threaded binary
tree. Extending the node implementation of Figure 5.7, the threaded binary
tree stores with each node two additional bit fields that indicate if the child
pointers
lc
and
rc
are regular pointers to child nodes or threads. If
lc
is not a pointer to a non-empty child (i.e., if it would be
null
in a regular
binary tree), then it instead stores a pointer to the inorder predecessor of that
node. The inorder predecessor is the node that would be printed immediately
before the current node in an inorder traversal. If
rc
is not a pointer to a
child, then it instead stores a pointer to the node's inorder successor. The
inorder successor is the node that would be printed immediately after the
current node in an inorder traversal. The main advantage of threaded binary
