Data Structures and Algorithms in Java, 2nd Edition

10. 2-3-4 Trees and External Storage

In This Chapter

• Introduction to 2-3-4 Trees

• Java Code for a 2-3-4 Tree

• 2-3-4 Trees and Red-Black Trees

• Efficiency of 2-3-4 Trees

• 2-3 Trees

• External Storage

In a binary tree, each node has one data item and can have up to two children. If we allow more data items and children per node, the result is a multiway tree. 2-3-4 trees, to which we devote the first part of this chapter, are multiway trees that can have up to four children and three data items per node.

2-3-4 trees are interesting for several reasons. First, they’re balanced trees like red-black trees. They’re slightly less efficient than red-black trees but easier to program. Second, and most important, they serve as an easy-to-understand ...