Data Structures & Algorithms in Python

9. 2-3-4 Trees and External Storage

In This Chapter

• Introduction to 2-3-4 Trees

• The Tree234 Visualization Tool

• Python Code for a 2-3-4 Tree

• 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 you allow more data items and children per node, the result is a multiway tree. A 2-3-4 tree, to which we devote the first part of this chapter, is a multiway tree that can have up to four children and three data items per node.

These 2-3-4 trees are interesting for several reasons. First, they’re balanced trees designed to avoid the problems that come from having too many nodes along some of the paths in the tree. Second, there’s an interesting way to convert ...