Binary search trees - Data Structures and Problem Solving Using Java - page 705

Recall that in a tree of N nodes there are N + 1 null links. The external path
length measures the total number of nodes that are accessed, including the
null node for each of these N + 1 null links. The null node is sometimes
called an external tree node, which explains the term external path length . As
we show later in the chapter, replacing the null node with a sentinel may be
convenient.

definition: The external path length of a binary search tree is the sum of the
depths of the N + 1 null links. The terminating null node is considered a node
for these purposes.

One plus the result of dividing the average external path length by N + 1
yields the average cost of an unsuccessful search or insertion. As with the binary
search algorithm, the average cost of an unsuccessful search is only slightly
more than the cost of a successful search, which follows from Theorem 19.2.

For any tree T , let IPL ( T ) be the internal path length of T and let EPL ( T ) be its exter-
nal path length. Then, if T has N nodes, EPL ( T ) = IPL ( T ) + 2 N .

Theorem 19.2

This theorem is proved by induction and is left as Exercise 19.7.

Proof

It is tempting to say immediately that these results imply that the average
running time of all operations is O (log N ). This implication is true in practice,
but it has not been established analytically because the assumption used to
prove the previous results do not take into account the deletion algorithm. In
fact, close examination suggests that we might be in trouble with our deletion
algorithm because the remove operation always replaces a two-child deleted
node with a node from the right subtree. This result would seem to have the
effect of eventually unbalancing the tree and tending to make it left-heavy. It
has been shown that if we build a random binary search tree and then perform
roughly N 2 pairs of random insert / remove combinations, the binary search
trees will have an expected depth of . However, a reasonable number
of random insert and remove operations (in which the order of insert and
remove is also random) does not unbalance the tree in any observable way. In
fact, for small search trees, the remove algorithm seems to balance the tree.
Consequently, we can reasonably assume that for random input all operations
behave in logarithmic average time, although this result has not been proved
mathematically. In Exercise 19.25 we describe some alternative deletion
strategies.

Random remove
operations do not
preserve the ran-
domness of a tree.
The effects are not
completely under-
stood theoretically,
but they apparently
are negligible in
practice.

ON ( )