2人の子供とBSTツリーからノードを削除する方法は？

Question

GOUGLED、いくつかのチュートリアルを読み、この質問を投稿する前にいくつかのBSTノードの削除アルゴリズムの説明を見ました。何らかの理由で、BSTノード削除アルゴリズムの説明が完全に説明できません。

バイナリ検索ツリーから2人の子供を持つノードを削除するための4つのアルゴリズムを見つけました：
1）右サブツリーから最小ノードを見つけて、削除したいノードと交換します。
2）左サブツリーから最大のノードを見つけて、削除したいノードと交換します。
3）右のサブツリーから最も深い左端のノードを見つけて、削除したいノードと交換します。
4）左サブツリーから最も深い右端のノードを見つけて、削除したいノードと置き換えます。

どうやら、これらのアルゴリズムのどれも次のユースケースのために機能しません（私は欠けているか理解していないから）。ユースケースは、次のツリーから要素5を削除することです。

最初のアルゴリズムでは、要素6を選択し、その右サブツリーを失います。 2番目のアルゴリズムの場合、要素4を選択し、左サブツリーを失います。 3番目のアルゴリズムでは、要素7を選択し、BSTルールに違反します。 4番目のアルゴリズムでは、BST規則にも違反するであろう要素3を選択します。

そのようなユースケースの正しいアルゴリズムは何ですか？

Answer 1

正しい、BSTでは通常、ノードに2人の子供がいる場合には軽減されます。

2人の子供を持つノードを考えます。このノードをBST（左サブツリー内の右端のノード）の前任者（すなわち、左サブツリー内の右端のノード）でスワップします.-右側のサブトリック（右側のサブツリーの左端のノード）と--totally symmetricslap。

でスワップします。

削除するノードは、最大1つの子供にあります（私たちが前任者に行くことは正しい子を持つことはできません）。 子供がいない場合は、ノードを削除し、完了しました。

ノードが単一の子を持つ場合は、ノードを取り外してそのサブツリーで置き換えます。私たちは再びBSTを取得します。

href="https://i.stack.imgur.com/7bexi.png" rel="nofollownoreferrer">

あなたの例では5を取り外して、その前身4でそれを交換したい4. 4つはrootに入っていて、5つの子供を残しました。最後に5を取り除き、その場所に子供3を置きます。今3は2の右の子供です。

ps。この方法は、値があるノードから別のノードにコピーされるため、「コピーによる削除」と呼ばれることがあります。 2つの理由でこのプロセスを承認しないものがあります。最初のコピーは高価な操作であり得、2番目の基準は失われます（別のデータストラクチャがある値を持つノードを指している場合）。代わりにポインタを変更するだけです。