printable version
Quiz 3
[1]
[2]
[3]
[4]
Problem Q3.1.
[6 pts]
Write the postorder traversal of the tree at right.
d h e b i f g c a
Problem Q3.2.
a. [6 pts]
Draw the tree resulting from inserting 8 into the
binary search tree at right,
using the algorithm described in class.
b. [6 pts]
Draw the tree resulting from deleting 4 from the
binary search tree at left (before inserting 8),
using the algorithm described in class.
a. 

b. 

Problem Q3.3.
[6 pts]
Suppose we have a redblack tree as diagrammed at right,
and then
we insert 4 using the insertion algorithm discussed in class.
Diagram the resulting tree, indicating which nodes are red and
which are black.
Problem Q3.4.
[6 pts]
Using Java's syntax for defining interfaces, define the
Map
interface as it exists in the
java.util
package. Your definition should include at least four of the six
methods we saw in class.
public interface Map<K,V> {
public E get(K key);
public E put(K key, V value);
public E remove(K key);
public boolean containsKey(K key);
public int size();
public Set<K> keySet();
}