Overview

• Preliminaries.
  • Admin.
  • Upcoming Work.
  • Extra Credit.
• Review.
• Your questions.
• Insertion in red-black trees.
• Deletion in binary-search trees.
• Deletion in red-black trees.

Preliminaries

Admin

• Moment of Silence
• Friday PSA
• UW wants to know:
  • Which of the books do you like more?
    • CLRS has wonderful detail.
    • But boy, proofs!
  • Do you keep your CS textbooks or do you resell?
    • Mostly keep
  • Physical or legal digital?
    • Split
• HW says "Red-Black trees don't normally make intuitive sense at first. They will make more sense after you do 2-3-4 trees."

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.
  • Bring questions on Monday

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). Closing event!
• 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.

Other Good Things

• KDIC interview at 4:30 pm today
• Homecoming football game in Grinnell
• Awesome concert tonight

Review

• What are the key properties of red-black trees?
  • Binary search trees.
  • Red or black nodes.
  • With a black root
  • Red nodes can only have black children / red nodes cannot have red children.
  • Every leaf is black (and holds no value)
  • All the paths from any node to all the leaves below it have the same number of black nodes. This is the black height of the node.
• Why do we care about red-black trees?
  • Height is O(logn)
  • Search will be O(logn), we hope that we can make insert and delete O(logn)
  • More complicated than the alternative; a rite of passage

Your questions

AVL Trees were easy and O(logn). Skip lists were wicked neat and O(logn). Hash tables are expected O(1). Why study another O(logn) dictionary implementation?

Different data structures suited for different situation.

Insertion in red-black trees

• Insert as in binary search trees. We create a new almost-leaf.
• Color it red.
• Check for property violations
  • No: Celebrate! O(logn) insertion
  • Yes: Clean up after ourselves.
• How do we "clean up trees"
  • Rotate a subtree (left or right)
  • Change the color of nodes
  • Do any of the above multiple times (say O(logn))
  • The nuclear option
• The easy situation: The new node is the child of a black node.
• The hard situation. We screwed something up.
  • We didn't change the black length. Yay!
  • The leaves are still all black. Yay!
  • The root is still black, except for the one stupid case in which we had an empty tree. We can fix that easily. RECOLOR THE ONE NODE.
  • No two red nodes in sequence. Probably violated.
• We made a list of the eight possible cases.
• We generalized so that they weren't at the leaf.
• We started to look at how they work in each case.
• Observation one: If the uncle is red, we can swap colors of parent and uncle from red to black. That restores the anti-red-red property.
  
  • However, it changes the black height of the tree.
  • So, we make the grandparent red. At that point, we may need to recurse up the tree.
• Observation two: If we recurse all the way to the root and turn the root red, we can just make the root black, since changing the black height of the whole tree cannot affect ancestors.
• Commentary: We also looked at other approaches. We expect that this is the same thing that the original designers did: Think about each case and how you restore the properties after each step (or get closer to restoring the properties after each step).

Deletion in binary-search trees

• See handout!

Deletion in red-black trees