1: // Removes an entry from the tree rooted at a given node.
2: // rootNode is a reference to the root of a tree.
3: // entry is the object to be removed.
4: // oldEntry is an object whose data field is null.
5: // Returns the root node of the resulting tree; if entry matches
6: // an entry in the tree, oldEntry's data field is the entry
7: // that was removed from the tree; otherwise it is null.
8: private BinaryNode<T> removeEntry(BinaryNode<T> rootNode, T entry,
9: ReturnObject oldEntry)
10: {
11: if (rootNode != null)
12: {
13: T rootData = rootNode.getData();
14: int comparison = entry.compareTo(rootData);
15:
16: if (comparison == 0) // entry == root entry
17: {
18: oldEntry.set(rootData);
19: rootNode = removeFromRoot(rootNode);
20: }
21: else if (comparison < 0) // entry < root entry
22: {
23: BinaryNode<T> leftChild = rootNode.getLeftChild();
24: BinaryNode<T> subtreeRoot = removeEntry(leftChild, entry, oldEntry);
25: rootNode.setLeftChild(subtreeRoot);
26: }
27: else // entry > root entry
28: {
29: BinaryNode<T> rightChild = rootNode.getRightChild();
30: rootNode.setRightChild(removeEntry(rightChild, entry, oldEntry));
31: } // end if
32: } // end if
33:
34: return rootNode;
35: } // end removeEntry
36: // Version 4.0