O'Reilly logo

Learning Functional Data Structures and Algorithms by Raju Kumar Mishra, Atul Khot

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

Red-Black trees

Given this rotation algorithm, we can now look at the core Red-Black tree.

A Red-Black tree node always has a color, either red or black, with the following invariants:

  • A red node can never have a red child
  • Every path from the root to an empty node contains the same number of black nodes

An empty node is a leaf nil node. This nil node indicates termination and is also known as a sentinel node.

Here is an example of a Red-Black tree. Note that each node is annotated with its black height. The black height is the number of black nodes from the node to the leaf.

Note these important points:

  1. The root is always black.
  2. Every leaf is black.
  3. Both the children of a red node are black (as a red node cannot have a red child).
  4. Every path from a node ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required