Logo Data Structures and Algorithms with Object-Oriented Design Patterns in C++
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. E.g., in this case, we consider n>2 and divide both sides of Equation gif by n+1 to get

displaymath64662

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

   eqnarray19148

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

eqnarray19195

where tex2html_wrap_inline64676 is the tex2html_wrap_inline58453 harmonic number . In Section gif it is shown that tex2html_wrap_inline64680, where tex2html_wrap_inline64682 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

eqnarray19223

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

eqnarray19225


next up previous contents index

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