二分探索木 (BST) と例

二分探索木とは何ですか?

二分探索ツリーは、ツリー構造でモデル化されたノードとその左右の枝を分析し、値を返すために使用される高度なアルゴリズムです。 BST は、 archi基本的な二分探索アルゴリズムの構造。したがって、ノードの検索、挿入、削除を高速化できます。これにより、プログラムが非常に高速かつ正確になります。

二分探索木の属性

BST は複数のノードで構成され、次のもので構成されます。wing 属性:

  • ツリーのノードは親子関係で表現されます
  • 各親ノードは、子ノードを持たないか、左側と右側に最大 XNUMX つのサブノードまたはサブツリーを持つことができます。
  • 二分探索ツリーとも呼ばれるすべてのサブツリーには、それ自体の右側と左側にサブ分岐があります。
  • すべてのノードはキーと値のペアでリンクされています。
  • 左側のサブツリーに存在するノードのキーは、親ノードのキーよりも小さいです
  • 同様に、左側のサブツリー ノードのキーの値は、親ノードのキーよりも小さくなります。

二分探索木の属性

  1. メイン ノードまたは親レベル 11 があります。その下に、独自のキー値を持つ左右のノード/ブランチがあります。
  2. 右のサブツリーには親ノードよりも大きなキー値があります
  3. 左側のサブツリーには親ノードよりも値があります

なぜ二分探索木が必要なのでしょうか?

  • 二分探索ツリーを現実世界の問題に対する最適な解決策にする XNUMX つの主な要素は、速度と精度です。
  • 二分検索は親子関係を持つ分岐のような形式であるため、アルゴリズムはツリーのどの位置で要素を検索する必要があるかを認識します。 これにより、プログラムが目的の要素を見つけるために実行する必要があるキーと値の比較の数が減少します。
  • さらに、検索対象の要素が親ノードより大きいか小さい場合、ノードはツリーのどの側を検索するかを認識します。 その理由は、左側のサブツリーは常に親ノードよりも小さく、右側のサブツリーには常に親ノード以上の値があるためです。
  • BST は一般的に com の実装に利用されます。plex 検索、堅牢なゲーム ロジック、オートコンプリート アクティビティ、グラフィックス。
  • このアルゴリズムは、検索、挿入、削除などの操作を効率的にサポートします。

二分木の種類

バイナリ ツリーには次の XNUMX 種類があります。

  • 完全なバイナリ ツリー: ツリー内のすべてのレベルは、最後のレベルで発生する可能性のある例外でいっぱいです。 同様に、すべてのノードがいっぱいになり、左端に進みます。
  • 完全なバイナリ ツリー: リーフを除くすべてのノードに 2 つの子ノードがあります。
  • バランスの取れたバイナリ ツリーまたは完全なバイナリ ツリー: ツリーでは、すべてのノードに XNUMX つの子があります。 また、各サブノードには同じレベルがあります。

詳細については、こちらから データ構造の二分木 もし興味があれば。

二分探索ツリーはどのように機能するのでしょうか?

ツリーには常にルート ノードと、左側または右側にさらに子ノードがあります。 このアルゴリズムは、値をルートと、それに応じて左または右のサブツリー内のさらに子ノードと比較することによって、すべての操作を実行します。

挿入、検索、または削除される要素に応じて、比較後、アルゴリズムはルート ノードの左側または右側のサブツリーを簡単に削除できます。

BST は主に次の機能を提供しますwing 用途に応じて XNUMX 種類の操作を選択できます。

  • 検索: バイナリ ツリーから要素を検索します。
  • 挿入: バイナリ ツリーに要素を追加します。
  • 削除: バイナリ ツリーから要素を削除します。

各操作には独自の構造と実行/分析方法がありますが、最も一般的なのはplex 最も重要なのは削除操作です。

検索操作

常にルート ノードでツリーの分析を開始し、検索対象の要素がルートより小さいか大きいかに応じて、ルート ノードの右または左のサブツリーにさらに移動します。

検索操作

  1. 検索する要素は10です
  2. この要素をルート ノード 12、10 < 12 と比較すると、左側のサブツリーに移動します。 右サブツリーを分析する必要はありません
  3. 次に、10 とノード 7 を比較します。10 > 7 なので、右のサブツリーに移動します。
  4. 次に、10 を次のノード (9、10 > 9) と比較し、右側のサブツリーの子を調べます。
  5. 10 はノード内の値と一致します (10 = 10)。値がユーザーに返されます。

Se の疑似コードarchiBST ではNG

search(element, root)
     if !root
    	return -1
     if root.value == element
    	return 1
     if root.value < element
    	search(element, root.right)
      else
    	search(element, root.left)

挿入操作

これは非常に簡単な操作です。 最初にルート ノードが挿入され、次に次の値がルート ノードと比較されます。 値がルートより大きい場合は右側のサブツリーに追加され、ルートより小さい場合は左側のサブツリーに追加されます。

