2

remove(node cRoot, Object o)ソートされた二分木の関数を書こうとしています。

これが私がこれまでに持っているものです：

private boolean remove(Node cRoot, Object o) {
  if (cRoot == null) {
    return false;
  }
  else if (cRoot.item.equals(o)) { 
    //erase node fix tree
    return true;
  }
  else if (((Comparable)item).compareTo(cRoot.item)<=0){
    return remove(cRoot.lChild, o);
  }
  else { 
     return remove(cRoot.rChild,o);
  }
}

正しく動作しません。ノードを削除するには、ツリーを修復して穴を修正する必要があります。これはどのように行う必要がありますか？

4

5 に答える 5

4

ツリーで削除を実行するには、一般に次の 2 つの方法があります。

最初の方法:

ノードを削除してから、いずれかの子に置き換えます。次に、ツリーが再度ソートされるまで、親子スワップを実行してツリーを再ソートします。

2 番目の方法:

ツリーをトラバースして、ルートとして属する次の (最高または最低の) 値を見つけます*。それがリーフ ノードの場合は、それをルートと交換し、削除する値を削除します。内部ノードの場合は、そのノードで remove を再帰的に呼び出す必要があります。葉ノードが削除されるまで繰り返します。

* つまり、BST をソート済みリストに変換する場合、ルートの左側または右側の値を新しいルートとして選択する必要があるということです。つまり、右のサブツリーの一番左の子、または左のサブツリーの一番右の子です。

于 2009-05-07T18:29:16.853 に答える
2

ソートされたツリーからノードを消去するための基本的な擬似コードは非常に単純です。

  1. ノード値を消去します
  2. 最大値を持つ子ノードを見つける
  3. それをルートノードにします
  4. 子がいる場合 - goto 2 再帰的に

基本的に、あなたがしていることは、各ノードの子ノードの最大値になるたびにノードをツリーにバブリングすることです。そのため、最終的にはソートされたツリーのままになり、移動したフルパスの最後にノードが 1 つだけ欠けています。 .

また、件名のウィキペディアを参照してください。Cのサンプルコードもあります。

于 2009-05-07T18:28:43.237 に答える
1

単純なcase3では、次のアルゴリズムを使用できます。

if(removed node had left child)
{
   place left child instead of removed node;
   most_right = most right leaf in the left subtree;
   move right child of removed node as right child of most_right;
}
else
{
   place right child instead of removed node
}

より複雑なケースでは、ツリーのバランスを取り直す必要がある場合があります（C ++の例については、AVLツリー、 http： //www.cmcrossroads.com/bradapp/ftp/src/libs/C ++ / AvlTrees.htmlを参照してください）。

于 2009-05-07T18:38:30.623 に答える
0
  1. リーフ削除ノード
  2. サブツリーを昇格させる
  3. 2 子の場合、ノードをいずれかで置き換えます
  4. 順番に後継者または前任者
  5. 右のサブツリーのほとんどを左または
  6. 左サブツリーの右端
于 2009-05-08T18:06:47.127 に答える