The Essentials of Computer Organization and Architecture, 6th Edition

A.3 TREES

Queues, stacks, and arrays are useful for processing lists of things where the locations of the items in the list (relative to each other) do not change no matter how many items are in the list. Certainly, this is not the nature of many of the data collections that we use in our daily lives. Consider a program that would manage an address book. One useful way of sequencing this data is to keep the list in order by last name. A binary search could quickly locate any name in the list, successively limiting the search to half the list. A binary search is shown seeking the name Kleene in the list of famous mathematicians in Figure A.2. We begin by determining the middle of the list (Hilbert) and comparing this value to our key. If they ...