// Deletes nodes from a tree recursively. private Customer deleteRecursively(Customer…
- User
// Deletes nodes from a tree recursively. private Customer deleteRecursively(Customer node, int id) { // Base case if (node == null) { return null; }
// Traversing the tree if (id < node.getID()) { // Go left node.setLeft(deleteRecursively(node.getLeft(), id)); } else if (id > node.getID()) { // Go right node.setRight(deleteRecursively(node.getRight(), id)); } else { // We found the node here we need to delete if (node.getLeft() == null) { // No left child so return the right return node.getRight(); } else if (node.getRight() == null) { // No right child so return the left return node.getLeft(); } // Node with two children replacing the min from the right subtree. Customer successor = findMin(node.getRight()); // Replacing ID with the successor's ID node.setID(successor.getID()); // Remove the successor node.setRight(deleteRecursively(node.getRight(), successor.getID())); } updateHeight(node); return balance(node); }how would you edit this function to make sure that it passes this test @Test void testDeletePerformanceAVL(){ //run this test 10 times, if Acceptable > 6 times, passes int count = 0;
for(int i=0; i<11; i++){ if(testDeletePerformanceAcceptableAVL()){ count++; } } System.out.println(count); if(s1.getRoot()==null) assertTrue(false, "This is an empty tree"); if(count >= 7) assertTrue(true, "AVL Remove Acceptable:"); else assertTrue(false, "AVL Remove Unacceptable:"); } boolean testInsertPerformanceAcceptableAVL() { RandomGen IdSequence = new RandomGen(10000,100000,RANDOMTYPE.UNIFORMINT,3000,0,1); int power1Size = 1000; int power2Size = 2000; //find time for adding 1000 Customers long startTime1000 = System.nanoTime(); for(int i=0;i<power1Size; i++){ d1 = s1.new Customer(IdSequence.getRandNum()); s1.insert(d1); } long endTime1000 = System.nanoTime(); long duration1000 = (endTime1000 - startTime1000); s1.clear(); //find time for adding 2000 Customers long startTime2000 = System.nanoTime(); for(int i=0;i<power2Size; i++){ d2 = s1.new Customer(IdSequence.getRandNum()); s1.insert(d2); } long endTime2000 = System.nanoTime(); long duration2000 = (endTime2000 - startTime2000); double compareTime = duration2000/(2.0 * duration1000); if(compareTime > .7 && compareTime < 1.5) return true; else return false; }it seems that after removing 1000 or 2000 people there is still one node left
- Assistant
You can modify the
deleteRecursivelyfunction to ensure it properly handles the deletion of nodes, especially when deleting the last node in the tree. The key is to prevent callingupdateHeightandbalanceon anullnode, which can happen when the last node is being deleted.Here's how you can edit the function:
private Customer deleteRecursively(Customer node, int id) { // Base case if (node == null) { return null; } // Traversing the tree if (id < node.getID()) { // Go left node.setLeft(deleteRecursively(node.getLeft(), id)); } else if (id > node.getID()) { // Go right node.setRight(deleteRecursively(node.getRight(), id)); } else { // We found the node to delete if (node.getLeft() == null && node.getRight() == null) { // No children, so delete node return null; } else if (node.getLeft() == null) { // No left child so return the right return node.getRight(); } else if (node.getRight() == null) { // No right child so return the left return node.getLeft(); } else { // Node with two children: replace with min from right subtree Customer successor = findMin(node.getRight()); // Replace node's data with successor's data node.setID(successor.getID()); // Delete the successor node.setRight(deleteRecursively(node.getRight(), successor.getID())); } } // Update height and balance the node if it's not null if (node != null) { updateHeight(node); return balance(node); } else { // When the node is null (e.g., after deleting the last node), return null return null; } }Explanation:
-
Check for
node != nullbefore updating height and balancing:When you delete a node and it becomes
null(especially when deleting the last node), callingupdateHeight(node)andbalance(node)with anullreference can cause errors or unexpected behavior. By adding a condition to check ifnodeis notnullbefore these calls, you ensure that the function handles this case properly. -
Return
nullwhen the node isnull:If the node becomes
nullafter deletion (which happens when deleting a leaf node or the last node in the tree), you should simply returnnullwithout attempting further operations.
By making these changes, you ensure that the deletion process correctly updates the tree structure, even when deleting nodes that result in empty subtrees or an empty tree. This should help your function pass the test
testDeletePerformanceAVL, as it will correctly handle all deletion cases and ensure that no unwanted nodes remain in the tree after deletions. -