BSTから順番に番号を削除します

Question

試験中にこの質問があり、すぐに回答が見つかりませんでした。

いくつかの順序番号A = [1,3,6,9,11]と数字をキーとするBSTを含む配列Aがあります。 BSTからAの数字を削除する効率的な再帰アルゴリズムを提供する必要があります。

問題はノードを削除することではなく、ノードを削除する際に配列が順序付けされているという事実をどのように使うかです。

誰かがヒントを教えてもらえますか？

Answer 1

これは考えられる方法の1つです。

BST（standard recursive algorithmを使用）とA（左から右）の両方を同時にトラバースすることができます。トラバースのそれぞれは、要素を昇順で生成します。あなたはツリーからそれらを削除するために一致する要素を探しています。

純粋なアルゴリズムは、O(size(BST))時間の複雑さを持ちます。

場合によっては、左のサブツリーを完全に見ることを避けることができます。ツリー内の「現在の」ノードの値は、左のサブツリーの値の上限を示します。 Aの「現在の」要素は、左のサブツリーをスキップします。

Aを使い切ったらすぐにアルゴリズムを停止することもできます。

Answer 2

BSTをルートノードで表します。

引数arrayとbst持つ関数delete-array-from-bstである：array又はbstが空の場合

• は：
• 三個のサブアレイにアレイを分割戻り、値が小さい、等しい、およびより大きいbstのルートノードの値
• 小数点以下の値を左の副BSTに、小行列の値を右の副BSTに、最後に等しい値を削除するappliケーブル

アレイの分割はバイナリ検索であるため、各アレイ値をルートノードと比較する必要はありません。サブアレイは元の配列と構造を共有できます。最後に等しい値を削除すると、配列内の各値に対して最悪の削除ケースが発生することはありません。