Recall the Red-Black properties:
- Every node is either red or black.
- If a node has a NULL child, that "child" is considered black.
- If a node is red, then both of its children are black.
- Every simple path from a node to a descendant NULL child has the same number
of black nodes, (including the black NULL child).
- The root is black.
Examples of Insertion
How should a newly-inserted node be coloured? Property III
requires the same number of black nodes on all full paths. Property
IV insists that no two red nodes be adjacent. Here's a colouring that
satisfies the properties (where NULL children are shown as square
nodes):
How to insert 8 into the tree?
To
satisfy Properties III and IV, 8 must be red.
In general, a new node must always be red, otherwise some path has
an extra black node.
Now how to insert 11?
Property
III is violated (11 and 12 will be adjacent reds).
To fix this, recolour the nodes: "Move" 9's black colour down to
its two children:
Can we insert 10?
NO! There
is no way to colour this tree to satisfy all properties!
Therefore, the tree must somehow be restructured!
Restructuring With Rotations
Here's how we'll alter the shape of the BST without violating the
BST ordering of nodes. This is called ``rotation'', since one edge of
the tree is rotated.
Note that BST ordering is preserved by rotation!
The following procedure does a rotation about the edge
above x. The first part does a right rotation; the second
part (not shown) does a left rotation.
Rotate(x)
y = parent(x)
z = parent(y) // = NULL if y is root
if x == left(y)
// right rotation
beta = right(x)
left(y) = beta
right(x) = y
if z == NULL // if y was root, now x is root
root = x
else if y == right(z)
right(z) = x
else
left(z) = x
parent(x) = z
parent(y) = x
if beta != NULL
parent(beta) = y
else
// left rotation
...
This produces the following:
Try this: Click on 15 below to see what happens when rotating
about the edge above 15. Then click on 42.
Try this: Make the following tree perfectly balanced, using
only rotations. Click on any node to rotate about the edge above that
node.
Continuing with Red-Black Insertion:
Here's the outline of our Red-Black insertion procedure:
Idea: Insertion might violate Property III, so we first fix the
problem at x, and then move up the tree to correct any new violations
that the fixing caused above x.
The pointer x should always point to the current violation, not to
the inserted node. Everything below x should satisfy the Red-Black
properties!
Conditions for a Property III violation at x
colour( x ) = red
colour( P( x ) ) = red
parent( x ) != root (since root is always black)
colour( L( x ) ) = black
colour( R( x ) ) = black
colour( P( P( x ) ) ) = black
colour( sibling of x ) = black
Tree structure for a Property III Violation at x
Cases that must be fixed inside the WHILE loop
Consider the sibling of x's parent (i.e. x's uncle/aunt). There
are several situations that might occur:
- Uncle/Aunt is Red
Solution: Move black colour down from P(P(x)). Then point x to
P(P(x)).
All paths still have the same number of black nodes (good). Now go
back to the top of the 'while' loop.
This works for structures I, II, III, and IV.
- Uncle / Aunt is Black
x is a left child, P( x ) is a left child
Solution: Rotate P(x). Then colour x red, P(x) black, and the
sibling of x red.
Note that the black height of each subtree is unchanged! Since
subtree at y is now black, there is no Property III violation above y,
which means that we're done, and x does not move up.
This works for structure I only. A symmetric operation works for
structure III.
- Uncle / Aunt is Black
x is a right child, P( x ) is a left child
Solution:
Now it's case II, and can be handled with the code for case II!
This works for structure II only. A symmetric operation works for
structure IV.
Comments on Red-Black Insertion
- We might recolour all the way up to the root, so time is in
.
- At most two rotations are performed (case III, then case II), after which
no violation exists.
- Another balanced tree, called the AVL tree, can use
rotations in the worst case. Red-Black is better than AVL if
rotations are expensive (e.g. if tree is stored on disk) .