9

削除するノードに 2 つの子がある場合、BST での削除手順を検討してください。右のサブツリーに最小キーを保持するノードに常に置き換えるとしましょう。

問題は次のとおりです。この手順は交換可能ですか? つまり、x を削除してから y を削除すると、最初に y を削除してから x を削除した場合と同じ結果になりますか?

答えはノーだと思いますが、反例を見つけることも、正当な理由を理解することもできません。

編集：

多分私はもっと明確にする必要があります。

手順を考えてみましょうtransplant(node x, node y): x を y (およびそのサブツリー) に置き換えます。したがって、2 つの子を持つノード (x など) を削除する場合は、右のサブツリーに最小キーを保持するノードに置き換えます。

y = minimum(x.right)
transplant(y, y.right) // extracts the minimum (it doesn't have left child)
y.right = x.right
y.left = x.left
transplant(x,y)

問題は、上記の手順が可換でないことをどのように証明するかということでした。

4

4 に答える 4

19

削除 (一般に) は可換ではありません。反例を次に示します。

    4
   / \
  3   7
     /
    6

4 を削除してから 3 を削除するとどうなるでしょうか。

4 を削除すると、新しいルートとして 6 が取得されます。

   6
  / \
 3   7

3 を削除してもツリーは変わりませんが、次のようになります。

  6
   \
    7

3 を削除してから 4 を削除するとどうなるでしょうか。

3 を削除しても、ツリーは変わりません。

 4
  \
   7
  /
 6

ただし、ここで 4 を削除すると、新しいルートは 7 になります。

  7
 /
6

結果として得られる 2 つのツリーは同じではないため、削除は可換ではありません。

アップデート

これは、2 つの子を持つノードを常に削除する場合の制限を読みませんでした。私の解決策は一般的なケースです。反例が見つかったら更新します。

別の更新

具体的な証拠はありませんが、推測を危険にさらすつもりです：

一般的なケースでは、子供が 2 人いるのか、1 人なのか、または子供がいないのかによって、削除の処理方法が異なります。私が提供した反例では、最初に 2 つの子を持つノードを削除し、次に 1 つの子を持つノードを削除します。その後、子のないノードを削除してから、子が 1 つある別のノードを削除します。

2 つの子を持つノードのみを削除するという特殊なケースでは、両方のノードが同じサブツリーにある場合を考慮する必要があります (異なるサブツリーにあるかどうかは問題ではないため、削除の順序に基づいて全体の構造が変わることはありません)。実際に証明する必要があるのは、各ノードに 2 つの子がある同じサブツリー内のノードの削除順序が重要かどうかです。

A が B の祖先である 2 つのノード A と B を考えます。次に、質問を次のように絞り込むことができます。

相互に祖先と子孫の関係にある二分探索木からの 2 つのノードの削除を検討している場合、削除は交換可能ですか (これは、それらが同じサブツリーにあることを意味します)?

ノード (A としましょう) を削除すると、右側のサブツリーをトラバースして最小要素を見つけます。このノードはリーフ ノードになり、B と等しくなることはありません (B には 2 つの子があり、リーフ ノードになれないため)。次に、A の値をこのリーフノードの値に置き換えます。これが意味することは、ツリーの唯一の構造上の変更は、A の値をリーフ ノードの値に置き換えることと、リーフ ノードを失うことです。

B についても同じプロセスが必要です。つまり、ノードの値を置き換え、リーフ ノードを置き換えます。したがって、一般に、2 つの子を持つノードを削除する場合、構造上の変更は、削除するノードの値の変更と、置換として使用する値のリーフ ノードの削除のみです。

したがって、質問はさらに洗練されています。

削除の順序に関係なく、常に同じ置換ノードを取得することを保証できますか (2 つの子を持つノードを常に削除する場合)。

答えは（私が思うに）イエスです。なんで？ここにいくつかの観察があります：

  • 最初に子孫ノードを削除し、次に祖先ノードを削除するとします。子孫ノードを削除したときに変更されたサブツリーが、先祖ノードの右側の子の左側のサブツリーにありません。これは、このサブツリーが影響を受けないことを意味します。これはまた、削除の順序に関係なく、2 つの異なるサブツリーが変更されるため、操作は交換可能であることを意味します。
  • 繰り返しになりますが、最初に子孫ノードを削除し、2 番目に祖先ノードを削除するとします。子孫ノードを削除したときに変更されたサブツリーは、先祖ノードの右側の子の左側のサブツリーにあります。しかし、ここでも重なりはありません。その理由は、最初に子孫ノードを削除すると、子孫ノードの右側の子の左側のサブツリーが表示されるためです。次に先祖ノードを削除すると、先祖ノードの右子の左サブツリーに入った後は常に左に向かっているため、そのサブツリーを下ることはありません。繰り返しますが、最初に何を削除するかに関係なく、異なるサブツリーを変更しているため、順序は問題ではないようです。
  • もう 1 つのケースは、先祖ノードを最初に削除し、最小ノードが子孫ノードの子であることがわかった場合です。これは、子孫ノードが 1 つの子を持つことになり、1 つの子を削除するのは簡単であることを意味します。このシナリオで、最初に子孫ノードを削除した場合を考えてみましょう。次に、子孫ノードの値をその右の子に置き換えてから、右の子を削除します。次に、祖先ノードを削除すると、同じ最小ノード (古い削除されたノードの左の子であり、置き換えられたノードの左の子でもあります) が見つかります。いずれにせよ、同じ構造になってしまいます。

