Cover Data Structures and Algorithms with Object-Oriented Design Patterns in Java
next up previous contents index

Solving The Recurrence-Telescoping

This section presents a technique for solving recurrence relations such as Equation gif called telescoping . The basic idea is this: We rewrite the recurrence formula so that a similar functional form appears on both sides of the equal sign. For example, in this case, we consider n>2 and divide both sides of Equation gif by n+1 to get

displaymath63500

Since this equation is valid for any n>2, we can write the following series of equations:

   eqnarray18308

Each subsequent equation in this series is obtained by substituting n-1 for n in the preceding equation. In principle, we repeat this substitution until we get an expression on the right-hand-side involving the base case. In this example, we stop at n-k-1=2.

Because Equation gif has a similar functional form on both sides of the equal sign, when we add Equation gif through Equation gif together, most of the terms cancel leaving

eqnarray18355

where tex2html_wrap_inline63514 is the tex2html_wrap_inline57406 harmonic number . In Section gif it is shown that tex2html_wrap_inline63518, where tex2html_wrap_inline63520 is called Euler's constant . Thus, we get that the average internal path length of the average binary search tree with n internal nodes is

eqnarray18383

Finally, we get to the point: The average depth of a node in the average binary search tree with n nodes is

eqnarray18385


next up previous contents index

Bruno Copyright © 1998 by Bruno R. Preiss, P.Eng. All rights reserved.