Technical Headaches:

   This weekend I had technical problems with the turnin procedure, so
   I'll go over an email announcement.  Basically, for hw1 you can
   just leave your sol.jar in your ~/cs323/hw1/.  I'll take a snapshot
   of those files at 9pm tomorrow (Tuesday).  Remember to "include
   source" when you build your jar file.

Expect hw2 soon, probably Wednesday.

I'll offer to go over solutions to the hw1 written problems, if
there is interest.

We resume discussing red-black trees.  First, it seemed that there
were a couple of 4-node restructuring cases were not covered by the
insert method in ../book/RedBlackLiteBST.java, but now we'll see that
those cases cannot occur.

Next we'll talk about strategies for deletion in a red-black tree.
The basic idea, in terms of a 2-3 tree: never step into a 2-node
(the current node is always a 3-node or a temporary 4-node).
This will require "borrowing from siblings", and sending a key
down (opposite of split); then on way back up, eliminate 4 nodes.

Details: pages 441-443

This gets somewhat complicated when we translate it back to a
red-black tree, just for a taste we may look at the recursive delete
method in RedBlackBST.java.  But this is hard code, we won't have time
to go through the details.

However let me point out that in this fancier class, each node also
maintains a .N field, the size of its subtree.  We'll look at how this
extra information supports fast "rank" and "select" operations.  That
is, find the key with rank i, or count the keys less than a given k.

This code is complicated, but just for comparison let us compare it to
TreeMap.java (java.util.TreeMap is also a red-black tree with
key-value pairs, its source code is available from
http://www.docjar.com/src/api/java/util/TreeMap.java).

TreeMap is quite a bit longer, even after stripping javadoc comments:
$ decomment < RedBlackBST.java | wc
    506    2127   15827
$ decomment < TreeMap.java | wc
   1842    5190   57220

We might consider the reasons for this difference, if there is time.