0

我正在编写一个二叉搜索树，并且快完成了。我在删除节点时遇到问题。

每个节点都有一个对其左、右和父节点的引用（给根节点一个虚拟父节点）、一个数据元素和一个整数计数（称为副本）。当一个人输入一个已经存在的元素时，节点只会增加它的副本，当他们调用 decrementCopies() 时，该方法会减少副本数，如果副本数低于 1，则返回 false。 setLeft() 和 setRight () 方法将给定节点的父节点设置为被调用节点（即，node1.setLeft(node2) 将节点2 的父节点设置为节点1）。

下面是删除方法：

public void remove(T target) {
    if (target == null)
        throw new IllegalArgumentException();

    // cont is container, the node containing the
    // desired element.
    boolean rootRemoval;
    boolean contIsLeft;
    CountingNode<T> cont;
    CountingNode<T> parent;
    CountingNode<T> left;
    CountingNode<T> right;
    CountingNode<T> grad;

            assert root != null;
    if (root == null) {
        return;
    }
    else {
        cont = root.getNodeFor(target);
    }

    assert cont != null;
    if (cont == null) {
        return;
    }
    else if (cont.decrementCopies()) {
        words -= 1;
        return;
    }

    words -= 1;
    nodes -= 1;

    parent = cont.getParent();
    left = cont.getLeft();
    contIsLeft = parent.getLeft() == cont;
    rootRemoval = cont == root;

    if (cont.getNumChildren() < 2) {
        parent.setChild(cont.getOnlyChild(), contIsLeft);

        if (rootRemoval) {
            root = dummyParent.getOnlyChild();
        }

        return;
    }

    right = cont.getRight();
    grad = left.getRightMostNode();

    grad.getParent().setRight(grad.getLeft());

    if (grad != left) 
        grad.setLeft(left);
    else 
        grad.setLeft(null);

    grad.setRight(right);
    parent.setChild(grad, contIsLeft);

    if (rootRemoval) {
        root = dummyParent.getOnlyChild();
    }

    return;

}

它适用于大多数输入，但偶尔当我转储大量单词然后按顺序删除相同的单词时，我会遇到循环引用和丢失节点的问题。我一直在试图找出问题出在哪里，但我似乎无法在较小的范围内复制错误条件（我必须转储相当大的文件以使其发生以进行调试），我也看不到任何东西显然错了。

希望有人可以帮助我阐明一些观点。谢谢

4

0 回答 0