An Introduction to the Analysis of Algorithms by Robert Sedgewick

Author:Robert Sedgewick [Sedgewick, Robert]
Language: eng
Format: epub
Published: 2014-01-22T15:08:23+00:00

§ .

T

6.7 Average Path Length in Random Catalan Trees. To begin our

analysis of tree parameters, we consider the model where each tree is equally

likely to occur. To avoid confusion with other models, we add the modi er

Catalan to refer to random trees under this assumption, since the probability

that a particular tree occurs is the inverse of a Catalan number.

is model is

a reasonable starting point for many applications, and the combinatorial tools

developed in Chapters 3 and 5 are directly applicable in the analysis.

Binary Catalan trees. What is the average (internal) path length of a binary

tree with N internal nodes, if each N -node tree is considered to be equally

likely? Our analysis of this important question is prototypical of the general

approach to analyzing parameters of combinatorial structures that we considered in Chapters 3 and 5:

• De ne a bivariate generating function (BGF), with one variable marking the size of the tree and the other marking the internal path length.

• Derive a functional equation satis ed by the BGF, or its associated cumulative generating function (CGF).

• Extract coefficients to derive the result.

We will start with a recurrence-based argument for the second step, because

the underlying details are of interest and related to familiar problems. We

know from Chapter 5 that direct generating-function-based arguments are

available for such problems. We shall consider two such derivations in the

next subsection.

To begin, we observe that the probability that the left subtree has k

nodes (and the right subtree has N −k −1 nodes) in a random binary Catalan

( )

tree with N nodes is T

2N

k TN −k−1/TN (where TN =

/ (N +1) is the Nth

N

Catalan number).

e denominator is the number of possible N -node trees

and the numerator counts the number of ways to make an N -node tree by

using any tree with k nodes on the left and any tree with N − k − 1 nodes on

the right. We refer to this probability distribution as the Catalan distribution.

Figure 6.14 shows the Catalan distribution as N grows. One of the

striking facts about the distribution is that the probability that one of the

subtrees is empty tends to a constant as N grows: it is 2TN−1/TN ∼ 1/2.

Random binary trees are not particularly well balanced.

One approach to analyzing path length in a random binary tree is to

use the Catalan distribution to write down a recurrence very much like the

one that we have studied for quicksort: the average internal path length in a

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.