CS 70

Red–Black Tree Insert

  • LHS Cow speaking

    Now we have all the tools we need to perform red–black tree insertions.

  • Dog speaking

    Let's do it!!

Insertion in a red–black tree involves traveling down the tree to a leaf (just like in a regular BST) and also, at each node on the way:

  • Possibly performing a rotation; and
  • Possibly changing some node colors.

The color changes correspond to promotions in the corresponding 2–3–4 tree, and rotations ensure that 4-nodes always have the proper shape with a red node on each side, not two red nodes on one side.

Practice

Now it's your turn!

Here's the tree we ended up with on the previous page:

Starting from that tree, draw out the tree as you insert the following values:

  • 60
  • 70
  • 80
  • 90
  • 100

Write down what rotations and color changes you're performing as you go.

Big Hint

  • Perform each operation in a 2–3–4 tree step-by step.
  • Translate each step into its red–black tree equivalent.
  • Figure out what would cause each rotation (if any) and color change (if any).

Across all of those insertions, how many times did you perform a rotation?

Correction @ 8:28: (40 | 60) is a 3-node and (40 | 60 | 80) is a 4-node.

(When logged in, completion status appears here.)