Transcript Chapter 19 Implementing Trees and Priority Queues

Chapter 19
Implementing Trees and
Priority Queues
Fundamentals of Java
Objectives


2
Use the appropriate terminology to describe
trees.
Distinguish different types of hierarchical
collections such as general trees, binary
trees, binary search trees, and heaps.
Fundamentals of Java
Objectives (cont.)



3
Understand the basic tree traversals.
Use binary search trees to implement sorted
sets and sorted maps.
Use heaps to implement priority queues.
Fundamentals of Java
Vocabulary






4
Binary search tree
Binary tree
Expression tree
General tree
Heap
Heap property
Fundamentals of Java
Vocabulary (cont.)






5
Interior node
Leaf
Left subtree
Parse tree
Right subtree
Root
Fundamentals of Java
An Overview of Trees

Tree: Data structure in which each item can
have multiple successors
–
All items have exactly one predecessor.
 Except

Parse tree: Describes the syntactic structure
of a sentence in terms of its component parts
–
6
a privileged item called the root
Noun phrases and verb phrases
Fundamentals of Java
An Overview of Trees (cont.)
Figure 19-1: Parse tree for a sentence
7
Fundamentals of Java
An Overview of Trees (cont.)
Table 19-1: Summary of terms used to describe trees
8
Fundamentals of Java
An Overview of Trees (cont.)
9
Table 19-1: Summary of terms used to
describe trees (cont.)
Fundamentals of Java
An Overview of Trees (cont.)
Figure 19-2: Tree and some of its properties
10
Fundamentals of Java
An Overview of Trees (cont.)


11
General trees: Trees with no restrictions on
number of children
Binary trees: Each node has at most two
children: left child and right child.
Figure 19-3: Two unequal binary trees that
have equal sets of nodes
Fundamentals of Java
An Overview of Trees (cont.)

Recursive processing of trees is common, so
useful to have recursive definitions of trees
–
General tree: Either empty or consists of a finite
set of nodes T
Node r is the root.
 Set T - {r} partitioned into disjoint subsets (general
trees)

–
12
Binary tree: Either empty or consists of a root
plus a left subtree and a right subtree (binary
trees)
Fundamentals of Java
An Overview of Trees (cont.)
Figure 19-4: Different types of binary trees
13
Fundamentals of Java
An Overview of Trees (cont.)

Full binary tree: Contains maximum number
of nodes for its height
–
–
–
–
14
Fully balanced
If height is d, 2d-1 nodes
Level n has up to 2n nodes.
Height of a fully balanced tree of n nodes is
log2n.
Fundamentals of Java
An Overview of Trees (cont.)

Heap: Binary tree in which the item in each
node is less than or equal to the items in both
of its children
–
Heap property
Figure 19-5: Examples of heaps
15
Fundamentals of Java
An Overview of Trees (cont.)

Expression tree: For evaluating expressions
Figure 19-6: Some expression trees
16
Fundamentals of Java
An Overview of Trees: Binary
Search Trees
Figure 19-7: Call tree for the binary search of an array
17
Fundamentals of Java
An Overview of Trees: Binary
Search Trees (cont.)
Figure 19-8: Binary search tree
18
Fundamentals of Java
An Overview of Trees: Binary
Search Trees (cont.)


19
Binary search tree: Each node is greater
than or equal to left child and less than or
equal to right child.
Recursive search process:
Fundamentals of Java
An Overview of Trees: Binary
Search Trees (cont.)
Figure 19-9: Three binary tree shapes with the same data
20
Fundamentals of Java
Binary Tree Traversals
Figure 19-10: Preorder traversal
Figure 19-11: Inorder traversal
21
Fundamentals of Java
Binary Tree Traversals (cont.)
Figure 19-12: Postorder traversal
22
Figure 19-13: Level-order traversal
Fundamentals of Java
Linked Implementation of
Binary Trees
23
Table 19-2: Methods of the BSTPT interface
Fundamentals of Java
Linked Implementation of
Binary Trees (cont.)
Table 19-2: Methods of the BSTPT interface (cont.)
24
Fundamentals of Java
Linked Implementation of
Binary Trees (cont.)
Figure 19-14: Interfaces and classes used in the binary
search tree prototype
25
Fundamentals of Java
Linked Implementation of
Binary Trees (cont.)
26
Example 19.1: Interface for binary search
tree prototypes
Fundamentals of Java
Linked Implementation of
Binary Trees (cont.)
27
Example 19.1: Interface for binary search
tree prototypes (cont.)
Fundamentals of Java
Linked Implementation of
Binary Trees (cont.)
28
add method
Fundamentals of Java
Linked Implementation of
Binary Trees (cont.)
29
add method (cont.)
Fundamentals of Java
Linked Implementation of
Binary Trees (cont.)

30
Pseudocode for searching a binary tree:
Fundamentals of Java
Linked Implementation of
Binary Trees (cont.)

31
Inorder traversal code:
Fundamentals of Java
Linked Implementation of
Binary Trees (cont.)

32
Pseudocode for level-order traversal:
Fundamentals of Java
Linked Implementation of
Binary Trees (cont.)

33
Steps for removing a node:
Fundamentals of Java
Linked Implementation of
Binary Trees (cont.)

34
Expanded step 4 for removing a node from a
binary tree:
Fundamentals of Java
Array Implementation of a
Binary Tree
Figure 19-16: Complete binary tree
Figure 19-17: Array representation of a complete binary
tree
35
Fundamentals of Java
Array Implementation of a
Binary Tree (cont.)
Table 19-3: Locations of given items in an array
representation of a complete binary tree
36
Fundamentals of Java
Array Implementation of a
Binary Tree (cont.)
Table 19-4: Relatives of a given item in an array
representation of a complete binary tree
37
Fundamentals of Java
Implementing Heaps
Table 19-5: Methods in the interface HeapPT
38
Fundamentals of Java
Implementing Heaps (cont.)

39
add method:
Fundamentals of Java
Implementing Heaps (cont.)

40
pop method:
Fundamentals of Java
Implement Heaps (cont.)

41
pop method (cont.):
Fundamentals of Java
Using a Heap to Implement a
Priority Queue
Example 19.3: Heap implementation of a priority queue
42
Fundamentals of Java
Using a Heap to Implement a
Priority Queue (cont.)
43
Example 19.3: Heap implementation of a
priority queue (cont.)
Fundamentals of Java
Summary


44
There are various types of trees or
hierarchical collections such as general
trees, binary trees, binary search trees, and
heaps.
The terminology used to describe
hierarchical collections is borrowed from
biology, genealogy, and geology.
Fundamentals of Java
Summary (cont.)



45
Tree traversals: preorder, inorder, postorder,
and level-order traversal
A binary search tree preserves a natural
ordering among its items and can support
operations that run in logarithmic time.
Binary search trees are useful for
implementing sorted sets and sorted maps.
Fundamentals of Java
Summary (cont.)

Heap
–
–
–


46
Useful for ordering items according to priority
Guarantees logarithmic insertions and removals
Useful for implementing priority queues
Binary search trees typically have a linked
implementation.
Heaps typically have an array representation.
Fundamentals of Java