Question: Need help with this delete method for an AVL java program. It does not delete the inserts, is it wrong? how can I fix it?
Need help with this delete method for an AVL java program. It does not delete the inserts, is it wrong? how can I fix it?
public NodedeleteNode(Node root, E item) { //Step 1: Perform standard BST delete if (root == null) return root; /*If the key to be deleted is smaller than the root's key, then it lies in left subtree*/ if (root.item.compareTo(root.item) < 0) root.left = deleteNode(root.left, item); /*If the key to be deleted is greater than the root's key, then it lies in right subtree*/ else if (root.item.compareTo(root.item) > 0) root.right = deleteNode(root.right, item); /*if key is same as root's key, then this is the node to be deleted*/ else { //node with only one child or no child if ((root.left == null) || (root.right == null)) { Node temp = null; if (temp == root.left) temp = root.right; else temp = root.left; //No child case if (temp == null) { temp = root; root = null; } else// One child case root = temp; // Copy the contents of // the non-empty child } else { /*node with two children: Get the inorder successor (smallest in the right subtree)*/ Node temp = minValueNode(root.right); //Copy the inorder successor's data to this node root.item = temp.item; //Delete the inorder successor root.right = deleteNode(root.right, temp.item); } } //If the tree had only one node then return if (root == null) return root; //Step 2: Update height of the current node root.height = max(height(root.left), height(root.right)) + 1; /*Step 3: Get the balance factor of this node (to check whether this node became unbalanced)*/ int balance = getBalance(root); //If this node becomes unbalanced, then there are 4 cases //Left Left Case if (balance > 1 && getBalance(root.left) >= 0) return rightRotate(root); //Left Right Case if (balance > 1 && getBalance(root.left) < 0) { root.left = leftRotate(root.left); return rightRotate(root); } //Right Right Case if (balance < -1 && getBalance(root.right) <= 0) return leftRotate(root); //Right Left Case if (balance < -1 && getBalance(root.right) > 0) { root.right = rightRotate(root.right); return leftRotate(root); } return root; }
Step by Step Solution
There are 3 Steps involved in it
Get step-by-step solutions from verified subject matter experts
