Chapter 21

Advanced Data Structures


Chapter Goals

Sets

A Set of Printers


Fundamental Operations on a Set

Sets

Set Classes and Interface in the Standard Library

Iterator

Code for Creating and Using a Hash Set

Listing All Elements with an Iterator

Iterator<String> iter = names.iterator();
while (iter.hasNext())
{
   String name = iter.next();
   Do something with name
}
// Or, using the "for each" loop
for (String name : names)
{
   Do something with name
}

File SetTester.java

Output

Add name, Q when done: Dick
{ Dick }
Add name, Q when done: Tom
{ Tom Dick }
Add name, Q when done: Harry
{ Harry Tom Dick }
Add name, Q when done: Tom
{ Harry Tom Dick }
Add name, Q when done: Q
Remove name, Q when done: Tom
{ Harry Dick }
Remove name, Q when done: Jerry
{ Harry Dick }
Remove name, Q when done: Q

Self Check

  1. Arrays and lists remember the order in which you added elements; sets do not. Why would you want to use a set instead of an array or list?
  2. Why are set iterators different from list iterators?

Answers

  1. Efficient set implementations can quickly test whether a given element is a member of the set.
  2. Sets do not have an ordering, so it doesn't make sense to add an element at a particular iterator position, or to traverse a set backwards.

Maps

An Example of a Map

Map Classes and Interfaces

Code for Creating and Using a HashMap

Printing Key/Value Pairs

Set<String> keySet = m.keySet();
for (String key : keySet)
{
   Color value = m.get(key);
   System.out.println(key + "->" + value);
}

File MapTester.java

Output

Romeo->java.awt.Color[r=0,g=255,b=0]
Eve->java.awt.Color[r=255,g=175,b=175]
Adam->java.awt.Color[r=0,g=0,b=255]
Juliet->java.awt.Color[r=255,g=175,b=175]

Self Check

  1. What is the difference between a set and a map?
  2. Why is the collection of the keys of a map a set?

Answers

  1. A set stores elements. A map stores associations between keys and values.
  2. The ordering does not matter, and you cannot have duplicates.

Hash Tables

Sample Strings and Their Hash Codes

String Hash Code
"Adam" 2035631
"Eve" 70068
"Harry" 69496448
"Jim" 74478
"Joe" 74656
"Juliet" -2065036585
"Katherine" 2079199209
"Sue" 83491

Simplistic Implementation of a Hash Table

Simplistic Implementation of a Hash Table

Problems with Simplistic Implementation

Solutions

Hash Table with Buckets to Store Elements with Same Hash Code

Algorithm for Finding an Object x in a Hash Table

  1. Get the index h into the hash table
  2. Iterate through the elements of the bucket at position h
  3. If a match is found among the elements of that bucket, then x is in the set

Hash Tables

Hash Tables

File HashSet.java

File SetTester.java

Output

Harry
Sue
Nina
Susannah
Larry
Eve
Sarah
Adam
Juliet
Katherine
Tony

Self Check

  1. If a hash function returns 0 for all values, will the HashSet work correctly?
  2. What does the hasNext method of the HashSetIterator do when it has reached the end of a bucket?

Answers

  1. Yes, the hash set will work correctly. All elements will be inserted into a single bucket.
  2. It locates the next bucket in the bucket array and points to its first element.

Computing Hash Codes

Computing Hash Codes

A hashCode Method for the Coin Class

A hashCode Method for the Coin Class

class Coin
{
   public int hashCode()
   {
      int h1 = name.hashCode();
      int h2 = new Double(value).hashCode();
      final int HASH_MULTIPLIER = 29;
      int h = HASH_MULTIPLIER * h1 + h2:
      return h
   }
   . . .
}

Creating Hash Codes for your Classes

Creating Hash Codes for your Classes

Hash Maps

File Coin.java

File HashCodeTester.java

Output

hash code of coin1=-1513525892
hash code of coin2=-1513525892
hash code of coin3=-1768365211
Coin[value=0.25,name=quarter]
Coin[value=0.05,name=nickel]

Self Check

  1. What is the hash code of the string "to"?
  2. What is the hash code of new Integer(13)?

Answers

  1. 31 × 116 + 111 = 3707
  2. 13.

Binary Search Trees

A Binary Search Tree

A Binary Tree That Is Not a Binary Search Tree

Implementing a Binary Search Tree

Implementing a Binary Search Tree

public class BinarySearchTree
{
   public BinarySearchTree() { . . . }
   public void add(Comparable obj) { . . . }
   . . .
   private Node root;
   private class Node
   {
      public void addNode(Node newNode) { . . . }
      . . .
      public Comparable data;
      public Node left;
      public Node right;
   }
}

Insertion Algorithm

Example

BinarySearchTree tree = new BinarySearchTree();
tree.add("Juliet"); 
tree.add("Tom"); 
tree.add("Dick"); 
tree.add("Harry"); 

Example


Example Continued

tree.add("Romeo"); 

Insertion Algorithm: BinarySearchTree Class

public class BinarySearchTree
{
   . . .
   public void add(Comparable obj)
   {
      Node newNode = new Node();
      newNode.data = obj;
      newNode.left = null;
      newNode.right = null;
      if (root == null) root = newNode;
      else root.addNode(newNode);
   }
   . . .
}

Insertion Algorithm: Node Class

private class Node
{
   . . .
   public void addNode(Node newNode)
   {
      int comp = newNode.data.compareTo(data);
      if (comp < 0)
      {
         if (left == null) left = newNode;
         else left.addNode(newNode);
      }
      else if (comp > 0)
      {
         if (right == null) right = newNode;
         else right.addNode(newNode);
      }
   }
   . . .
}

