10. 2-3-4 Trees and 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 ...

Get Data Structures and Algorithms in Java, 2nd Edition now with the O’Reilly learning platform.

O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.