write a \"delete\" method to remove values from the tree. submit a version of BS
ID: 3553484 • Letter: W
Question
write a "delete" method to remove values from the tree.
submit a version of BST that builds on what we did in class and supports deleting a value from the tree.
there are 3 cases:
(1) deleting leaf node
(2) deleting a node with one child (left or right)
(3) deleting a node with 2 children
Of course, you will also have to pay special attention to whether or not you are deleting a root nod.
// what we did in class: /* Practice using Java to create a tree class. Use graphviz to render */ //(1) Create a node class (simple, no encapsulation) //(2) Create a BST class (simple, no encapsulation) //(3) Insert //(4) findMax //(5) findMin //(6) toGraphviz //(7) findNode //(8) contains //(9*) removeNode public class BST { static class Node { Node left = null; Node right = null; String data = null; }; Node root = null; public boolean isEmpty() { return this.root == null; } private void insertHelper(Node subtree, String data) { assert subtree != null; if (data.compareTo(subtree.data) < 0) { if (subtree.left == null) { Node theNode = new Node(); theNode.data = data; subtree.left = theNode; } else { insertHelper(subtree.left, data); } } else { if (subtree.right == null) { Node theNode = new Node(); theNode.data = data; subtree.right = theNode; } else { insertHelper(subtree.right, data); } } } public void insert(String data) { if (this.isEmpty()) { Node theNode = new Node(); theNode.data = data; this.root = theNode; } else { insertHelper(this.root, data); } } private void printGraphvizHelper(Node subtree) { if (subtree.left != null) { System.out.println("""+subtree.data + "" -> "" + subtree.left.data + """); printGraphvizHelper(subtree.left); } if (subtree.right != null) { System.out.println("""+subtree.data + "" -> "" + subtree.right.data + """); printGraphvizHelper(subtree.right); } } public void printGraphviz() { System.out.println("digraph g{"); if (!this.isEmpty()) { printGraphvizHelper(this.root); } System.out.println("}"); } private Node findNode(Node subtree, String data) { if (subtree == null) { return null; } else if (data.compareTo(subtree.data) == 0) { return subtree; } else if (data.compareTo(subtree.data) < 0) { return findNode(subtree.left, data); } else { return findNode(subtree.right, data); } } public boolean contains(String data) { return findNode(this.root, data) != null; } public static void main(String[] args) { //Driver code //incrementall test the BST as its developed BST bst = new BST(); assert bst.isEmpty(); bst.insert("K"); assert !bst.isEmpty(); bst.insert("C"); bst.insert("B"); bst.insert("M"); bst.insert("L"); bst.insert("L"); bst.printGraphviz(); } }; Explanation / Answer
public static pBSTRemoveNode tree_removeNumber( pBSTRemoveNode r,Comparable n){ if(r != null){ if(r.data.compareTo(n) < 0){ r.right = tree_removeNumber(r.right,n); }else if(r.data.compareTo(n) > 0){ r.left = tree_removeNumber(r.left,n); }else{ if(r.left == null && r.right == null){ r = null; }else if(r.left != null && r.right == null){ r = r.left; }else if(r.right != null && r.left == null){ r = r.right; }else{ if(r.right.left == null){ r.right.left = r.left; r = r.right; }else{ pBSTRemoveNode q,p = r.right; while(p.left.left != null) p = p.left; q = p.left; p.left = q.right; q.left = r.left; q.right = r.right; r = q; } } } } return r; }Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.