CSC301.01 2015F, Class 14: Red-Black Trees, Concluded
=====================================================
_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.