2-3-4 Search Trees

In practice: For every 2-4 tree, there are corresponding red–black trees with data elements in the same order. The insertion and deletion operations on 2-4 trees are also equivalent to color-flipping and rotations in red–black trees. This makes 2-4 trees an important tool for understanding the logic behind red–black trees, and this is why many introductory algorithm texts introduce 2-4 trees just before red–black trees, even though 2-4 trees are not often used in practice.

Visit the following resources to learn more:

• @article@CS 61B Lecture 26: Balanced Search Trees
• @video@Bottom Up 234-Trees
• @video@Top Down 234-Trees