Java Reference
In-Depth Information
The implementation of the iterator is not efficient. Every time you remove an element through
the iterator, the whole list is rebuilt (line 261 in Listing 25.5 BST.java). The client should
always use the
delete
method in the
BinraryTree
class to remove an element. To prevent
the user from using the
remove
method in the iterator, implement the iterator as follows:
public void
remove() {
throw new
UnsupportedOperationException
(
"Removing an element from the iterator is not supported"
);
}
After making the
remove
method unsupported by the iterator class, you can implement the iterator
more efficiently without having to maintain a list for the elements in the tree. You can use a stack
to store the nodes, and the node on the top of the stack contains the element that is to be returned
from the
next()
method. If the tree is well-balanced, the maximum stack size will be
O
(log
n
).
25.14
✓
✓
What is an iterator?
Check
25.15
Point
What method is defined in the
java.lang.Iterable<E>
interface?
25.16
Suppose you delete
extends Iterable<E>
from line 1 in Listing 25.3, Tree.java.
Will Listing 25.11 still compile?
25.17
What is the benefit of being a subtype of
Iterable<E>
?
Huffman coding compresses data by using fewer bits to encode characters that occur
more frequently. The codes for the characters are constructed based on the occur-
rence of the characters in the text using a binary tree, called the Huffman coding tree.
Compressing data is a common task. There are many utilities available for compressing files.
This section introduces Huffman coding, invented by David Huffman in 1952.
In ASCII, every character is encoded in 8 bits. If a text consists of 100 characters, it will take
800 bits to represent the text. The idea of Huffman coding is to use a fewer bits to encode fre-
quently used characters in the text and more bits to encode less frequently used characters to reduce
the overall size of the file. In Huffman coding, the characters' codes are constructed based on the
characters' occurrence in the text using a binary tree, called the
Huffman coding tree
. Suppose
the text is
Mississippi
. Its Huffman tree can be shown as in Figure 25.20a. The left and right
edges of a node are assigned a value
0
and
1
, respectively. Each character is a leaf in the tree. The
code for the character consists of the edge values in the path from the root to the leaf, as shown in
Figure 25.20b. Since
i
and
s
appear more than
M
and
p
in the text, they are assigned shorter codes.
Based on the coding scheme in Figure 25.20,
is encoded to
Key
Point
Huffman coding
is decoded to
Mississippi
=======7
000101011010110010011
======= 7
Mississippi
0
1
Character
M
p
s
i
Code
000
001
01
1
Frequency
1
2
4
4
i
0
1
s
0
1
p
M
(a) Huffman coding tree
(b) Character code table
F
IGURE
25.20
The codes for characters are constructed based on the occurrence of characters
in the text using a coding tree.
Search WWH ::
Custom Search