Reminders:

hw1 written was due yesterday, the hw1 program is due 9pm Tuesday.
"turnin" is not working yet, I intend to get that done (and announced
by email) this evening.  For those new to bluej, I'm willing to
demonstrate some basic tricks (like how to get it compiling, and how
to invoke ErdosRenyi.main()).

Lecture:

Last time we introduced 2-3 trees, with search and insertion (using
temporary 4-nodes).  We also introduced the left-leaning red-black
BST, as a BST representing a 2-3 tree.

Today we continue with red-black trees.  We start by sketching
some elementary tree operations:
    rotations (which some of you have seen with AVL trees)
    color flipping

Next, some pretty stuff (animations):
    33DemoRedBlackBST.mov -- slow animation of insertions
      In particular we note:
         Right-leaning 3-nodes are "rotated" to left-leaning.
         Temporary 4-nodes are first put into a "balanced" form
         (two sibling red edges under the middle key), and then
         we simply recolor edges to promote the middle key up.
    I'm not sure if we'll have time for it, but there are three
    nice "fast" animations of 255 insertions into a red-black BST
    (in random order, increasing, or decreasing) near end of:
      http://algs4.cs.princeton.edu/33balanced/

Then, some uglier stuff, source code:
     ../book/RedBlackLiteBST.java  -- red-black BST, ST (no deletion)
     In particular we'll look at the basic tree operations, and put.
     Various extra elements make this program a bit long:
         Java generics, the two type parameters (Key and Value)
         "assert check()", methods checking correctness (BST, 2-3, balance)

To compile and run this example code (with a little output):
     cd ../book
     export CLASSPATH='.:*'
     javac RedBlackLiteBST.java
     java -ea RedBlackLiteBST      # -ea enables assertion checking
     java RedBlackLiteBST 15       # insert 0, 1, 2, .., 15