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 ...

Get Data Structures & Algorithms in Python now with the O’Reilly learning platform.

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