挿入操作

  1. BST に左から右の順に挿入する必要がある 6 つの要素のリストがあります。
  2. ルート ノードとして 12 を挿入し、次の値 7 と 9 を比較して、それに応じて左右のサブツリーに挿入します。
  3. 残りの値 19、5、および 10 をルート ノード 12 と比較し、それに応じて配置します。 19 > 12 は 12 の右の子として配置され、5 < 12 & 5 < 7 なので 7 の左の子として配置されます。次に 10 を比較します。10 は < 12 & 10 は > 7 & 10 は > 9 で、10 を配置します。 9 の右側のサブツリーとして。

BST にノードを挿入するための擬似コード

insert (element, root)
    Node x = root
    Node y = NULL
    while x:
    	y = x
    if x.value < element.value
        x = x.right
    else
        x = x.left
    if y.value < element
    	y.right = element
    else
    	y.left = element

削除操作

BST からノードを削除するには、ルートを削除する場合とリーフ ノードを削除する場合があります。 また、ルートを削除した後は、ルート ノードについて考える必要があります。

リーフ ノードを削除したい場合は、単に削除するだけで済みますが、ルートを削除したい場合は、ルートの値を別のノードに置き換える必要があります。 フォローしてみましょうwing 例:

  • ケース 1 - 子がゼロのノード: これは最も簡単な状況です。右側または左側に子がもうないノードを削除するだけです。
  • ケース 2 – XNUMX つの子を持つノード: ノードを削除したら、その子ノードを削除された値の親ノードに接続するだけです。
  • ケース 3 XNUMX つの子を持つノード: これは最も困難な状況であり、次のように動作します。wing XNUMXつのルール
  • 3a – In Order Predecessor: XNUMX つの子を持つノードを削除し、削除されたノードの左側のサブツリーの最大値で置き換える必要があります。
  • 3b – In Order Successor: XNUMX つの子を持つノードを削除し、削除されたノードの右側のサブツリーの最大値で置き換える必要があります。

削除操作

  1. これは、子のないノードを削除する最初の削除ケースです。 図からわかるように、19、10、5 には子供がいません。 ただし、19 は削除します。
  2. 値 19 を削除し、ノードからリンクを削除します。
  3. 19 を使用しない BST の新しい構造を表示します。

削除操作

  1. これは、1 に 9 つの子があることがわかるように、XNUMX つの子を持つノードを削除する XNUMX 番目の削除ケースです。
  2. ノード 9 を削除し、その子ノード 10 に置き換えて、7 から 10 へのリンクを追加します。
  3. 9 を使用しない BST の新しい構造を表示します。

削除操作

  1. ここでは、12 つの子を持つノード XNUMX を削除します。
  2. ノードの削除は、順序どおりの先行ルールに基づいて行われます。これは、12 の左側のサブツリー上の最大の要素がノードを置き換えることを意味します。
  3. ノード 12 を削除し、左側のサブツリーの最大値である 10 に置き換えます。
  4. 12 を削除した後の BST の新しい構造を表示します。

削除操作

  1. 1 12 つの子を持つノード XNUMX を削除します。
  2. 2 ノードの削除は、In Order Successor ルールに基づいて行われます。これは、12 の右側のサブツリー上の最大の要素がノードを置き換えることを意味します。
  3. 3 ノード 12 を削除し、右側のサブツリーの最大値である 19 に置き換えます。
  4. 4 削除後の BST の新しい構造を表示する 12

ノードを削除するための疑似コード

delete (value, root):
    Node x = root
    Node y = NULL
# searching the node
    while x:
    	y = x
    if x.value < value
        x = x.right
    else if x.value > value
        x = x.left
    else if value == x
        break
# if the node is not null, then replace it with successor
    if y.left or y.right:
    	newNode = GetInOrderSuccessor(y)
    	root.value = newNode.value
# After copying the value of successor to the root #we're deleting the successor
    	free(newNode)
    else
    	free(y)

重要な用語

  • 挿入: ツリーに要素を挿入/ツリーを作成します。
  • 検索: ツリー内の要素を検索します。
  • 事前順序トラバーサル: 事前順序方式でツリーをスキャンします。
  • Inorder Traversal: ツリーを順序どおりに走査します。
  • ポストオーダー トラバーサル: ポストオーダー方式でツリーをトラバースします。

まとめ

  • BST は、ノード値とルート ノードの比較に基づいてさまざまな操作を実行する高度なレベルのアルゴリズムです。
  • 親子階層内の任意の点がノードを表します。 少なくとも XNUMX つの親ノードまたはルート ノードが常に存在します。
  • 左サブツリーと右サブツリーがあります。 左側のサブツリーには、ルート ノードよりも小さい値が含まれています。 ただし、右側のサブツリーにはルート ノードよりも大きい値が含まれています。
  • 各ノードは、XNUMX、XNUMX、または XNUMX つの子を持つことができます。
  • 二分探索ツリーは、検索、挿入、削除などの主要な操作を容易にします。
  • 一番多いcomを削除plex 子がないノード、子が XNUMX つあるノード、子が XNUMX つあるノードなど、複数のケースがあります。
  • このアルゴリズムは、ゲーム、オートコンプリート データ、グラフィックスなどの実世界のソリューションで利用されています。