Transcript Chapter 10

Chapter 10: Data Structures II
Presentation slides for
Java Software Solutions
for AP* Computer Science
by John Lewis, William Loftus, and Cara Cocking
Java Software Solutions is published by Addison-Wesley
Presentation slides are copyright 2002 by John Lewis, William Loftus, and Cara Cocking. All rights
reserved.
Instructors using the textbook may use and modify these slides for pedagogical purposes.
Data Structures II
 Now we learn a few more data structures
 Chapter 10 focuses on:
•
•
•
•
Sets and maps
Trees and binary search trees
Heaps
Handling collisions in hashtables
2
Sets and Maps
 A set is a collection of elements with no duplicates
• Example: {5, 7, 8} is a set, {3, 3, 4} is not
 A map matches, or maps, keys to value
• Example: a dictionary is a map that maps words to
definitions
 The keys in a map form a set (and therefore must be
unique)
 The Set and Map interfaces in Java represent sets
and maps
 The classes HashSet, TreeSet, HashMap, and
TreeMap are implementations
Trees and Binary Trees
 A tree is a non-linear data structure that consists of
zero or more nodes that form a hierarchy
 One node is the root node
 In a binary tree, each node has at most two children,
the right child and left child
 Nodes without children are called leaf nodes
 See Figure 10.4
 A subtree is formed by each child, consisting of the
child and its descendents
Binary Tree Implementation
 A binary tree is a dynamic data structure
 Each node contains data and has references to the
left and right children
 Basic structure:
class TreeNode {
Object value;
TreeNode left;
TreeNode right;
}
 See TreeNode.java (page 549)
Tree Traversal
 There are 3 ways to traverse a tree, that is, to visit
every node:
 Preorder traversal: visit the current node, then
traverse its left subtree, then its right subtree
 Postorder traversal: traverse the left subtree, then
the right subtree, then visit the current node
 Inorder traversal: traverse the left subtree, then visit
the current node, then traverse its right subtree
 Tree traversal is a recursive process
Binary Search Trees
 A binary search tree can be used for storing sorted
data
 For any node N, every node in N’s left subtree must
be less than N, and every node in N’s right subtree
must be greater than or equal to N
 See Figure 10.9
 An inorder traversal of a binary tree visits the nodes
in sorted order
 See SortGrades.java (page 554)
 See BSTree.java (page 555)
 See BSTNode.java (page 557)
Binary Search Trees
 Searching for an element is a recursive process
 If the desired element is less than the current node,
try the left child next
 If the desired element is greater than the current
node, try the right child next
 To insert an element, perform a search to find the
proper spot
 To delete an element, replace it with its inorder
successor
Heaps
 A heap is a complete binary tree in which each parent
has a value less than both its children
 A complete binary tree has the maximum number of
nodes on every level, except perhaps the bottom, and
all the nodes are in the leftmost positions on the
bottom
 See Figures 10.15 and 10.16
 The smallest node in a heap is always at the root
Heaps
 To add a node to a heap, add it in the position that
keeps the tree complete, then bubble it up if
necessary by swapping with its parent until it is not
less than its parent
 See Figures 10.17 and 10.18
 To delete a node from a heap, replace it with the last
node on the bottom level and bubble that node up or
down as necessary
 See Figures 10.19 and 10.20
Heapsort
 A heap can be used to perform a sort
 To do a heapsort, add the elements to a heap, then
remove the elements one-by-one by always removing
the root node
 The nodes will be removed in sorted order
 Heapsort is O(n log n)
Hashtables
 We can handle collisions in hashtables using
chaining or open addressing techniques
 With chaining, each cell in the hashtable is a linked
list and thus many elements can be stored in the
same cell
 See Figure 10.22
Hashtables
 With open addressing techniques, when a collision
occurs, a new hash code is calculated, called
rehashing
 Rehashing continues until a free cell is found
 Linear probing, a simple rehash method, probes
down the hashtable (wrapping around when the end
is reached) until a free cell is found
 See Figure 10.23
Summary
 Chapter 10 has focused on:
•
•
•
•
Sets and maps
Trees and binary search trees
Heaps
Handling collisions in hashtables