Published in

basecs

A very disciplined 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.

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 three nodes cannot possibly every be a valid red-black tree.

Following the rules of red

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

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.

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.

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

--

--

More from basecs

Exploring the basics of computer science, every Monday, for a year.

Get the Medium app

Writing words, writing code. Sometimes doing both at once.