0

これは 12 年生の課題です。質問の 1 つは、BNode または整数のいずれかを取り、ツリーからノードを削除する BTree クラスのメソッドを作成するように求めています。

これが私が試したことです：

public void delete(BNode b){
    if(b==null){
        return;
    }
    if(b.getLeft()==null && b.getRight()==null){

        b = null;
    }
    else{
        //System.out.println("boiboi");
        BNode tmp = b;
        b = null;
        add(tmp.getLeft());
        add(tmp.getRight());
        tmp = null;
    }
}
public void delete(int v){
    //System.out.println("gord");
    delete(find(v));
}

私が正しいと思う add と find メソッドは次のとおりです。

public BNode find(int v){
    return find(v, root);
}
public BNode find(int v, BNode branch){
    if(branch == null || branch.getVal() == v){
        return branch;
    }
    if(v<branch.getVal()){
        return find(v, branch.getLeft());
    }
    else{//else if(v>branch.getVal())
        return find(v, branch.getRight());
    }
}
public void add(int v){
    if(root == null){
        root = new BNode(v);
    }
    else{
        add(v, root);
    }
}
public void add(int v, BNode branch){
    if(v == branch.getVal()){
        return;
    }
    if(v<branch.getVal()){
        if(branch.getLeft() == null){
            branch.setLeft(new BNode(v));
        }
        else{
            add(v, branch.getLeft());
        }
    }
    else{
        if(branch.getRight() == null){
            branch.setRight(new BNode(v));
        }
        else{
            add(v, branch.getRight());
        }
    }
}
public void add(BNode n){
    if(n==null){
        return;
    }
    add(n.getVal());
}

これが私のテストクラスです：

    BTree bTree = new BTree();
    bTree.add(50);
    bTree.add(60);
    bTree.add(40);
    bTree.add(35);
    bTree.add(55);
    bTree.add(45);
    bTree.add(51);
    bTree.delete(60);
    bTree.display();

出力はまだ私が追加したすべてのものです: 35 40 45 50 51 55 60 最も単純なケースである 51 を削除しようとしても、同じ出力です。ヘルプや提案をいただければ幸いです。ありがとうございます。

4

2 に答える 2

2

BST からノードを削除するときに注意する必要がある 3 つのケースがあります。

  1. 葉の場合は、先に進んで削除してください。

  2. ノードに child が 1 つしかない場合は、単純にその子を親に接続します。[明らかに、getParentOfNode などにいくつかのヘルパー メソッドが必要になります]

  3. ノードに 2 つの子がある場合は、右側のサブツリーで最小の要素を見つけます。その値を現在のノードに入れ、そのノードを削除します。

詳細はこちら。 http://www.cs.sunysb.edu/~skiena/373/notes/lecture6/lecture6.html

于 2013-03-27T03:50:49.243 に答える
0 
/* Algorithm to delete a record from a B-tree of order n.
The field used indicates how many keys in the node are being used. */
    q = NULL;
    p = tree;
    while (p) {
        i = nodesearch(p, key);
        q = p;
        if (i < used(p) -1 && key == k(p,i)) {
            found = TRUE;
            position = i;
            break;
        }
        p = son(p,i);
    }
    if (!found)
    /* error - item not found */
    else if (subtree(p)) {
        /* node is not a leaf */
        if (used(p) > ((n-1)/2)+1)
            /* no underflow */
            delkey (p, position, key);
        else {
            /* Statements to replace key to be deleted */
            /* with successor in father node. */
            replace (p, position, fsucc(p));
            p0 r1 p1 r2 p2 r3 ……. pn-1 rn-1 pn
            q = &fsucc(p);
            qpos = index of fsucc;
            if (used(rbrother(p)) > ((n-1)/2)+1)
                replace (q, qpos, sonsucc(q));
            else
                while (q && used(q) < (n-1)/2) {
                    concatenate(q, brother(q));
                    q = father(q);
                }
        }
    }
    else /* is a leaf */
    delkey(p, position, key);
}
于 2016-08-28T13:09:38.577 に答える