Transcript PPT Chapter 10 Non- Linear Data Structures

Chapter 10: Non-linear Data Structures
Presentation slides for
Java Software Solutions
for AP* Computer Science A
2nd Edition
by John Lewis, William Loftus, and Cara Cocking
Java Software Solutions is published by Addison-Wesley
Presentation slides are copyright 2006 by John Lewis, William Loftus, and Cara Cocking. All rights
reserved.
Instructors using the textbook may use and modify these slides for pedagogical purposes.
*AP is a registered trademark of The College Entrance Examination Board which was not involved in
the production of, and does not endorse, this product.
© 2006 Pearson Education
Non-linear Data Structures
 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
© 2006 Pearson Education
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
© 2006 Pearson Education
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
 A subtree is formed by each child, consisting of the
child and its descendents
© 2006 Pearson Education
A Tree
© 2006 Pearson Education
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 557)
© 2006 Pearson Education
Binary Tree Implementation
© 2006 Pearson Education
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
© 2006 Pearson Education
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
 An inorder traversal of a binary tree visits the nodes
in sorted order
 See SortGrades.java (page 562)
 See BSTree.java (page 563)
 See BSTNode.java (page 565)
© 2006 Pearson Education
A Binary Search Tree
© 2006 Pearson Education
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
© 2006 Pearson Education
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
 The smallest node in a heap is always at the root
© 2006 Pearson Education
Adding to a Heap
 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
© 2006 Pearson Education
Deleting from a Heap
 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
© 2006 Pearson Education
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)
© 2006 Pearson Education
Implementing Heaps
 Heaps are often implemented using lists since it is
more convenient to add and delete items
 The children of the ith element are the 2ith and 2i+1th
elements in the list
© 2006 Pearson Education
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
© 2006 Pearson Education
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 Guests.java (page 586)
© 2006 Pearson Education
Summary
 Chapter 10 has focused on:
•
•
•
•
Sets and maps
Trees and binary search trees
Heaps
Handling collisions in hashtables
© 2006 Pearson Education