10. 2-3-4 Trees and External Storage
In This Chapter
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 ...