Held: Monday, 28 September 2015

Back to Outline 13 - Red-Black Trees, Continued. On to Outline 15 - 2-3 Trees.

Summary

We finish our consideration of red-black trees by exploring ways to delete from red-black trees.

Related Pages

Overview

• Key ideas from insertion.
• Deletion in binary search trees.
• Deletion in red-black trees.

Administrivia

• Most of these algorithms will make much more sense if you sketch them out by hand.
• My class model is that they also make more sense if you try to do them yourself first.

Upcoming Work

• 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

• Don't forget that you can send these to me in advance!

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

Key Ideas from Insertion

• A common strategy for developing data structure: Place some requirements on the data structure, look at the requirements that are violated after certain operations, figure out how to restore those requirements.
• Note that we relied on something very much like loop invariants
  • The "black height" property was restored after every step.
  • The "red-black" proeprty held below each point.
  • At every "step", we move higher in the tree.
• These ideas do not come easily. It is like mathematics in that way ... you try something. You may seem to move forward. But you then hit a dead end. So you back up, and try something again, and again, and again.
• Sometimes you solve some cases one way and solve the rest by transforming into already solved cases.

Deleting from BSTs

• Some deletions are easy (typically near leaves), some are not so easy.
• Multiple approaches.
  • There's one I taught my students
  • CLRS show a general one that seems more efficient.

Deleting from Red-Black Trees

• The scary line: "Deleting a node from a red-black tree is a bit more complicated than inserting a node."
• But it's not too bad, as long as we keep track of all of the details.