Java: BST - удаление узла без детей не работает - PullRequest
Новая
       42

Java: BST - удаление узла без детей не работает

0 голосов
/ 03 мая 2018

Я использую связанный узел для представления BST. Я могу найти узел без детей, но метод удаления для этого узла не работает:

После того, как я добавлю один узел со значением "cat", у моего BST будет только один узел без дочерних элементов.

Я попытался удалить узел "cat", но обнаружил, что метод удаления не работает - узел "cat" все еще находится в BST.

Кто-нибудь знает, как решить эту проблему? Спасибо 

public class BinarySearchTree {

Node root;

public BinarySearchTree() {
    root = null;
}

/*
 * Adds the specified node to the BST
 */
public String add(String value) {
    if (root == null) {
        root = new Node(value);
        return value;
    }
    return add(root, value);
}

public String add(Node root, String value) {
    int comparision = value.compareTo(root.data);

    if (comparision < 0) {
        if (root.left != null)
            return add(root.left, value);
        root.left = new Node(value);
        return value;
    }

    if (comparision > 0) {
        if (root.right != null)
            return add(root.right, value);
        root.right = new Node(value);
        return value;
    }
    return value;// not allow duplicate
}

/*
 * Returns true if the string is found in the BST
 */
public boolean contains(String value) {
    return contains(root, value);
}

private boolean contains(Node root, String value) {
    if (root == null) {
        return false;
    }

    int comparison = value.compareTo(root.data);
    if (comparison == 0) {
        return true;
    }
    if (comparison < 0) {
        return contains(root.left, value);
    } else {
        return contains(root.right, value);
    }
}

/*
 * Checks whether the tree is empty or not
 */
public boolean isEmpty() {
    return root == null;
}

/*
 * Removes the specified string from the BST
 */
public boolean remove(String s) {
    if (contains(s) == false) {
        return false;
    }
    return remove(root, s);
}

public boolean remove(Node root, String s) {
    if (root == null) {
        return false;
    }

    int comparision = s.compareTo(root.data);

    if (comparision == 0) {
        if (root.left == null && root.right == null) {
            System.out.println("----------------------------------");
            root = null;
            return true;
        } else if (root.left != null && root.right != null) {
            Node temp = root;
            String min = minValue(temp.right).data;
            root.data = min;
            removemin(root.right);
            return true;
        }
    }

    if (comparision < 0) {
        if (root.left.data.equals(s)) {
            if (root.left.left == null || root.left.right == null) {
                root.left = root.left.right;
                return true;
            }
        }
        return remove(root.left, s);
    }

    if (comparision > 0) {
        if (root.right.data.equals(s)) {
            if (root.right.right == null || root.right.left == null) {
                root.right = root.right.left;
                return true;
            }
        }
        return remove(root.right, s);
    }
    return false;
}

public Node minValue(Node root) {
    if (root.left == null) {
        return root;
    } else
        return minValue(root.left);
}

public static void removemin(Node root) {
    if (root.left == null) {
        root = null;
    } else
        removemin(root.left);
}

/**
 * Prints the inorder traversal of this tree
 */
public void inorderTraversal() {
    inorderTraversal(root);
}

private void inorderTraversal(Node root) {
    if (root == null)
        return;
    inorderTraversal(root.left);
    System.out.print(root.data + " ");
    inorderTraversal(root.right);
}

private class Node {
    String data;
    Node left;
    Node right;

    public Node(String data) {
        this.data = data;
    }
}

/*
 * Returns the height of the tree
 */
public int getHeight() {
    return getHeight(root);
}

private int getHeight(Node root) {
    if (root == null)
        return 0;
    return 1 + Math.max(getHeight(root.left), getHeight(root.right));

}

Ответы [ 2 ]

0 голосов
/ 03 мая 2018

Проблема связана с методом удаления в этой части: 

if (root.left == null && root.right == null) {
    System.out.println("----------------------------------");
    root = null;
    return true;
}

Вы ожидаете удаления корня, но не удаляете его, потому что java is pass by value. Поэтому, когда вы делаете root = null;, вы устанавливаете скопированную переменную на null, а не на BST root.

Вот ваш обновленный remove метод. Я переименовал root в node для уменьшения путаницы. 

public boolean remove(Node node, String s) {
    if (node == null) {
        return false;
    }

    int comparision = s.compareTo(node.data);

    if (comparision == 0) {
        if (node.left == null && node.right == null) {
            System.out.println("----------------------------------");
            if (node.equals(root))
                this.root = null;
            node = null;
            return true;
        } else if (node.left != null && node.right != null) {
            Node temp = node;
            String min = minValue(temp.right).data;
            node.data = min;
            removemin(node.right);
            return true;
        }
    }

    if (comparision < 0) {
        if (node.left.data.equals(s)) {
            if (node.left.left == null || node.left.right == null) {
                node.left = node.left.right;
                return true;
            }
        }
        return remove(node.left, s);
    }

    if (comparision > 0) {
        if (node.right.data.equals(s)) {
            if (node.right.right == null || node.right.left == null) {
                node.right = node.right.left;
                return true;
            }
        }
        return remove(node.right, s);
    }
    return false;
}

Обратите внимание на эту часть кода, где я устанавливаю this.root в null. 

if (node.equals(root))
    this.root = null;
0 голосов
/ 03 мая 2018

В вашем методе remove(Node root, String s) после определения того, что root содержит значение s, вы изменяете только переменную root на нулевую ссылку. Это не влияет на родителей левого или правого потомка пользователя root, поскольку они никогда не ссылаются на них.

Типичный метод удаления BST возвращает такой узел, что вы можете сделать что-то вроде: 

//...
if(valueToDelete.compareTo(root.value) == 0){
  if(root.left == null && root.right == null){
    return null;
  }
  // Otherwise some juggling of children into a new shape
  // ... actual code here
  return someNodeThatWasDescendantOfRoot
}else if(valueToDelete.compareTo(root.value) < 0){
  root.left = delete(root.left, valueToDelete)
  return root;
}else{
  root.right = delete(root.right, valueToDelete)
  return root;
}
//...

Присвоение дочернему узлу, который может быть затронут, позволяет в результате удаления обновлять его родителя при необходимости, не требуя, чтобы дети ссылались на своих родителей.

...