Quiz 3: Questions

Q3.1.

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

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.

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.

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.

Quiz 3: Solutions

Q3.1.

d h e b i f g c a

Q3.2.

Q3.3.

Q3.4.

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