0

BST でノードを削除するメソッドを作成しようとしていますが、機能しません。自分で作成した Node クラスを使用しています。デバッグを試みましたが、コードのエラーに対処するための助けが得られませんでした。

それを機能させる方法についての助けに感謝します。

public boolean delete(Node z)
{
    if (z == null)
        return false;

    Node x,y;
    if( z.getLeft() == null || z.getRight()== null)
        y = z;
    else { 
        y = (Node) successor(z);
    }
    if (y.getLeft() != null)
        x = y.getLeft();
    else x = y.getRight();
    if(x != null)
        x.setParent(y.getParent());
    if(y.getParent() == null) {
        this.node=x;
    }
    else if (y == y.getParent().getLeft())
    {
            y.getParent().setLeft(x);
    }
        else y.getParent().setRight(x);

    if(y==z)
        z.setKey(y.getKey());
    return true;    
}


public Node treeMinimum(Node x) {
    while (x.getLeft() != null)
        x = x.getLeft();

    return x;
}

public Node successor(Node node) {
    Node x = node;

    if (x.getRight() != null)
        return treeMinimum(x.getRight());

    Node y = x.getParent();
    while (y != null && x == y.getRight()) {
        x = y;
        y = y.getParent();
    }

    return y;
}
4

2 に答える 2

0

お役に立てれば

/**
 * Internal method to remove from a subtree.
 *
 * @param x the item to remove.
 * @param t the node that roots the tree.
 * @return the new root.
 * @throws ItemNotFoundException if x is not found.
 */
protected BinaryNode remove(Comparable x, BinaryNode t) {
    if (t == null) {
        throw new ItemNotFoundException(x.toString());
    }
    if (x.compareTo(t.element) < 0) {
        t.left = remove(x, t.left);
    } else if (x.compareTo(t.element) > 0) {
        t.right = remove(x, t.right);
    } else if (t.left != null && t.right != null) { // Two children
        t.element = findMin(t.right).element;
        t.right = removeMin(t.right);
    } else {
        t = (t.left != null) ? t.left : t.right;
    }
    return t;
}
于 2013-05-15T12:01:49.867 に答える