ABSTRACT
Tree structures are central in computing. In many cases, they are used as data struc-
tures that store information for later retrieval, and often as intermediate constructions
by algorithms. In other cases, trees are used as a backbone for modeling algorithmic
processes, describing the flow of logic and development of computations. For in-
stance, binary search trees are (abstract) models for Quick Sort, and digital trees
serve as models for Radix Exchange Sort. In this chapter we look at these structures.
Many classes of trees have been analyzed under a uniform probability model-
assuming each of the trees taking part in the calculation arises with the same
probability-furnishing a starting point and mathematical convenience. While many
results, both elegant and useful, were derived in this way, our aim in this chapter is to
deal with some nonuniform random trees. This still leaves an enormous scope, and
we therefore limit this chapter to a type we introduced in Chapter 5. Exercise 5.25
is about the uniform recursive tree, and explored the probability space underlying it.
We change here the probability measure to be nonuniform, allowing us to capture
additional applications of such trees. Naturally, we find there are many such possi-
bilities. Additional types of trees are presented in Chapter 8 as tools for data storage
and organization.
