basecs
Published in

basecs

Painting Nodes Black With Red-Black Trees

I see a red node, and I want it painted black!

A very disciplined tree

Red-black trees: a definition.
Rules of a red-black tree.
  1. Every single node in the tree must be either red or black.
  2. The root node of the tree must always be black.
  3. Two red nodes can never appear consecutively, one after another; a red node must always be preceded by a black node (it must have a black parent node), and a red node must always have black children nodes.
  4. Every branch path — the path from a root node to an empty (null) leaf node — must pass through the exact same number of black nodes. A branch path from the root to an empty leaf node is also known as an unsuccessful search path, since it represents the path we would take if we were to search for a node that didn’t exist within the tree.

a null leaf node is always considered to be a black node, not red.

Fulfilling the rules of a red-black tree.
  1. every node is red or black,
  2. the root node is black,
  3. no two red nodes appear consecutively,
  4. and, finally, the path from the root node to all four null leaf nodes passes through two black nodes (either 2 and then 1, or 2 and then 3) on the way to the null leaves.
A chain of 3 nodes is not possible in a red-black tree.

A chain of three nodes cannot possibly every be a valid red-black tree.

Following the rules of red

How would we insert a new node with a value of 3?

Inserting a node and immediately coloring it red makes it much easier to identify and subsequently fix any violations.

Inserting nodes, continued.
The power of left and right rotations.
Handling insertion and deletion by rotating and recoloring.
Rotate and recolor, no rules are violated.

The benefits of painting it black

The key to dealing with larger red-black trees is moving any rule violations up the tree as we go.

What about inserting into a much larger red-black tree?
Node 16 violates the tree, so it must be rotated.
Now, node 21 is the node that is violating the tree!
In order to finally finish balancing the tree, we need to recolor the root node, 16.
  1. every node is either red or black
  2. the root node is black
  3. no two red nodes appear in a row
  4. every branch path from the root node to any null pointer passes through the same number of black nodes; in this case, we’ll always pass through two black nodes in our tree before hitting a null pointer.
Red-black trees are logarithmically efficient for insertion & deletion given how many rotations they require.
Tracking the color of a node requires only 1 bit of information.

Resources

  1. Coursera Lecture 45 — Red-Black BSTs, Robert Sedgewick
  2. Generic Red-Black Tree, Dr. Richard Wiener
  3. Red-Black Trees, Professor Jim Skrentny
  4. Red/Black Tree Visualization, Professor David Galles
  5. Red-Black Tree Introduction, GeeksforGeeks

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store