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