1. 概要

二分探索木(BST)は基本的なデータ構造であり、二分木の一種であり、左側のノードの値が親より小さく、右側のノードの値が大きい親

このチュートリアルでは、2つの二分探索木をマージするために使用できる2つのアルゴリズムについて学習します。 また、これらのアルゴリズムの複雑さ、別名 BigOについても説明します。 アルゴリズムの複雑さは、アルゴリズムの実行に必要な時間とスペースの量を測定するため、非常に重要です。

次の画像には、2つの二分探索木(BST1とBST2)があります。 これらの2つのツリーをマージすると、以下に示すようにマージされたBSTが生成されます。

マージされたBSTは、BST1とBST2のすべての要素を持ち、二分探索木の特性を維持します。

2. マージ、ソート、再構築

このアルゴリズムの主なアイデアは、両方のBSTの要素を配列に移動し、マージされたBSTを並べ替えて形成することです。

このアルゴリズムには、次の3つの主要なステップがあります。

  • ステップ1: BSTを処理し、要素をそれぞれの配列に格納します。
  • ステップ2:マージされた配列で配列を結合し、それらの要素を並べ替えます。 バブルソート、挿入ソートなど、一般的なソート方法のいずれかを使用できます。
  • ステップ3:マージされた配列の要素をコピーして、順序どおりにトラバースすることにより、マージされたBSTを作成します。

データセットのサイズとともに増加するため、ステップ1の複雑なitはです。 およびは、マージされるBSTのサイズです。

ステップ2の時間計算量は、使用するソートアルゴリズムのタイプによって異なります。これは、バブルソートであるか、挿入ソートであるかによって異なります。

すべての要素を配列に格納する必要があるため、ステップのスペースの複雑さはです。

アルゴリズムは次のように説明できます。

3. トラバース、ソート、再構築

このソリューションでは、両方のBSTの要素を同時にトラバースし、マージされた配列に移動します。

このアルゴリズムには、次の4つの主要なステップもあります。

  • ステップ1: BSTを処理し、要素をそれぞれの配列に格納します。
  • ステップ2:のサイズのアレイを作成します。ここで、はマージされる2つのBSTのサイズです。 この配列は、マージされたBSTの要素を格納します。
  • ステップ3:両方のアレイを同時にトラバースします。 トラバース中に、現在の要素の小さい方を選択して、マージされた配列に移動します。 次に、前に選択した要素を削除した後、処理を続行します。
  • ステップ4:マージされた配列の要素をコピーして、順序どおりにトラバースすることにより、マージされたBSTを作成します

ステップ1とステップ2の時間とスペースの複雑さは、データセットのサイズとともに複雑さが増すにつれてです。

ステップ3の時間計算量はです。 ステップのスペースの複雑さはです。ここで、は配列がマージされた後のデータセットのサイズです。

ステップ4の時間と空間の複雑さはです。

それがどのように見えるか見てみましょう:

4. 結論

この記事では、二分探索木をマージするために使用できる2つの可能な解決策を検討しました。 また、それぞれの時間と空間の複雑さを特定しました。