二分探索木 (BST) と例

⚡ スマートサマリー

二分探索木(BST)は、各ノードの左サブツリーに小さなキー、右サブツリーに大きなキーが格納されるノードベースの木構造であり、高速な検索、挿入、削除を可能にします。本書では、BSTの属性、型、操作、擬似コードについて解説します。

  • 🌳 注文した鍵: 左サブツリーのキーは親よりも小さく、右サブツリーのキーは親よりも大きい。
  • ⚡ 対応時間 Operaション: 順序付けによって、値を比較することで検索、挿入、削除を効率的に実行できます。
  • 🔍 サーチ: 各ノードでの比較によって、ツリーの半分が破棄され、左または右に移動します。
  • ➕ インサート: 比較に基づいて、新しい値がルートの左側または右側に配置されます。
  • ➖ 削除: 削除処理では、先行ノードまたは後継ノードを使用して、子ノードが0個、1個、または2個あるノードを処理します。

二分探索木 (BST) と例

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

二分探索木は、ノードとその左右の枝(ツリー構造でモデル化される)を分析し、値を返すための高度なアルゴリズムです。二分探索木は基本的な二分探索アルゴリズムのアーキテクチャに基づいて設計されているため、ノードの検索、挿入、削除を高速に行うことができます。これにより、プログラムの速度と精度が大幅に向上します。

二分探索木の属性

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

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

二分探索木の属性

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

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

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

二分木の種類

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

  • 完全二分木: ツリーのすべてのレベルは満杯で、最後のレベルのみ例外となる可能性があります。同様に、すべてのノードも満杯で、左端に向かっています。
  • 完全二分木: リーフノードを除くすべてのノードは、2つの子ノードを持つ。
  • バランスのとれた、または完全な二分木: このツリーでは、すべてのノードに2つの子ノードがあります。また、各サブノードは同じ階層にあります。

トプカプ宮殿についての詳細 データ構造の二分木 もし興味があれば。

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

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

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

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

  • サーチ: 二分木から要素を検索する。
  • インサート: 二分木に要素を追加します。
  • 削除: 二分木から要素を削除します。

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

検索 Opera生産

ツリーの解析は常にルートノードから開始し、次に、探している要素がルートノードより小さいか大きいかに応じて、ルートノードの右または左のサブツリーに進みます。

検索   Opera生産

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

ニックネーム Code 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生産

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

インサート Opera生産

  1. 左から右の順に、二分探索木に挿入する必要のある6つの要素のリストがあります。
  2. 12をルートノードとして挿入し、次の値7と9を比較して、それぞれ右サブツリーと左サブツリーに挿入します。
  3. 残りの値 19、5、10 をルートノード 12 と比較し、それに応じて配置します。19 > 12 なので、19 を 12 の右の子として配置します。5 < 12 かつ 5 < 7 なので、5 を 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ン

二分探索木からノードを削除する場合、ルートノードの削除やリーフノードの削除など、いくつかのケースがあります。また、ルートノードを削除した後は、ルートノードについて考慮する必要があります。

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

  • ケース1 – 子ノードがゼロの場合: これは最も簡単なケースで、右または左に子ノードを持たないノードを削除するだけで済みます。
  • ケース2 – 子ノードが1つしかない場合: ノードを削除したら、その子ノードを削除した値の親ノードに接続するだけです。
  • ケース3 – 2つの子ノードを持つノード: これは最も困難な状況であり、以下の2つのルールに基づいて機能します。
    • 3a – 順序通りの先行語: 2つの子を持つノードを削除し、削除したノードの左部分木の中で最大の値で置き換える必要があります。
    • 3b – 順序後継者: 2つの子を持つノードを削除し、削除したノードの右部分木の中で最小の値で置き換える必要があります。

削除 Operaン

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

削除 Operaン

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

削除 Operaン

  1. ここでは、2つの子ノードを持つノード12を削除します。
  2. ノードの削除は、順序先行ノード規則に基づいて行われます。つまり、12 の左部分木の中で最大の要素がそのノードに置き換わります。
  3. ノード12を削除し、左サブツリーで最大の値である10に置き換えます。
  4. 12を削除した後のBSTの新しい構造を表示します。

削除 Operaン

  1. 子ノードが2つあるノード12を削除します。
  2. ノードの削除は、順序後継者ルールに基づいて行われます。つまり、12 の右部分木の中で最小の要素がそのノードに置き換わります。
  3. ノード12を削除し、右サブツリーで最小値である19に置き換えます。
  4. 12を削除した後のBSTの新しい構造を表示します。

ニックネーム Code ノードを削除するには

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, delete the successor
        free(newNode)
    else
        free(y)

重要な用語

  • インサート: ツリーに要素を挿入する/ツリーを作成する。
  • サーチ: ツリー構造の中から要素を検索します。
  • 予約注文の追跡: ツリーを先行順走査します。
  • インオーダートラバーサル: ツリーを順序通りに走査します。
  • 後順走査: ツリーを後順走査します。

よくあるご質問

BST(二分探索木)とそのバランス型バリアントは、オートコンプリート、決定木、ソート済みキーによる高速検索といったAI機能の背後にある順序付きデータを整理します。これらは検索効率を維持し、AIシステムが推論時に候補を迅速に取得するのに役立ちます。

はい。AIアシスタントは、BSTの検索、挿入、削除コードを生成できます。 Python, Javaまたは C++ 平易な説明から判断してください。削除ロジックは、子要素が2つの場合、間違いやすいので、慎重に確認してください。

バランスの取れた二分探索木では、検索、挿入、削除はO(log n)の時間で実行されます。最悪の場合、バランスの取れていない木は連結リストに劣化し、操作にO(n)の時間を要するため、自己平衡木がよく使用されます。

単純な二分探索木は、バランスが崩れて処理速度が遅くなることがあります。AVL木や赤黒木のようなバランスの取れた二分探索木は、挿入や削除後にノードを自動的に回転させて高さを小さく保ち、O(log n)の操作時間を保証します。