Java Reference
In-Depth Information
Searching a binary tree for a value that matches a key value is fast, especially for
tightly
packed
(or
balanced
)
trees
. In a tightly packed tree, each level contains about twice as
many elements as the previous level. Figure 21.19 is a tightly packed binary tree. A tightly
packed binary search tree with
n
elements has log
2
n
levels. Thus, at most log
2
n
compari-
sons are required either to find a match or to determine that no match exists. Searching a
(tightly packed) 1000-element binary search tree requires at most 10 comparisons, because
2
10
> 1000. Searching a (tightly packed) 1,000,000-element binary search tree requires at
most 20 comparisons, because 2
20
> 1,000,000.
The chapter exercises present algorithms for several other binary tree operations, such
as deleting an item from a binary tree, printing a binary tree in a two-dimensional tree
format and performing a
level-order traversal of a binary tree
. The level-order traversal
visits the nodes of the tree row by row, starting at the root node level. On each level of the
tree, a level-order traversal visits the nodes from left to right. Other binary tree exercises
include allowing a binary search tree to contain duplicate values, inserting string values in
a binary tree and determining how many levels are contained in a binary tree.
This chapter completes our presentation of data structures. We began in Chapter 16 with
an introduction to the built-in collections of the Java Collections Framework and contin-
ued in Chapter 20 by showing you how to implement generic methods and collections. In
this chapter, you learned to build generic dynamic data structures that grow and shrink at
execution time. You learned that linked lists are collections of data items that are “linked
up in a chain.” You also saw that an application can perform insertions and deletions at
the beginning and end of a linked list. You learned that the stack and queue data structures
are constrained versions of lists. For stacks, you saw that insertions and deletions are made
only at the top
.
For queues that
represent waiting lines, you saw that insertions are made
at the tail and deletions are made from the head. You also learned the binary tree data
structure. You saw a binary search tree that
facilitated high-speed searching and sorting of
data and eliminating duplicate data items efficiently. Throughout the chapter, you learned
how to create and package these data structures for reusability and maintainability.
In the next chapter, you'll continue your study of Swing GUI concepts, building on the
techniques you learned in Chapter 12. In Chapter 25, we'll introduce JavaFX GUI and
include in-depth treatments of JavaFX GUI, graphics and multimedia in the online chapters.
Summary
Section 21.1 Introduction
• Dynamic data structures (p. 870) can grow and shrink at execution time.
• Linked lists (p. 870) are collections of data items “linked up in a chain”—insertions and dele-
tions can be made anywhere in a linked list.
• Stacks (p. 870) are important in compilers and operating systems—insertions and deletions are
made only at the top (p. 870) of a stack.
• In a queue, insertions are made at the tail (p. 870) and deletions are made from the head (p. 870).
• Binary trees (p. 870) facilitate high-speed searching and sorting, eliminating duplicate data items
efficiently, representing file-system directories and compiling expressions into machine language.
