2

二分木からノードを削除する関数を作成しようとしています。私はまだ関数をコーディングしておらず、ノードを削除するために考慮すべきさまざまな条件について考えようとしています。考えられる条件は次のとおりだと思います。

  1. ノードには子がありません

  2. ノードには 1 つの子があります

  3. ノードには 2 つの子があります

これらのケースのそれぞれで、削除機能を実行するアルゴリズムは何でしょうか?

4

5 に答える 5

5

これは、アルゴリズムに関する標準的な教科書に見られるものですが、不均衡なケース（バランスの取れたツリーは通常、削除後に「回転」と呼ばれるいくつかのリバランス操作を実行します）に関心があり、「明白な」データ構造（tree_node構造）を使用するとします。値と他への2つのポインタを保持しますtree_node）：

  1. 子なし：ノードによって保持されているメモリを解放し、ノードを指す親の子リンクをNULL;として設定します。
  2. 1つの子：ノードによって保持されているメモリを解放し、ノードを指す親の子リンクをその一意の子のアドレスとして設定します。
  3. 2人の子供：これは確かに「複雑な」ケースです。左の子の右端のノード（または右の子の左端のノード）を見つけ、その値を取得して削除し（「ケース1」であるため、簡単で再帰的に実行できます）、現在のノードの値を次のように設定します。そのノードの1つ。これはですがO(tree_height) = O(n)、（少なくとも理論的には）問題ではありません。それでも、ノードを見つけるのは複雑になるからです。
于 2012-09-03T21:08:35.590 に答える
1

最初のタスクは、ノードが存在するかどうかを検索することです。これは、検索中に実行され、残りの条件が正しいかどうかを確認します。

  1. リーフ ノード:親の子 (右/左) を NULL に設定します。

  2. 子を 1 つ持つ:削除するノードの子をその親の子に設定するだけです。

  3. 2 つの子を持つ:基本的に、削除するノードの新しい子を見つけてサブツリーをプルーニングし、ここでサブツリー全体を並べ替える必要があります。

于 2012-09-03T20:52:09.593 に答える
1

一般的な二分木を扱っていると仮定すると、次のようにします。

  1. ノードには子がありません - つまり、リーフです: 削除すると便利です..

  2. ノードに子が 1 つある - 削除するノードの親をその子の親にしてから、ノードを削除します。つまり、A->Parent = B; C->Parent = A;andAを削除する必要がある場合、 1. Make C->Parent = B; 2.削除A;

  3. トリッキーなもの....はい、削除するノードを右のサブツリーの左端の子で置き換えるか、左のサブツリーの右端のツリーで置き換えるかのどちらかでうまくいきます...このように見ることができるので、

ノードが削除された場合、いくつかのプロパティを満たすノードに置き換える必要があります...たとえば、バイナリ ツリーが並べ替えられた数値を (昇順で) 順トラバーサルで表している場合、削除されたノードは次のいずれかのノードに置き換えられる必要があります。そのサブツリーのいずれか。これは、残りの左サブツリー全体よりも値が大きく、残りの右サブツリー全体よりも小さい必要があります (残りとは、削除されたノードを正常に調整した後に残っているサブツリーを意味します)。そのようなノードは 2 つしか存在しません。右のサブツリーの左端のリーフ、または左のサブツリーの右端のノードです。

したがって、削除されたノードをどちらかから置き換えるだけで十分です...!!

于 2012-09-03T21:24:21.753 に答える
1

ツリーに追加のプロパティはありますか? AVLですか？

そうでない場合は、必要なことを行うための非常に明白で簡単な方法がいくつかあります（Vitalijが言ったように、データ表現によって異なります）。

たとえばAVLの場合、それを行うためのよく知られた方法もあります（ウィキペディアはそのトピックについて詳しく説明します）

于 2012-09-03T20:48:42.660 に答える