Exercise 8 (Binary Search Trees)
Abschlussbedingungen
Delete a Node from a Binary Search Tree
Geöffnet: Donnerstag, 21. Mai 2015, 00:00
Fällig: Samstag, 30. Mai 2015, 08:00
Delete a Node from a Binary Search Tree
- Implement an algorithm to delete a node from the binary search tree which we discussed during the lecture.
- Download the source code from the Moodle page and implement the method delete.
- Use the method getSuccessor to find the successor if the node to be deleted has two child nodes (like discussed during the lecture).
public class Tree<E extends Comparable<E>> {
...
/**
* Returns true in case of success and false if the given node was not found.
*/
public boolean delete(E node) {
// TODO: Implement this algorithm.
}
private Node<E> getSuccessor(Node<E> delNode) {
...
}
- Write a short documentation how the delete node algorithm works (format txt or pdf). Explain why the algorithm works (also the sub-algorithm to find a successor).
Hints
Take care of the case where the node to be deleted is the root. There are three cases for the node to be deleted:
- The node is a leaf.
- The node has one child node.
- The node has two child nodes.