2 The Table ADT

Most of the chapters in this book implement a table structure as some kind of binary tree, so it is important to understand what a table is before we begin. That is this chapter's purpose.

This chapter begins with a brief definition of the meaning of “table” for the purposes of this book, then moves on to describe in a more formal way the interface of a table used by all of the tables in this book. The next chapter motivates the basic idea of a binary tree starting from simple, everyday concepts. Experienced programmers may skip these chapters after skimming through the definitions below.