CSC 378: Data Structures and Algorithm Analysis

Red-Black Insertion

Red-Black Insertion

Recall the Red-Black properties:

  1. Every node is either red or black.
  2. If a node has a NULL child, that "child" is considered black.
  3. If a node is red, then both of its children are black.
  4. Every simple path from a node to a descendant NULL child has the same number of black nodes, (including the black NULL child).
  5. 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.


If you were using a Java-enabled Web browser, you would see a binary search tree instead of this paragraph.

Try this: Make the following tree perfectly balanced, using only rotations. Click on any node to rotate about the edge above that node.


If you were using a Java-enabled Web browser, you would see a binary search tree instead of this paragraph.

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:

  1. 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.

  2. 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.

  3. 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 index1.gif .
  • 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 index2.gif rotations in the worst case. Red-Black is better than AVL if rotations are expensive (e.g. if tree is stored on disk) .



Back to the lecture index

Copyright 1998 James Stewart