Java Reference
In-Depth Information
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> t )
9 {
10 if( t == null )
11 throw new ItemNotFoundException( x.toString( ) );
12 if( x.compareTo( t.element ) < 0 )
13 t.left = remove( x, t.left );
14 else if( x.compareTo( t.element ) > 0 )
15 t.right = remove( x, t.right );
16 else if( t.left != null && t.right != null ) // Two children
17 {
18 t.element = findMin( t.right ).element;
19 t.right = removeMin( t.right );
20 }
21 else
22 t = ( t.left != null ) ? t.left : t.right;
23 return t;
24 }
figure 19.12
The remove method for the BinarySearchTree class
only one two-way comparison per node. The strategy is similar to what we
did in the binary search algorithm in Section 5.6. We discuss the technique for
binary search trees in Section 19.6.2 when we illustrate the deletion algorithm
for AA-trees.
Second, we do not have to use recursion to perform the insertion. In
fact, a recursive implementation is probably slower than a nonrecursive
implementation. We discuss an iterative implementation of insert in Section
19.5.3 in the context of red-black trees.
order statistics
19.2
The binary search tree allows us to find either the minimum or maximum item
in time that is equivalent to an arbitrarily named find . Sometimes, we also have
to be able to access the K th smallest element, for an arbitrary K provided as a
parameter. We can do so if we keep track of the size of each node in the tree.
 
 
Search WWH ::




Custom Search