binary search tree c
操作、C ++実装、利点、およびサンプルプログラムを含むC ++のバイナリ検索ツリー（BST）に関する詳細なチュートリアル：
一般的に呼ばれている二分探索木またはBSTは、次の条件を満たす二分木です。
- BSTの左の子として配置されるルートノードよりも小さいノード。
- BSTの右の子として配置されているルートノードよりも大きいノード。
- 左と右のサブツリーは、順番に二分探索木です。
キーを特定の順序で順序付けるこの配置により、プログラマーは検索、挿入、削除などの操作をより効率的に実行できます。ノードが順序付けられていない場合、操作結果を取得する前に、すべてのノードを比較する必要がある場合があります。
=> ここで完全なC ++トレーニングシリーズを確認してください。
学習内容：
二分探索木C ++
サンプルBSTを以下に示します。
バイナリ検索ツリーは、ノードのこの特定の順序のために「順序付きバイナリツリー」とも呼ばれます。
上記のBSTから、左側のサブツリーにはルートよりも小さいノード、つまり45があり、右側のサブツリーには45より大きいノードがあることがわかります。
次に、BSTのいくつかの基本的な操作について説明します。
基本操作
＃1）挿入
挿入操作は、バイナリ検索ツリーに新しいノードを追加します。
二分探索木の挿入操作のアルゴリズムを以下に示します。
メインC ++への未定義の参照
Insert(data) Begin If node == null Return createNode(data) If(data >root->data) Node->right = insert(node->left,data) Else If(data data) Node->right = insert(node>right,data) Return node; end上記のアルゴリズムに示されているように、BSTの順序に違反しないように、ノードが適切な位置に配置されていることを確認する必要があります。
上記の一連の図に示されているように、一連の挿入操作を行います。挿入するキーをルートノードと比較した後、適切な位置にリーフノードとして挿入するキーの左または右のサブツリーが選択されます。
＃2）削除
削除操作は、指定されたキーに一致するノードをBSTから削除します。この操作でも、BSTの順序に違反しないように、削除後に残りのノードを再配置する必要があります。
したがって、削除する必要のあるノードに応じて、BSTで削除する場合は次のようになります。
＃1）ノードがリーフノードの場合
削除するノードがリーフノードの場合、ノードを直接削除します。
＃2）ノードに子が1つしかない場合
削除するノードに子が1つしかない場合は、子をノードにコピーして削除します。
＃3）ノードに2つの子がある場合
削除するノードに2つの子がある場合、ノードのインオーダーサクセサを見つけて、インオーダーサクセサをノードにコピーします。後で、インオーダーサクセサを削除します。
2つの子を持つノード6を削除する上記のツリーでは、最初に、削除するノードの順序どおりの後続ノードを見つけます。右側のサブツリーで最小値を見つけることにより、インオーダーサクセサを見つけます。上記の場合、右側のサブツリーの最小値は7です。削除するノードにコピーしてから、インオーダーサクセサを削除します。
＃3）検索
BSTの検索操作は、BSTで「キー」として識別された特定のアイテムを検索します。 BSTでアイテムを検索する利点は、ツリー全体を検索する必要がないことです。代わりに、BSTでの順序付けのため、キーをルートと比較するだけです。
キーがrootと同じである場合、rootを返します。キーがルートでない場合は、キーをルートと比較して、左または右のサブツリーを検索する必要があるかどうかを判断します。サブツリーが見つかったら、キーを検索する必要があり、いずれかのサブツリーでキーを再帰的に検索します。
以下は、BSTでの検索操作のアルゴリズムです。
Search(key) Begin If(root == null || root->data == key) Return root; If(root->key left,key) Else if (root->key >key ) Search(root->right,key); end 
上記のツリーで値6のキーを検索する場合は、最初にキーをルートノードと比較します。つまり、if（6 == 7）=> No if（6<7) =Yes; this means that we will omit the right subtree and search for the key in the left subtree.
次に、左側のサブツリーに降ります。 （6 == 5）=>いいえの場合。
（6いいえ;これは6> 5を意味し、右に移動する必要がある場合。
（6 == 6）=>はいの場合;キーが見つかりました。
＃4）トラバーサル
二分木の探索についてはすでに説明しました。 BSTの場合も、ツリーをトラバースして、inOrder、preorder、またはpostOrderシーケンスを取得できます。実際、Inorder01シーケンスでBSTをトラバースすると、ソートされたシーケンスが取得されます。
これを下の図に示しました。
上記のツリーのトラバーサルは次のとおりです。
インオーダートラバーサル（lnr）：3 5 6 7 8 9 10
プレオーダートラバーサル（nlr）：7 5 3 6 9 8 10
PostOrderトラバーサル（lrn）：3 6 5 8 10 9 7
図
以下のデータから二分探索木を構築しましょう。
45 30 60 65 70
最初の要素をルートノードとして取り上げましょう。
＃1）45
後続のステップでは、バイナリ検索ツリーの定義に従ってデータを配置します。つまり、データが親ノードよりも小さい場合は左の子に配置され、データが親ノードよりも大きい場合はそれが配置されます。正しい子になります。
これらの手順を以下に示します。
＃2）30
＃3）60
＃4）65
＃5）70
先ほど作成した上記のBSTでインオーダートラバーサルを実行すると、シーケンスは次のようになります。
トラバーサルシーケンスには、昇順で配置された要素があることがわかります。
二分探索木実装C ++
C ++実装を使用してBSTとその操作を示しましょう。
#include using namespace std; //declaration for new bst node struct bstnode { int data; struct bstnode *left, *right; }; // create a new BST node struct bstnode *newNode(int key) { struct bstnode *temp = new struct bstnode(); temp->data = key; temp->left = temp->right = NULL; return temp; } // perform inorder traversal of BST void inorder(struct bstnode *root) { if (root != NULL) { inorder(root->left); cout<data<<' '; inorder(root->right); } } /* insert a new node in BST with given key */ struct bstnode* insert(struct bstnode* node, int key) { //tree is empty;return a new node if (node == NULL) return newNode(key); //if tree is not empty find the proper place to insert new node if (key data) node->left = insert(node->left, key); else node->right = insert(node->right, key); //return the node pointer return node; } //returns the node with minimum value struct bstnode * minValueNode(struct bstnode* node) { struct bstnode* current = node; //search the leftmost tree while (current && current->left != NULL) current = current->left; return current; } //function to delete the node with given key and rearrange the root struct bstnode* deleteNode(struct bstnode* root, int key) { // empty tree if (root == NULL) return root; // search the tree and if key data) root->left = deleteNode(root->left, key); // if key > root, go for rightmost tree else if (key > root->data) root->right = deleteNode(root->right, key); // key is same as root else { // node with only one child or no child if (root->left == NULL) { struct bstnode *temp = root->right; free(root); return temp; } else if (root->right == NULL) { struct bstnode *temp = root->left; free(root); return temp; } // node with both children; get successor and then delete the node struct bstnode* temp = minValueNode(root->right); // Copy the inorder successor's content to this node root->data = temp->data; // Delete the inorder successor root->right = deleteNode(root->right, temp->data); } return root; } // main program int main() { /* Let us create following BST 40 / 30 60 65 70*/ struct bstnode *root = NULL; root = insert(root, 40); root = insert(root, 30); root = insert(root, 60); root = insert(root, 65); root = insert(root, 70); cout<<'Binary Search Tree created (Inorder traversal):'< 出力：
作成された二分探索木（順序トラバーサル）：
30 40 60 65 70
Delete node 40
変更された二分探索木の順序トラバーサル：
30 60 65 70
上記のプログラムでは、順序どおりの走査シーケンスのBSTを出力します。
BSTの利点
＃1）検索は非常に効率的です
Linuxは2つのファイルの違いを見つける
BSTのすべてのノードが特定の順序であるため、特定のアイテムの検索は非常に効率的で高速です。これは、ツリー全体を検索してすべてのノードを比較する必要がないためです。
ルートノードを検索しているアイテムと比較するだけで、左または右のサブツリーを検索する必要があるかどうかを判断します。
＃2）配列やリンクリストと比較した場合の効率的な作業
BSTの場合にアイテムを検索すると、すべてのステップで左または右のサブツリーの半分が削除されるため、検索操作のパフォーマンスが向上します。これは、特定のアイテムを検索するためにすべてのアイテムを順番に比較する必要がある配列またはリンクリストとは対照的です。
＃3）挿入と削除が高速
リンクリストや配列などの他のデータ構造と比較すると、挿入および削除操作も高速です。
BSTのアプリケーション
BSTの主なアプリケーションのいくつかは次のとおりです。
- BSTは、データベースアプリケーションにマルチレベルインデックスを実装するために使用されます。
- BSTは、辞書などの構造を実装するためにも使用されます。
- BSTは、さまざまな効率的な検索アルゴリズムを実装するために使用できます。
- BSTは、オンラインストアのように入力としてソートされたリストを必要とするアプリケーションでも使用されます。
- BSTは、式ツリーを使用して式を評価するためにも使用されます。
結論
二分探索木（BST）は二分木のバリエーションであり、ソフトウェア分野で広く使用されています。 BSTの各ノードが特定の順序に従って配置されるため、これらは順序付き二分木とも呼ばれます。
BSTを順番にトラバースすると、アイテムの並べ替えられたシーケンスが昇順で表示されます。 BSTを検索に使用すると、非常に効率的で、短時間で実行されます。 BSTは、ハフマンコーディング、データベースのマルチレベルインデックス作成など、さまざまなアプリケーションにも使用されます。
=> ここで人気のあるC ++トレーニングシリーズを読んでください。
推奨読書