本Data Structures and Algorithms: Annotated Reference with Examples で使用されているバイナリ ツリー削除ノード アルゴリズムを読んでいます。
34 ページ、ケース 4 (右と左の両方のサブ ツリーを持つノードを削除)、本に記載されているアルゴリズムに従って動作しないように見えます。
//Case 4
get largestValue from nodeToRemove.Left
FindParent(largestValue).Right <- 0
nodeToRemove.Value<-largestValue.Value
次の行は、サブツリーから最大値をどのように削除しますかFindParent(largestValue).Right <- 0
2 つの子を持つノードを削除する場合、順序どおりの後続ノードまたは順序どおりの先行ノードのいずれかを選択できます。この場合、左のサブツリー (左のサブツリーの右端の子を意味する) で最大値を見つけています。つまり、ノードの順序どおりの先行ノードを見つけています。
置換ノードが見つかったら、削除するノードを実際に削除するわけではありません。代わりに、後続ノードから値を取得し、その値を削除するノードに保存します。次に、後続ノードを削除します。そうすることで、選択したノードの値が元のノードの左側のサブツリーのすべての子の値よりも低く、その値よりも大きくなることを確認できるため、二分探索ツリー プロパティを保持します。元のノードの右側のサブツリーにあるすべての子の。
編集
あなたの質問をもう少し読んだ後、私は問題を見つけたと思います。
delete通常、関数に加えて、replace問題のノードを置き換える関数があります。このコード行を変更する必要があると思います：
FindParent(largestValue).Right <- 0
に：
FindParent(largestValue).Right <- largestValue.Left
largestValueノードに左の子がない場合は、単にnullorを取得します0。左の子がある場合、その子はlargestValueノードの代わりになります。その通りです。largestValueこのコードは、ノードが左の子を持つ可能性があるというシナリオを考慮していません。
別の編集
スニペットを投稿しただけなので、コードのコンテキストが何であるかわかりません。しかし、投稿されたスニペットには、あなたが提案する問題があるようです (間違ったノードを置き換える)。通常、3つのケースがありますが、スニペットのコメントにあることに気付きました//Case 4（したがって、他のコンテキストがある可能性があります）。
先ほど、 にはdelete通常replace. そのため、ノードが見つかったらlargestValue、2 つの単純なケース (子のないノードと 1 つの子を持つノード) に従って削除します。したがって、2 つの子を持つノードを削除する疑似コードを見ている場合は、次のようにします。
get largestValue from nodeToRemove.Left
nodeToRemove.Value <- largestValue.Value
//now replace largestValue with largestValue.Left
if largestValue = largestValue.Parent.Left then
largestValue.Parent.Left <- largestValue.Left //is largestValue a left child?
else //largestValue must be a right child
largestValue.Parent.Right <- largestValue.Left
if largestValue.Left is not null then
largestValue.Left.Parent <- largestValue.Parent
Data Structures And Algorithms の本でこの部分が省略されているのは奇妙だと思います。理解する。
上記のコードが機能することを証明するには、次のツリーを検討してください。
8
/ \
7 9
を削除したいとしましょう8。largestValueから検索しようとしますnodeToRemove.Left。7左側のサブツリーには子が 1 つしかないため、これが得られます。
次に、次のようにします。
nodeToRemove.Value <- largestValue.Value
つまり:
8.value <- 7.Value
また
8.Value <- 7
したがって、ツリーは次のようになります。
7
/ \
7 9
置換ノードを取り除く必要があるためlargestValue、largestValue.Left(これはnull) に置き換えます。そのため、まず、どのような子供7であるかを調べます。
if largestValue = largestValue.Parent.Left then
つまり:
if 7 = 7.Parent.Left then
また：
if 7 = 8.Left then
7はの左子なので、( )8に置き換える必要があります。子がないため、nullです。そのため、 nullに割り当てられます (左の子が効果的に削除されます)。したがって、これは次のツリーになることを意味します。8.Left7.RightlargestValue.Parent.Left <- largestValue.Left77.LeftlargestValue.Parent.Left
7
\
9
何がうまくいかないのかを明確にする必要があると思います。
これが役立つ場合に備えて、バイナリツリーでの削除の概念を説明します。
ツリーに、削除する子ノードが2つあるノードがあるとします。
下のツリーで、ノードb a
/ \
b c
/ \ / \
d efgを削除するとします。
ノードを削除するときは、その依存ノードを再接続する必要があります。
すなわち。bを削除するときは、ノードdとeを再接続する必要があります。
左側のノードの値は右側のノードよりも小さく、親ノードの値は左側のノードと右側のノードの間にあることがわかります。この場合、d<bおよびb<eです。これは二分木の定義の一部です。
少しわかりにくいのは、e<aです。つまり、これはbをeに置き換えることができることを意味します。これで、eを再接続しました。dを再接続する必要があります。
前に述べたように、d <eなので、eをeの左側のノードとしてアタッチできます。
これで削除は完了です。
（ところで、ノードをツリーの上位に移動し、この方法で依存ノードを再配置するプロセスは、ノードのプロモートと呼ばれます。他のノードを削除せずにノードをプロモートすることもできます。）
a
/ \
d c
\ / \
e f g
ノードbを削除すると、別の完全に正当な結果が得られることに注意してください。ノードeではなくノードdをプロモートすることを選択した場合、ツリーは次のようになります。
a
/ \
e c
/ / \
d f g
アイデアは、単純に左側の最大のノードから値を取得し、それを削除するノードに移動することです。つまり、ノードをまったく削除せず、その内容を置き換えるだけです。次に、「削除された」ノードに移動した値を持つノードを削除します。これにより、すべてのノードの値がその左側のすべての子よりも大きく、右側のすべての子よりも小さいツリーの順序が維持されます。
疑似コードを理解していれば、一般的なケースでは機能しますが、「左サブツリーの 1 つのノード」のケースでは失敗します。ナイスキャッチ。
これは、node_to_remove を左側のサブツリーからの maximum_value に効果的に置き換えます (古い large_value ノードもヌルにします)。
BST では、node_to_remove の左側のサブツリーはすべて node_to_remove よりも小さいことに注意してください。node_to_remove の右側のサブツリーはすべて node_to_remove よりも大きくなります。したがって、左のサブツリーで最大のノードを取得すると、不変条件が保持されます。
これが「サブツリーの場合の 1 つのノード」である場合、代わりに正しいサブツリーが破棄されます。ラメ:(
Vivin が指摘しているように、largestNode の左の子を再接続することもできません。
アルゴリズムのその部分に関するウィキペディアの見解を見ると、より理にかなっているかもしれません。
2 つの子を持つノードの削除: 削除するノードを "N" と呼びます。N を削除しないでください。代わりに、順序どおりの後続ノードまたは順序どおりの先行ノード "R" のいずれかを選択します。N の値を R の値に置き換えてから、R を削除します (注: R 自体には最大 1 つの子があります)。
指定されたアルゴリズムは、順序どおりの先行ノードを選択することに注意してください。
編集: R (ウィキペディアの用語を使用する) に 1 つの子がある可能性を見逃しているようです。再帰的な削除の方がうまくいくかもしれません。