|
Productivity experts say that breakthroughs come by thinking ``nonlinearly.'' In this chapter, we discuss one of the most important nonlinear data structures in computing--trees. Tree structures are indeed a breakthrough in data organization, for they allow us to implement a host of algorithms much faster than when using linear data structures, such as list, vectors, and sequences. Trees also provide a natural organization for data, and consequently have become ubiquitous structures in file systems, graphical user interfaces, databases, Web sites, and other computer systems. It is not always clear what productivity experts mean by `nonlinear' thinking, but when we say that trees are nonlinear, we are referring to an organizational relationship that is richer than the simple `before' and `after' relationships between objects in sequences. The relationships in a tree are hierarchical, with some objects being `above' and some `below' others. Actually, the main terminology for tree data structures comes from family trees, with the terms `parent,' `child,' `ancestor,' and `descendent' being the most common words used to describe relationships. We show an example of a family tree below:
|