二分探索木 (BST) と例
⚡ スマートサマリー
二分探索木(BST)は、各ノードの左サブツリーに小さなキー、右サブツリーに大きなキーが格納されるノードベースの木構造であり、高速な検索、挿入、削除を可能にします。本書では、BSTの属性、型、操作、擬似コードについて解説します。
二分探索木とは何ですか?
二分探索木は、ノードとその左右の枝(ツリー構造でモデル化される)を分析し、値を返すための高度なアルゴリズムです。二分探索木は基本的な二分探索アルゴリズムのアーキテクチャに基づいて設計されているため、ノードの検索、挿入、削除を高速に行うことができます。これにより、プログラムの速度と精度が大幅に向上します。
二分探索木の属性
BST は複数のノードで構成され、次の属性で構成されます。
- ツリーのノードは、親子関係で表されます。
- 各親ノードは、子ノードを持たないか、左側と右側に最大 XNUMX つのサブノードまたはサブツリーを持つことができます。
- 二分探索ツリーとも呼ばれるすべてのサブツリーには、それ自体の右側と左側にサブ分岐があります。
- すべてのノードはキーと値のペアでリンクされています。
- 左サブツリーに存在するノードのキーは、その親ノードのキーよりも小さい。
- 同様に、右側のサブツリーに存在するノードのキーは、その親ノードのキーよりも大きい。
- メインノード、つまり親ノード(レベル11)があります。その下には、それぞれ独自のキー値を持つ左ノードと右ノード(ブランチ)があります。
- 右側のサブツリーは、親ノードよりも大きなキー値を持つ。
- 左側のサブツリーのキー値は、親ノードのキー値よりも小さい。
なぜ二分探索木が必要なのでしょうか?
- 二分探索木が現実世界のあらゆる問題に対する最適な解決策となる主な要因は、速度と精度である。
- 二分検索は親子関係を持つ分岐のような形式であるため、アルゴリズムはツリーのどの位置で要素を検索する必要があるかを認識します。 これにより、プログラムが目的の要素を見つけるために実行する必要があるキーと値の比較の数が減少します。
- さらに、検索対象の要素が親ノードより大きいか小さいかにかかわらず、ノードはどちらのツリー側を検索すればよいかを認識します。その理由は、左サブツリーは常に親ノードより小さく、右サブツリーは常に親ノード以上の値を持つからです。
- BST は、複雑な検索、堅牢なゲーム ロジック、オートコンプリート アクティビティ、グラフィックスなどを実装するためによく使用されます。
- このアルゴリズムは、検索、挿入、削除などの操作を効率的にサポートします。
二分木の種類
バイナリ ツリーには次の XNUMX 種類があります。
- 完全二分木: ツリーのすべてのレベルは満杯で、最後のレベルのみ例外となる可能性があります。同様に、すべてのノードも満杯で、左端に向かっています。
- 完全二分木: リーフノードを除くすべてのノードは、2つの子ノードを持つ。
- バランスのとれた、または完全な二分木: このツリーでは、すべてのノードに2つの子ノードがあります。また、各サブノードは同じ階層にあります。
トプカプ宮殿についての詳細 データ構造の二分木 もし興味があれば。
二分探索ツリーはどのように機能するのでしょうか?
ツリーには、左側でも右側でも、常にルート ノードとさらに子ノードがあります。アルゴリズムは、値をルートと左側または右側のサブツリーのさらに子ノードと比較することによって、すべての操作を実行します。
挿入、検索、削除する要素に応じて、比較後、アルゴリズムはルートノードの左または右のサブツリーを容易に削除できる。
BST では、主に次の 3 種類の操作を提供しています。
- サーチ: 二分木から要素を検索する。
- インサート: 二分木に要素を追加します。
- 削除: 二分木から要素を削除します。
各操作には独自の構造と実行/分析方法がありますが、最も複雑なのは削除操作です。
検索 Opera生産
ツリーの解析は常にルートノードから開始し、次に、探している要素がルートノードより小さいか大きいかに応じて、ルートノードの右または左のサブツリーに進みます。
- 検索対象の要素は10です。
- 要素をルートノード12と比較すると、10 < 12となるため、左サブツリーに移動します。右サブツリーを分析する必要はありません。
- 次に、ノード10とノード7を比較します。10 > 7なので、右側のサブツリーに移動します。
- 次に、10 を次のノードである 9 と比較します。10 > 9 なので、右側のサブツリーの子を調べます。
- 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生産
これは非常に単純な操作です。まず、ルートノードが挿入され、次に次の値がルートノードと比較されます。値がルートノードより大きい場合は右サブツリーに追加され、小さい場合は左サブツリーに追加されます。
- 左から右の順に、二分探索木に挿入する必要のある6つの要素のリストがあります。
- 12をルートノードとして挿入し、次の値7と9を比較して、それぞれ右サブツリーと左サブツリーに挿入します。
- 残りの値 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つの子を持つノードを削除し、削除したノードの右部分木の中で最小の値で置き換える必要があります。
- これは、子ノードを持たないノードを削除する最初のケースです。図に示すように、19、10、5には子ノードがありません。しかし、ここでは19を削除します。
- 値 19 を削除し、ノードからリンクを削除します。
- 19 を含まない BST の新しい構造を表示します。
- これは2番目の削除ケースで、子ノードが1つしかないノードを削除します。図に示すように、ノード9には子ノードが1つあります。
- ノード9を削除し、その子ノード10に置き換え、7から10へのリンクを追加します。
- 9 を含まない BST の新しい構造を表示します。
- ここでは、2つの子ノードを持つノード12を削除します。
- ノードの削除は、順序先行ノード規則に基づいて行われます。つまり、12 の左部分木の中で最大の要素がそのノードに置き換わります。
- ノード12を削除し、左サブツリーで最大の値である10に置き換えます。
- 12を削除した後のBSTの新しい構造を表示します。
- 子ノードが2つあるノード12を削除します。
- ノードの削除は、順序後継者ルールに基づいて行われます。つまり、12 の右部分木の中で最小の要素がそのノードに置き換わります。
- ノード12を削除し、右サブツリーで最小値である19に置き換えます。
- 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)
重要な用語
- インサート: ツリーに要素を挿入する/ツリーを作成する。
- サーチ: ツリー構造の中から要素を検索します。
- 予約注文の追跡: ツリーを先行順走査します。
- インオーダートラバーサル: ツリーを順序通りに走査します。
- 後順走査: ツリーを後順走査します。








