Итак, я создал функцию удаления для моей реализации BST. Он работает правильно для случаев удаления листовых узлов и поддеревьев с правым потомком, но без левого потомка, и наоборот.
Однако удаление корневого узла вызывает у меня проблемы. Я пытаюсь заменить корень его преемником, а затем установить правый дочерний элемент нового корня равным правому дочернему элементу старого корня.
Пример:
50
/ \
/ \
42 63
/ \ /
/ \ 55
21 43
\ \
23 \
/ \ 47
/ \
44 48
Если бы я удалил узел 50 в моей программе, 55 был бы новым корнем, но тогда 63 просто исчезнул бы, но все остальное работает нормально.
Я неправильно перекомпоновал узлы?
(Начинается с «Проблема здесь» комментарий в коде)
//How I display my tree
//inprder traversal
private void inOrder(Node curr){
if(curr != null){
//traverse left
inOrder(curr.leftChild);
System.out.print("\n" + curr + "->");
//traverse right
inOrder(curr.rightChild);
}
}
public boolean deleteContact(String key){
//Start at root node
Node currentNode = root;
Node parent = root;
boolean isLeftChld = true;
//loop over left and right subtrees
//finds node to be deleted
while(!key.equals(currentNode.key)){
parent = currentNode;
if(key.compareToIgnoreCase(currentNode.key) < 0){
isLeftChld = true;
currentNode = currentNode.leftChild;
}else{
isLeftChld = false;
currentNode = currentNode.rightChild;
}
//Node never found
if(currentNode == null){
return false;
}
}
//if the node doesnt have children
//go ahead and delete
if(currentNode.leftChild == null && currentNode.rightChild == null){
if(currentNode == root){
root = null;
//Handle case of juss deleting leafs
}else if(isLeftChld){//check if it was a left or right child
//delete it
parent.leftChild = null;
}else{
parent.rightChild = null;
}
//situation of no right child
//handling node dissapearing
} else if(currentNode.rightChild == null){
if(currentNode == root){
root = currentNode.leftChild;
}else if (isLeftChld){
parent.leftChild = currentNode.leftChild;
}else{
parent.rightChild = currentNode.leftChild;
}
//situation of no left child
}else if(currentNode.leftChild == null){
if(currentNode == root){
root = currentNode.rightChild;
}else if (isLeftChld){
parent.leftChild = currentNode.rightChild;
}else{
parent.rightChild = currentNode.leftChild;
}
**Problem is Here**
//situation of two children being involved
//figure out which node will replace which
} else {
//Node temp = currentNode.rightChild;
Node successor = minValue(currentNode.rightChild);
if(currentNode == root){
root = successor;
}else if(isLeftChld){
parent.leftChild = successor;
}else{
parent.rightChild = successor;
}
root.leftChild = currentNode.leftChild;
}
return true;
}
//Function to return min value for a root node
//Used for delete function - finds succesor
private Node minValue(Node root)
{
Node minv = root;
while (root.leftChild != null)
{
minv = root.leftChild;
root = root.leftChild;
}
return minv;
}