Created
October 27, 2015 10:54
-
-
Save maxskorr/5b53ace5c785a64b447f to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
private boolean delete(Node<T> node, T value) { | |
if (node == null) { | |
return false; | |
} | |
if (value.compareTo(node.value) > 0) { | |
return delete(node.right, value); | |
} | |
if (value.compareTo(node.value) < 0) { | |
return delete(node.left, value); | |
} | |
if (value.equals(node.value)) { | |
Node<T> parent = findParentNode(root, value); | |
if (parent == null) { | |
return false; | |
} | |
// node has no children | |
if (node.right == null && node.left == null) { | |
if (parent.left != null && parent.left.equals(node)) { | |
parent.setLeft(null); | |
size--; | |
return true; | |
} | |
if (parent.right != null && parent.right.equals(node)) { | |
parent.setRight(null); | |
size--; | |
return true; | |
} | |
} | |
// Node has one child | |
if (node.left == null) { | |
if (parent.left != null && parent.left.equals(node)) { | |
parent.setLeft(node.right); | |
size--; | |
return true; | |
} | |
if (parent.right != null && parent.right.equals(node)) { | |
parent.setRight(node.right); | |
size--; | |
return true; | |
} | |
} | |
if (node.right == null) { | |
if (parent.left != null && parent.left.equals(node)) { | |
parent.setLeft(node.left); | |
size--; | |
return true; | |
} | |
if (parent.right != null && parent.right.equals(node)) { | |
parent.setRight(node.left); | |
size--; | |
return true; | |
} | |
} | |
// node has two children | |
Node<T> minNode = findMin(node.left); | |
if (minNode == null) { | |
return false; | |
} | |
Node<T> minNodeParent = findParentNode(root, minNode.value); | |
minNodeParent.setLeft(null); | |
node.setValue(minNode.value); | |
return true; | |
} | |
return false; | |
} | |
public boolean delete(T value) { | |
return delete(root, value); | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment