Trees, Persistence and Iterators

Due: written by 5pm Tuesday 2/21, program by 9pm

Homework 2

Written Part

Try to solve these problems, and write out solutions on paper.

1

Consider a left-leaning red-black BST, as defined by our textbook. Argue that for any $k$, there is a situation where a single insertion requires at least $k$ rotations. (If you cannot do this, at least try for $k=3$.) Try to upper-bound $N$, the number of keys in your example, in terms of $k$. (Hint: see the ``movies'' near the end of the online lecture notes.)

2

Look up persistent data structures, outside our book. State the distinction between ``fully persistent'' and ``partially persistent''. Which kind of persistence are we implementing in PRedBlackBST? Look up the paper ``Planar point location using persistent search trees'' by Sarnak and Tarjan (1986). (In Emory's network, you can get the full text at dl.acm.org.) What kind of persistence do they implement, and how much space do they need per tree update (insert or delete)?

3

Look into the ``Java Collections'' documentation. Explain what it means for an iterator to be ``fail fast''. Skim the source of java.util.TreeMap (see 0206/TreeMap.java). What is the modCount field, and explain how it is used to help detect situations where an iterator should fail. (Hint: search for the exception that an iterator should throw on failure.)

Program Part (sketch)

You will implement insertion (the ``put'' method) for persistent left-leaning red-black trees. We implement the path-copying method, which needs $O(\lg n)$ space per insertion. (In fact the same claim could be made for deletion, but we are not implementing that). For extra credit, you can also implement a stack-based iterator.

For further details, see the files in hw2/. I hope to improve the test driver.

Honor Policy

Your work for this class is governed by the Emory Honor Code. Programming work is also governed by the Math/CS SPCA (Statement of Policy on Computer Assignments). In particular, you should take care to protect the confidentiality of your homework files. Apparent honor code violations will be referred to the Emory Honor Council. If you have questions about what is allowed under the policy, please ask.