/** * Removes the specified key and its related data from the tree. * If the tree does not contain the specified key, an KeyNotInTreeException should be thrown. */ public void remove (Key key) { // check if key exists in tree if (!contains(key)) throw new KeyNotInTreeException(); // check if key is less than root (-> left subtree) if (name.compareTo(key) > 0) leftSubtree.remove(key); // check if key is greater than root (-> right subtree) else if (name.compareTo(key) < 0) rightSubtree.remove(key); // key is wether in left nor in right subtree -> key must be root of actual tree else{ // left subtree is empty if (leftSubtree.isEmptyTree()){ // replace key with right subtree replaceBST(rightSubtree); } // right subtree is empty else if (rightSubtree.isEmptyTree()){ // replace key with left subtree replaceBST(leftSubtree); } // both subtrees are non-empty else{ // get leftest(smallest) right(greater) child/successor BinarySearchTree<Key, Data> child = rightSubtree.findSmallestChild(); // replace key with leftest right child replaceBST(child); // no left subtree exist because got leftest right child -> take right one child.replaceBST(child.rightSubtree); } } }public void replaceBST(BinarySearchTree<Key, Data> tree){ this.name = tree.name; this.value = tree.value; this.leftSubtree = tree.leftSubtree; this.rightSubtree = tree.rightSubtree; }