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

1 /**
2 * Internal method to remove from a subtree.
3 * @param x the item to remove.
4 * @param t the node that roots the tree.
5 * @return the new root.
6 * @throws ItemNotFoundException if x is not found.
7 */
8 protected BinaryNode<AnyType> remove( AnyType x, BinaryNode<AnyType> tt )
9 {
10 BinaryNodeWithSize<AnyType> t = (BinaryNodeWithSize<AnyType>) tt;
11
12 if( t == null )
13 throw new ItemNotFoundException( x.toString( ) );
14 if( x.compareTo( t.element ) < 0 )
15 t.left = remove( x, t.left );
16 else if( x.compareTo( t.element ) > 0 )
17 t.right = remove( x, t.right );
18 else if( t.left != null && t.right != null ) // Two children
19 {
20 t.element = findMin( t.right ).element;
21 t.right = removeMin( t.right );
22 }
23 else
24 return ( t.left != null ) ? t.left : t.right;
25
26 t.size--;
27 return t;
28 }

figure 19.18
The remove operation for a search tree with order statistics

analysis of binary
search tree operations

19.3

The cost of each binary search tree operation ( insert , find , and remove ) is pro-
portional to the number of nodes accessed during the operation. We can thus
charge the access of any node in the tree a cost of 1 plus its depth (recall that
the depth measures the number of edges on a path rather than the number of
nodes), which gives the cost of a successful search.
Figure 19.19 shows two trees. Figure 19.19(a) shows a balanced tree of
15 nodes. The cost to access any node is at most 4 units, and some nodes
require fewer accesses. This situation is analogous to the one that occurs in
the binary search algorithm. If the tree is perfectly balanced, the access cost
is logarithmic.

The cost of an
operation is
proportional to the
depth of the last
accessed node.
The cost is logarith-
mic for a well-
balanced tree, but it
could be as bad as
linear for a
degenerate tree.