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

1 /**
2 * Removes an item from this collection.
3 * @param x any object.
4 * @return true if this item was removed from the collection.
5 */
6 public boolean remove( Object x )
7 {
8 int oldSize = size( );
9
10 deletedNode = nullNode;
11 root = remove( (AnyType) x, root );
12
13 return size( ) != oldSize;
14 }
15
16 /**
17 * Change the size of this collection to zero.
18 */
19 public void clear( )
20 {
21 theSize = 0;
22 modCount++;
23 root = nullNode;
24 }

figure 19.72
Public deletion
methods for TreeSet

The iterator class is shown in Figure 19.74; current is positioned at the
node containing the next unseen item. The tricky part is maintaining the
stack, path , which includes all nodes on the path to the current node, but not
the current node itself. The constructor simply follows all the left links,
pushing all but the last node on the path onto the stack. We also maintain the
number of items visited, thus making the hasNext test easy.
The core routine is the private method next , shown in Figure 19.75.
After we record the value in the current node, and set lastVisited (for
remove ), we need to advance current . If the current node has a right child, we
go right once and then left as far as possible (lines 11-17). Otherwise, as
lines 21-32 illustrate, we need to go back up the path toward the root until
we find the node from which we turned left. That node, which must exist
because otherwise an exception would have been thrown at line 4, is the
next node in the iteration.
Figure 19.76 shows the remarkably tricky remove . The relatively easy part
is shown at lines 3-15, where after some error checks, we remove the item
from the tree at line 11. At line 13, we fix the expectedModCount , so as to not
get a subsequent ConcurrentModificationException for this iterator (only). At
line 14, we lower visited (so hasNext will work), and at line 15, we set
lastVisited to null , so a consecutive remove will be disallowed.