Quiz 3

Problem Q3.1.

[6 pts] Write the post-order traversal of the tree at right.

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 red-black 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();
}