これは厳密な証明ではありません。これらは私が行ったいくつかの観察です。ぜひ、気軽に穴をあけてみてください！

于 2010-06-07T17:32:02.513 に答える
2

Vivin の回答に示されている反例は非可換性の唯一のケースであり、2 つの子を持つノードのみを削除できるという制限によって実際に排除されているように思えます。

しかし、Vivin の前提の 1 つと思われるものを破棄すれば、それを排除することもできます。つまり、適切なサブツリーをできるだけトラバースして、受け入れ可能な後継者を見つける必要はありません。代わりに、正しいサブツリー内の最小のノードを常に後継者として昇格させる場合、それがどれだけ離れているかに関係なく、2 つ未満の子を持つノードを削除する制限を緩和したとしても、Vivin の結果は 

    7
   /
  6
で開始すると、到達することはありません

    4
   / \
  3 7
     /
    6

代わりに、最初に 3 (後続なし) を削除し、次に 4 (後続として 6) を削除します。 

    6
     \
      7

これは、削除の順序が逆になった場合と同じです。

削除は可換であり、私が名前を付けた前提を考えると、常に可換であると思います（後続ノードは常に、削除されたノードの右側のサブツリー内の最小のノードです）。

提供できる正式な証拠はありません。事例を列挙しただけです。

  1. 削除する 2 つのノードが異なるサブツリーにある場合、一方を削除しても他方には影響しません。それらが同じパスにある場合にのみ、削除の順序が結果に影響を与える可能性があります。

    したがって、可換性への影響は、祖先ノードとその子孫の 1 つが両方とも削除された場合にのみ発生します。では、これらの垂直関係は可換性にどのように影響するのでしょうか?

  2. 祖先の左サブツリーの子孫。後継者は右側のサブツリーから来ており、左側のサブツリーにはまったく影響を与えないため、この状況は可換性には影響しません。

  3. 祖先の右サブツリーの子孫。先祖の後継者が常に右側のサブツリーの最小ノードである場合、先祖の前または後にどの子孫が削除されても、削除の順序によって後継者の選択が変わることはありません。祖先の後継ノードが削除対象の子孫ノードであることが判明した場合でも、その子孫もその次に大きいノードに置き換えられ、その子孫は独自の左サブツリーを処理する必要がありません。 . したがって、先祖と右サブツリーの子孫の削除は常に交換可能です。

于 2011-04-06T18:34:42.320 に答える
1

ノードに 2 つの子がある場合、ノードを削除するには 2 つの同じように実行可能な方法があると思います:
ケース 4 にスキップ...

ケース 1:削除 3 (葉ノード)
 2 3
 / \ --> / \
1 3 1


ケース 2:削除 2 (左の子ノード)
 2 3
 / \ --> / \
1 3 1


ケース 3:削除 2 (右の子ノード)
 2 2
 / \ --> / \
1 3 3

______________________________________________________________________
ケース 4: 2 (左右の子ノード) を削除 2
 2 3
 / \ --> / \ または / \      
1 3 1 3 両方とも機能し、結果として異なるツリーが作成されます
:) .mathcs.emory.edu/~cheung/Courses/323/Syllabus/Trees/AVL-delete.html
Deleting a node with 2 children nodes: 1) Replace the (to-delete) node with its in-order predecessor or in-order successor 2) Then delete the in-order predecessor or in-order successor

于 2016-10-10T01:02:58.117 に答える
0

ここで、Vivin の 2 回目の更新に応答します。

これは質問の良い言い直しだと思います：

相互に祖先と子孫の関係にある二分探索木からの 2 つのノードの削除を検討している場合、削除は交換可能ですか (これは、それらが同じサブツリーにあることを意味します)?

しかし、以下の太字の文は正しくありません。

ノード (A としましょう) を削除すると、右側のサブツリーをトラバースして最小要素を見つけます。このノードはリーフ ノードになり、 B と等しくなることはありません

A の右側のサブツリーの最小要素は、右側の子を持つことができるためです。ですから、葉ではありません。A の右サブツリーの最小要素を と呼びましょうsuccessor(A)。ここで、B が ではないことは事実ですsuccessor(A)が、その右側のサブツリーにある可能性があります。だから、それは混乱です。

要約してみます。

仮説：

  1. A と B にはそれぞれ 2 人の子供がいます。
  2. A と B は同じサブツリーにあります。

仮説から推測できるその他の事柄:

  1. Bsuccessor(A)も A もありませんsuccessor(B)。

さて、それを考えると、4つの異なるケースがあると思います（いつものように、AをBの先祖としましょう）：

  1. B は A の左側のサブツリーにあります
  2. Bは先祖successor(A)
  3. successor(A)Bの祖先です
  4. Bと後継者(A)は何の関係もありません。(それらは異なる A のサブツリーにあります)

ケース1、2、4は問題ではないと思います（もちろん証明できません）。したがって、successor(A)B 削除手順の祖先が交換可能ではない場合のみです。それともできますか？

私はボールを渡します:)

よろしく。

于 2010-06-11T17:45:09.823 に答える