1: // Removes the entry in a given root node of a subtree.
2: // rootNode is the root node of the subtree.
3: // Returns the root node of the revised subtree.
4: private BinaryNode<T> removeFromRoot(BinaryNode<T> rootNode)
5: {
6: // Case 1: rootNode has two children
7: if (rootNode.hasLeftChild() && rootNode.hasRightChild())
8: {
9: // Find node with largest entry in left subtree
10: BinaryNode<T> leftSubtreeRoot = rootNode.getLeftChild();
11: BinaryNode<T> largestNode = findLargest(leftSubtreeRoot);
12:
13: // Replace entry in root
14: rootNode.setData(largestNode.getData());
15:
16: // Remove node with largest entry in left subtree
17: rootNode.setLeftChild(removeLargest(leftSubtreeRoot));
18: } // end if
19:
20: // Case 2: rootNode has at most one child
21: else if (rootNode.hasRightChild())
22: rootNode = rootNode.getRightChild();
23: else
24: rootNode = rootNode.getLeftChild();
25:
26: // Assertion: If rootNode was a leaf, it is now null
27:
28: return rootNode;
29: } // end removeEntry
30: // Version 4.0