Binary Search Trees

Removing a Node with One Child


Removing a Node with Two Children


Binary Search Trees

An Unbalanced Binary Search Tree


File BinarySearchTree.java

Self Check

  1. What is the difference between a tree, a binary tree, and a balanced binary tree?
  2. Give an example of a string that, when inserted into the tree of Figure 10, becomes a right child of Romeo.

Answers

  1. In a tree, each node can have any number of children. In a binary tree, a node has at most two children. In a balanced binary tree, all nodes have approximately as many descendants to the left as to the right.
  2. For example, Sarah. Any string between Romeo and Tom will do.

Tree Traversal

Example

Example

BinarySearchTree Class print Method

public class BinarySearchTree
{
   . . .
   public void print()
   {
      if (root != null)
         root.printNodes();
   }
   . . .
}

Node Class printNodes Method

private class Node
{
   . . .
   public void printNodes()
   {
      if (left != null)
         left.printNodes();
      System.out.println(data);
      if (right != null)
         right.printNodes();
   }
   . . .
}

Tree Traversal

Preorder Traversal

Inorder Traversal

Postorder Traversal

Tree Traversal

A Stack-Based Calculator

A Stack-Based Calculator

A Stack-Based Calculator


Self Check

  1. What are the inorder traversals of the two trees in Figure 14?
  2. Are the trees in Figure 14 binary search trees?

Answers

  1. For both trees, the inorder traversal is 3 + 4 * 5.
  2. No–for example, consider the children of +. Even without looking up the Unicode codes for 3, 4, and +, it is obvious that + isn't between 3 and 4.

Reverse Polish Notation


Using Tree Sets and Tree Maps

To Use a TreeSet

To Use a TreeMap

File TreeSetTester.java


Output
   Coin[value=0.01,name=penny]
   Coin[value=0.05,name=nickel]
   Coin[value=0.25,name=quarter]

Self Check

  1. When would you choose a tree set over a hash set?
  2. Suppose we define a coin comparator whose compare method always returns 0. Would the TreeSet function correctly?

Answers

  1. When it is desirable to visit the set elements in sorted order.
  2. No–it would never be able to tell two coins apart. Thus, it would think that all coins are duplicates of the first.

Priority Queues

Example

Heaps

An Almost Complete Tree


A Heap


Differences of a Heap with a Binary Search Tree

  1. The shape of a heap is very regular
  2. In a heap, the left and right subtrees both store elements that are larger than the root element

Inserting a New Element in a Heap

  1. Add a vacant slot to the end of the tree

Inserting a New Element in a Heap

  1. Demote the parent of the empty slot if it is larger than the element to be inserted

Inserting a New Element in a Heap

  1. Demote the parent of the empty slot if it is larger than the element to be inserted

Inserting a New Element in a Heap

  1. At this point, either the vacant slot is at the root, or the parent of the vacant slot is smaller than the element to be inserted. Insert the element into the vacant slot

Removing an Arbitrary Node from a Heap

  1. Extract the root node value

Removing an Arbitrary Node from a Heap

  1. Move the value of the last node of the heap into the root node, and remove the last node.
    Heap property may be violated for root node (one or both of its children may be smaller).

Removing an Arbitrary Node from a Heap

  1. Promote the smaller child of the root node.
    Root node again fulfills the heap property. Repeat process with demoted child.
    Continue until demoted child has no smaller children. Heap property is now fulfilled again.
    This process is called "fixing the heap".

Removing an Arbitrary Node from a Heap

  1. Promote the smaller child of the root node.
    Root node again fulfills the heap property. Repeat process with demoted child.
    Continue until demoted child has no smaller children. Heap property is now fulfilled again.
    This process is called "fixing the heap".

Heap Efficiency

Storing a Heap in an Array


File MinHeap.java

File HeapTester.java

File WorkOrder.java

Output

priority=1, description=Fix broken sink
priority=2, description=Order cleaning supplies
priority=3, description=Shampoo carpets
priority=6, description=Replace light bulb
priority=7, description=Empty trash
priority=8, description=Water plants
priority=9, description=Clean coffee maker
priority=10, description=Remove pencil sharpener shavings

Self Check

  1. The software that controls the events in a user interface keeps the events in a data structure. Whenever an event such as a mouse move or repaint request occurs, the event is added. Events are retrieved according to their importance. What abstract data type is appropriate for this application?
  2. Could we store a binary search tree in an array so that we can quickly locate the children by looking at array locations 2 * index and 2 * index + 1?

Answers

  1. A priority queue is appropriate because we want to get the important events first, even if they have been inserted later.
  2. Yes, but a binary search tree isn't almost filled, so there may be holes in the array. We could indicate the missing nodes with null elements.

The Heapsort Algorithm

The Heapsort Algorithm

Turning a Tree into a Heap



Turning a Tree into a Heap



Turning a Tree into a Heap



The Heapsort Algorithm

Using Heapsort to Sort an Array


File Heapsorter.java

Self Check

  1. Which algorithm requires less storage, heapsort or mergesort?
  2. Why are the computations of the left child index and the right child index in the HeapSorter different than in MinHeap?

Answers

  1. Heapsort requires less storage because it doesn't need an auxiliary array.
  2. The MinHeap wastes the 0 entry to make the formulas more intuitive. When sorting an array, we don't want to waste the 0 entry, so we adjust the formulas instead.