CSC301.01 2015F, Class 12: Red-Black Trees
==========================================

_Overview_

* Preliminaries.
    * Admin.
    * Upcoming Work.
    * Extra Credit.
    * Questions.
* Balancing (or at least rearranging) binary search trees.
* Red-black tree basics.
* Red-black tree examples.
* Insertion in red-black trees.

Preliminaries
-------------

### Admin

* If things don't show up in the boards, check the .md file and send
  me an email (and send me another email).  

### Upcoming Work

* For Friday: Read CLRS on Red-Black Trees
    * Understand as best you can
    * Mark what you can't understand
* For Next Wednesday: HW 4
    * What kind of homework do you want?  Implementation?  Proof?
      Thought problems?  Reading and reflection?  Correcting someone
      else's incorrect work?

### Extra Credit

#### Academic

* Wednesday CS Extra, 4:15 in 3821: Ursula Wolz on Building
  Coding Communities
* Thursday CS Extra, 4:15 in 3821: SamR on The Architecture of
  Mediascript
* CS Table Tuesday at noon.

#### Peer

* EE Show
* CM Talk - Tuesday at 11am in (population modeling in 502 years) (2517)
* Radio show Friday

### Questions

Balancing (or at least rearranging) balanced trees
--------------------------------------------------

We had

          a (N+2)
         / \
        /   \
     b(N+1) C(N)
      /  \
     /    \
    D(N)  E(N)

We added a node below D which increased its height by 1.

            a (N+3)
           / \
          /   \
       b(N+2) C(N)
        /  \
       /    \
    D(N+1)  E(N)

Questions

* How can we rebalance this a bit?
* What are all of the cases in which adding a node imbalances?
* How do we fix those?

Red-black tree basics
---------------------

* Binary search tree
* That we try to keep mostly balanced - to make search, insert, remove 
  O(logn) (assuming balancing is cheap)
* We color each node red or black.
    * Node colors can switch.
* Red nodes can only have black children
* The root is black
* For any node in the tree, the number of black nodes on a direct path to
  any leaf descendant is identical.  This is the "black height" of a node.

How imbalanced can such a tree be?
How do we compute the black height of a node?

Red-black tree examples
-----------------------

Insertion in red-black trees
----------------------------

We insert in the normal bst model.  We color the new leaf red and then
clean up.

Examples of things we'll have to deal with.  Assume b and r are the old
black and red nodes, and R is the new red node.

               b
              / \
             /   \
            b     b
           / \
          /   \
         r     r
        /
       /
      R