Red-Black Tree Operations
Learn to add and remove an element in red-black trees.
We'll cover the following...
Addition
To implement add(x)
in a RedBlackTree
, we perform a standard BinarySearchTree
insertion to add a new leaf, u
, with u.x = x
and set u.colour = red
. Note that this does not change the black height of any node, so it
does not violate the black-height property. It may, however, violate the
left-leaning property (if u
is the right child of its parent), and it may
violate the no-red-edge property (if u
’s parent is red). To restore these
properties, we call the addFixup(u)
method.
boolean add(T x) {Node < T > u = newNode(x);u.colour = red;boolean added = add(u);if (added)addFixup(u);return added;}
A single round in the process of fixing Property 2 after an insertion is illustrated in figure below:
The addFixup(u)
method takes as input a
node u
whose colour is red and which may violate the no-red-edge property and/or the left-leaning property. The following discussion is probably impossible to follow without referring to Figure 9.8 or recreating it on
a piece of paper. Indeed, the reader may wish to study this figure before
continuing.
If u
is the root of the tree, then we can colour u
black to restore both
properties. If u’s sibling is also red, then u
’s parent must be black, so both
the left-leaning and no-red-edge properties already hold.
Otherwise, we first determine if u
’s parent, w
, violates the left-leaning
property and, if so, perform a flipLeft(w)
operation and set u = w
. This leaves us in a well-defined state: u
is the left child of its parent, w
, so w
now satisfies the left-leaning property. All that remains is to ensure the no-red-edge property at u
. We only have to worry about the case in which
w
is red, since u
already satisfies the no-red-edge property.
We are not done yet, u
is red and w
is red. The no-red-edge property (which is only violated by u
and not by w
) implies that u
’s grandparent g
exists and is black. If g
’s right child is red, then the left-leaning
property ensures that both g
’s children are red, and a call to pushBlack(g)
makes g
red and w
black. This restores the no-red-edge property at u
, but may cause it to be violated at g, so the whole process starts over with
u = g
.
If g’
s right child is black, then a call to flipRight(g)
makes w
the
(black) parent of g
and gives w
two red children, u
and g
. This ensures
that u
satisfies the no-red-edge property and g
satisfies the left-leaning property. In this case, we can stop.
void addFixup(Node < T > u) {while (u.colour == red) {if (u == r) { // u is the root - doneu.colour = black;return;}Node < T > w = u.parent;if (w.left.colour == black) { // ensure left-leaningflipLeft(w);u = w;w = u.parent;}if (w.colour == black)return; // no red-red edge = doneNode < T > g = w.parent; // grandparent of uif (g.right.colour == black) {flipRight(g);return;} else {pushBlack(g);u = g;}}}
The insertFixup(u)
method takes constant time per iteration and each iteration either finishes or moves u
closer to the root. Therefore,
the insertFixup(u)
method finishes after iterations in time.
Removal
The remove(x)
operation in a RedBlackTree
is the most complicated to
implement, and this is true of all known red-black tree variants. Just
like the remove(x)
operation in a BinarySearchTree
, this operation boils
down to finding a node w
with only one child, u
, and splicing w
out of the
tree by having w.parent
adopt u
.
The problem with this is that, if w
is black, then the black-height
property will now be violated at w.parent
. We may avoid this problem, temporarily, by adding w.colour
to u.colour
. Of course, this introduces two other problems: (1) if u
and w
both started out black, then
u.colour
+ ...