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 O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.