Overview

• Preliminaries.
  • Admin.
  • Upcoming Work.
  • Extra Credit.
  • Questions.
• Key ideas from insertion.
• Deletion in binary search trees.
• Deletion in red-black trees.

Preliminaries

Admin

• 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.
• Exam to be distributed soon, due Friday the 9th.

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
• Publication fair noon tomorrow.

Questions

Deletion is confusing

We'll work through some of it today.

Problem 13.3-6

The RB-INSERT and RB-INSERT-FIXUP procedures often refer to x.p or x.p.p (or something equivalent). That suggests that the underlying implementation stores a parent pointer in each node. p means parent, at least in this context.

Real data structures try to conserve space. Do I really need the parent pointer? Can I write fixup without it? Yes, you can do the stupid "search the whole tree for the parent". But that's not efficient. So find an efficient approach. * Note: You may need to gather information during insert to use during fixup.

Key ideas from insertion

• The algorithm.
• Common design technique for data structures (often related to trees or graphs):
  • Set restrictions on the organization of the data structure (these restictions give us some useful broader property)
  • Write "natural" algorithms for the data structure
  • Identify violations of the restrictions
  • Repair violations
• It's not easy.
• Breaking into separate cases is often important.
• Sometimes you solve one case by transforming it into another case.

Deletion in binary search trees

Some simple cases (removing z)

        |
        z      =>  NIL
       / \    
     NIL NIL

        |         |
        z      => r
       / \       / \
     NIL  r     ?   ?
         / \
        ?   ?


        |         |
        z      => l
       / \       / \
      l  NIL    ?   ?
     / \
    ?   ?

        z     =>  y
       / \       / \
      l   y     l   x
         / \
       NIL  x

        z     =>           z          =>     y
       / \                / \               / \
      l   r              l   y             l   r
         / \                / \               / \
        .   ?             NIL  r             .
       .                      / \           .
      .                      .   ?         .
     y                      .             x
    / \                    .             
  NIL  x                  x

Deletion in red-black trees

        |
        z      =>  NIL
       / \    
     NIL NIL

• If z is red, we don't care about black height.
• If z ib black, we need to fix the black height (somehow)
• Doesn't break red-black property.

        |         |
        z      => RED
       / \       / \
     NIL RED   NIL NIL
         / \
       NIL NIL

• z could not have been red
• We've broken the black height
• We might have broken the red-black property.
• Let's turn red to black. We've fixed the red-black property. We've fixed the black height property. Life is good.

        z     =>  y
       / \       / \
      l   y     l   x
         / \
       NIL  x

• If z is red, l and y must be black, x must be red or NIL y has a black height of 1, x must have a black height of 1, l must have a black height of 1
  • z has a black height of 2
  • The revised version has a black height of 1
  • We've broken the black height again
• If z is black, l and y have the same black height We'll probably have to ask whether y is red or black
• This is going to fit into the more general analysis.

        z     =>           z          =>     y
       / \                / \               / \
      l   r              l   y             l   r
         / \                / \               / \
        .   ?             NIL  r             .
       .                      / \           .
      .                      .   ?         .
     y                      .             x
    / \                    .             
  NIL  x                  x

The main thing to fix: We've broken the black height property by 1. We need to fix it. Identify cases and do clever rotations and recolorings.