Deletion from Red-Black Trees - Purdue University
CS 21: Red Black Tree Deletion
February 25, 1998
Deletion from Red-Black Trees
E
C
RR
B
DO
U
S
X
erm
12.235
CS 21: Red Black Tree Deletion
February 25, 1998
Setting Up Deletion
As with binary search trees, we can always delete a node that has at least one external child
If the key to be deleted is stored at a node that has no external children, we move there the key of its inorder predecessor (or successor), and delete that node instead
Example: to delete key 7, we move key 5 to node u, and delete node v
7u
5u
4
8
v
25
9
4
8
2
9
erm
12.236
CS 21: Red Black Tree Deletion
February 25, 1998
Deletion Algorithm
1. Remove v with a removeAboveExternal operation
2. If v was red, color u black. Else, color u double black.
v
u
u
v
u
u
3. While a double black edge exists, perform one of the following actions ...
erm
12.237
CS 21: Red Black Tree Deletion
February 25, 1998
How to Eliminate the Double Black Edge
? The intuitive idea is to perform a "color compensation''
? Find a red edge nearby, and change the pair ( red , double black ) into ( black , black )
? As for insertion, we have two cases: ? restructuring, and ? recoloring (demotion, inverse of promotion)
? Restructuring resolves the problem locally, while recoloring may propagate it two levels up
? Slightly more complicated than insertion, since two restructurings may occur (instead of just one)
erm
12.238
CS 21: Red Black Tree Deletion
February 25, 1998
Case 1: black sibling with a red child
? If sibling is black and one of its children is red, perform a restructuring
p vs
s pz
z
v
p vs
z
z
p
s
v
erm
12.239
................
................
In order to avoid copyright disputes, this page is only a partial summary.
To fulfill the demand for quickly locating and searching documents.
It is intelligent file search solution for home and business.
Related download
- tutorial openrefine umd
- pyroot tutorial python
- chapter 2 lists arrays and dictionaries
- university of california berkeley college of
- python tutorial stanford artificial intelligence
- deletion from red black trees purdue university
- programming for gcse topic 6 1 lists arrays and
- lecture 12 doubly linked lists and recursion
Related searches
- red and black invitation template
- red white black wedding invitations
- red and black wedding invitations
- red white and black wedding
- black and red birthday invitations
- black and red wedding
- red and black wedding reception
- black and red wedding invitations
- red black and silver wedding
- red black silver wedding invitations
- red black white wedding invitations
- red black white wedding ideas