Held: Friday, 25 September 2015

Back to Outline 12 - Red-Black Trees. On to Outline 14 - Red-Black Trees, Concluded.

Summary

We continue our exploration of red-black trees.

Related Pages

Overview

• Review.
• Your questions.
• Insertion in red-black trees.
• Deletion in binary-search trees.
• Deletion in red-black trees.

Administrivia

• Moment of Silence
• Friday PSA
• UW wants to know:
  • Which of the books do you like more?
  • Do you keep your CS textbooks or do you resell?

Upcoming Work

• For Monday: Review CLRS on Red-Black Trees
• For Wednesday: HW 4. CLRS 13.3-2, 13.3-5, 13.3-6, 13.4-3, 13.4-5, 13.4-7. 13-2.

Extra Credit

Academic

• CS Table Tuesday at noon: YouTube Takedowns.
• CS Extra Thursday at 4:15 p.m.: PMO and CC on Grad School.

Peer

• EE Show (one more week).
• CM Talk on Population Modeling - Tuesday at 11am in 2517
• Radio show Friday
• Soccer matches Saturday, women at 11, men at 1:30
• Orchestra concert Saturday, 2:00 in S-L.
• Jazz concert Saturday, 7:30 in S-L.

Review

• What is a red-black tree?
• Why do we care about them?
  • Depth is O(logn)
• What are the key operations?
  • Lookup
  • Insert
  • Delete
• What is the likely model for insert?
• What is the likely model for delete?

Student Questions

• What parts of the reading made the least sense?

Insertion in Red-Black Trees

• We start by inserting using the normal BST insertion algorithm.
• We color the resulting node red.
• What properties might we have violated?
  • If we inserted at the root, we've violated the "black root" property.
  • If we inserted at a leaf, we might have violated the "red parents don't have red children" property.
  • Adding a red node should not change the number of black nodes on a path from node to leaves.
• What are the approaches we can use to make the tree closer to meeting the red-black criteria?
  • We can recolor nodes
  • We can rotate parts of the tree left or right
• What are the different cases in which trees might violate the "no two red nodes in sequence" property?
  • CLRS list three cases, but there are really eight cases (with some symmetry).

01       b
       /   \
      r     r
     / \   / \
    ?   R ?   ?
       / \
      ?   ?

02       b
       /   \
      r     r
     / \   / \
    R   ? ?   ?
   / \
  ?   ?

03       b
       /   \
      r     b
     / \   / \
    ?   R ?   ?
       / \
      ?   ?

04       b
       /   \
      r     b
     / \   / \
    R   ? ?   ?
   / \
  ?   ?

05       b
       /   \
      r     r
     / \   / \
    ?   ? R   ?
         / \
        ?   ?

06       b
       /   \
      r     r
     / \   / \
    ?   ? ?   R
             / \
            ?   ?

07       b
       /   \
      r     r
     / \   / \
    ?   ? R   ?
         / \
        ?   ?

08       b
       /   \
      r     r
     / \   / \
    ?   ? ?   R
             / \
            ?   ?

• The last four are symmetrical, so we won't process them?
• What are the black heights of the unnamed subtrees (or all the subtrees)?
• How do we change each?

Deletion in Binary Search Trees

• What do you remember?
• Handout!

Deletion in Red-Black Trees

• Complicated!