Java Reference
In-Depth Information
1
1
2
3
3
2
3
1
3
1
2
3
2
2
1
(a)
(b)
(c)
(d)
(e)
figure 19.20
Binary search trees that can result from inserting a permutation 1, 2, and 3; the balanced tree shown in
part (c) is twice as likely to result as any of the others.
When we divide the internal path length of a tree by the number of nodes in
the tree, we obtain the average node depth. Adding 1 to this average gives the
average cost of a successful search in the tree. Thus we want to compute the
average internal path length for a binary search tree, where the average is
taken over all (equally probable) input permutations. We can easily do so by
viewing the tree recursively and by using techniques from the analysis of
quicksort given in Section 8.6. The average internal path length is established
in Theorem 19.1.
The internal path
length is used to
measure the cost
of a successful
search.
The internal path length of a binary search tree is approximately 1.38 N log N on
average, under the assumption that all permutations are equally likely.
Theorem 19.1
Proof
Let D ( N ) be the average internal path length for trees of N nodes, so D (1) = 0 .An N -
node tree T consists of an i -node left subtree and an ( N - i - 1) -node right subtree,
plus a root at depth 0 for 0
i < N . By assumption, each value of i is equally likely. For
a given i, D(i) is the average internal path length of the left subtree with respect to its
root. In T , all these nodes are one level deeper. Thus the average contribution of the
nodes in the left subtree to the internal path length of T is , plus 1
for each node in the left subtree. The same holds for the right subtree. We thus
obtain the recurrence formula D ( N ) = (2 / N )( ) + N - 1 , which is identical
to the quicksort recurrence solved in Section 8.6. The result is an average internal
path length of O ( N log N ) .
N 1
-
(
1 N
)
Di
()
i
=
0
N 1
-
Di
()
i
=
0
The external path
length is used to
measure the cost of
an unsuccessful
search.
The insertion algorithm implies that the cost of an insert equals the cost of
an unsuccessful search, which is measured by using the external path length.
In an insertion or unsuccessful search, we eventually reach the test t==null .
 
Search WWH ::




Custom Search