Chapter Six. Trees

Trees are fundamental structures that arise implicitly and explicitly in many practical algorithms, and it is important to understand their properties in order to be able to analyze these algorithms. Many algorithms construct trees explicitly; in other cases trees assume significance as models of programs, especially recursive programs. Indeed, trees are the quintessential nontrivial recursively defined objects: a tree is either empty or a root node connected to a sequence (or a multiset) of trees. We will examine in detail how the recursive nature of the structure leads directly to recursive analyses based upon generating functions.

We begin with binary trees, a particular type of tree first introduced in Chapter 3. Binary ...

Get An Introduction to the Analysis of Algorithms, Second Edition now with O’Reilly online learning.

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