二分探索木 (BST) と例

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

バイナリサーチツリーは、ツリー構造でモデル化されたノードとその左と右のブランチを分析し、値を返すために使用される高度なアルゴリズムです。BST は、基本的なバイナリサーチアルゴリズムのアーキテクチャに基づいて考案されているため、ノードの検索、挿入、削除が高速化されます。これにより、プログラムが非常に高速かつ正確になります。

二分探索木の属性

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

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

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

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

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

二分木の種類

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

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

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

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

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

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

BST では、主に次の 3 種類の操作を提供しています。

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

各操作には独自の構造と実行/分析方法がありますが、最も複雑なのは削除操作です。

検索 Opera生産

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

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

BST で検索するための疑似コード

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)

インセット Opera生産

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

BST に左から右の順に挿入する必要がある 6 つの要素のリストがあります。
ルートノードとして 12 を挿入し、次の値 7 と 9 を比較して、それに応じて左右のサブツリーに挿入します。
残りの値 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

削除 Operaン

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

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

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

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

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

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

1 12 つの子を持つノード XNUMX を削除します。
2 ノードの削除は、In Order Successor ルールに基づいて行われます。これは、12 の右側のサブツリー上の最大の要素がノードを置き換えることを意味します。
3 ノード 12 を削除し、右側のサブツリーの最大値である 19 に置き換えます。
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 つの子を持つことができます。
バイナリ検索ツリーは、検索、挿入、削除などの基本的な操作を容易にします。
削除は最も複雑で、子を持たないノード、子を 1 つ持つノード、子を 2 つ持つノードなど、複数のケースがあります。
このアルゴリズムは、ゲーム、オートコンプリートデータ、グラフィックスなどの実世界のソリューションで利用されています。