バイナリ検索ツリー（BST）は、すべてのノードが以下のプロパティに従うツリーです-
-
左側のサブツリーのキーの値は、その親（ルート）ノードのキーの値よりも小さいです。
-
右側のサブツリーのキーの値は、その親（ルート）ノードのキーの値以上です。,左のサブツリーと右のサブツリーは、-
left_subtree (keys) < node (key) ≤ right_subtree (keys)
表現
BSTは、BSTプロパティを維持する方法で配置されたノードの集合です。 各ノードには、キーと関連付けられた値があります。 検索中に、目的のキーがBSTのキーと比較され、見つかった場合は関連する値が取得されます。,
以下はBST-
ルートノードキー(27)には、左側のサブツリーにすべての小さい値のキーがあり、右側のサブツリーに高い値のキーがあることがわかります。
基本操作
以下は、ツリーの基本操作です-
-
検索-ツリー内の要素を検索します。
-
Insert−ツリーに要素を挿入します。
-
プリオーダートラバーサル−プリオーダー方法でツリーをトラバースします。
-
in-order Traversal-順序通りにツリーをトラバースします。,
-
ポストオーダートラバーサル-ポストオーダーの方法でツリーをトラバースします。
Node
左と右の子ノードへの参照、いくつかのデータを持つノードを定義します。
struct node { int data; struct node *leftChild; struct node *rightChild;};検索操作
要素を検索するたびに、ルートノードから検索を開始します。 次に、データがキー値よりも小さい場合は、左側のサブツリーで要素を検索します。 それ以外の場合は、右側のサブツリー内の要素を検索します。 各ノードで同じアルゴリズムに従います。,
アルゴリズム
挿入操作
要素を挿入するときはいつでも、まず適切な場所を見つけます。 ルートノードから検索を開始し、データがキー値よりも小さい場合は、左側のサブツリーで空の場所を検索してデータを挿入します。 それ以外の場合は、右側のサブツリーで空の場所を検索し、データを挿入します。
アルゴリズム
iv id=”46c8ef6cbf
-