which we have started implementing a BinarySearchTree class that implements the
ID: 3817386 • Letter: W
Question
which we have started implementing a BinarySearchTree class that implements the Set interface. To make the code remove an element from the binary search tree easier, I wrote deleteEntry() so that it relies on three support methods. You must now complete the removeLeaf(), promoteChild(), and selectReplacementChild() methods . An explanation of what each of these methods must do is in the javadoc comments that appear before each method.
Now do consider following situation:
testRemoveLeafOnlyChildLeft
testRemoveLeafOnlyChildRight
testRemoveLeafBothChildren
testSelectReplacementOnlyChildLeft
testSelectReplacementOnlyChildRight
testSelectReplacementLeaf
testPromoteChildWithNodeFromLeft
testPromoteChildWithNodeFromRight
testPromoteChildToRoot
------------
Explanation / Answer
1) removeLeaf: Obtain parent reference of leaf. If it is left child then remove parent reference to leaf by making the reference null. Otherwise it is the right child so make the parent right child reference null.
private void removeLeaf(Entry<E> leaf) {
Entry<E> p = leaf.parent;
if (p.left == leaf) {
p.left = null;
} else {
p.right = null;
}
}
2) selectReplacementChild: As there is only 0 or 1 child for given node, return left / right child (if present). Otherwise, there is no child for given node so return null.
3) promoteChild: Obtain parent node reference and grand parent node reference of replacement node. If parent node is left child (of grand parent node) then promote replace node as left child (of grand parent node). Otherwise parent node is the right child (of grand parent node) so promote the replacement node as right child (of grand parent node).
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.