この記事では、二分探索木について説明します。この記事は、コースの重要なトピックであるため、技術的な背景を持つ学生にとって非常に役立ち、有益です。
二分探索ツリーに直接進む前に、まずツリーの簡単な説明を見てみましょう。
木とは何ですか？
ツリーは、データを階層形式で表すために使用されるデータ構造の一種です。これは、階層をシミュレートするために相互にリンクされるノードと呼ばれるオブジェクトまたはエンティティのコレクションとして定義できます。ツリー内のデータは線形または順次に格納されないため、ツリーは非線形データ構造です。
さて、本題の二分探索ツリーを始めましょう。
二分探索木とは何ですか?
二分探索木は、ある順序に従って要素を配置します。二分探索木では、左ノードの値は親ノードより小さく、右ノードの値は親ノードより大きくなければなりません。このルールは、ルートの左右のサブツリーに再帰的に適用されます。
例を挙げて二分探索木の概念を理解しましょう。
上の図では、ルート ノードが 40 で、左側のサブツリーのすべてのノードがルート ノードより小さく、右側のサブツリーのすべてのノードがルート ノードより大きいことがわかります。
同様に、ルート ノードの左の子は左の子より大きく、右の子より小さいことがわかります。したがって、二分探索木の性質も満たします。したがって、上の画像の木は二分探索木であると言えます。
上記のツリーのノード 35 の値を 55 に変更した場合、そのツリーが二分探索木になるかどうかを確認します。
ランダムc
上の木では、ルート ノードの値は 40 で、左の子の 30 よりは大きいですが、30 の右の子の 55 よりは小さいため、上の木は二分探索木の性質を満たしていません。したがって、上記の木は二分探索木ではありません。
二分探索木の利点
- 二分探索ツリー内の要素の検索は、どのサブツリーに目的の要素があるかというヒントが常に得られるため、簡単です。
- 配列やリンク リストと比較して、BST では挿入と削除の操作が高速になります。
二分探索木の作成例
ここで、例を使用して二分探索木の作成を見てみましょう。
データ要素が次のとおりであるとします。 - 45、15、79、90、10、55、12、20、50
- まず、挿入する必要があります 4つ。 木の根として木の中に。
- 次に、次の要素を読み取ります。ルート ノードより小さい場合は、それを左側のサブツリーのルートとして挿入し、次の要素に移動します。
- それ以外の場合、要素がルート ノードより大きい場合は、その要素を右サブツリーのルートとして挿入します。
ここで、指定されたデータ要素を使用して二分探索ツリーを作成するプロセスを見てみましょう。 BST を作成するプロセスを以下に示します。
ステップ 1 - 45 を挿入します。
ステップ 2 - 15 を挿入します。
15 は 45 より小さいため、左側のサブツリーのルート ノードとして挿入します。
ワンパスワールド
ステップ 3 - 79 を挿入します。
79 は 45 より大きいため、右のサブツリーのルート ノードとして挿入します。
ステップ 4 - 90 を挿入します。
90 は 45 および 79 より大きいため、79 の右側のサブツリーとして挿入されます。
ステップ 5 - 10 を挿入します。
10 は 45 および 15 より小さいため、15 の左側のサブツリーとして挿入されます。
ステップ 6 - 55 を挿入します。
55 は 45 より大きく、79 より小さいため、79 の左側のサブツリーとして挿入されます。
ステップ 7 - 12 を挿入します。
12 は 45 および 15 より小さいですが、10 より大きいため、10 の右側のサブツリーとして挿入されます。
ステップ 8 - 20 を挿入します。
データ構造内のハッシュ化
20 は 45 より小さいですが 15 より大きいため、15 の右側のサブツリーとして挿入されます。
ステップ 9 - 50 を挿入します。
50 は 45 より大きいですが、79 および 55 より小さいため、55 の左側のサブツリーとして挿入されます。
これで二分探索木の作成は完了です。その後、二分探索木で実行できる操作に進みましょう。
二分探索ツリー上で挿入、削除、検索操作を実行できます。
二分探索木で検索がどのように実行されるかを理解しましょう。
二分探索木での検索
検索とは、データ構造内の特定の要素またはノードを検索または配置することを意味します。二分探索木では、BST の要素が特定の順序で格納されているため、ノードの検索が簡単です。二分探索ツリーでノードを検索する手順は次のとおりです。
- まず、検索対象の要素とツリーのルート要素を比較します。
- ルートがターゲット要素と一致する場合、ノードの位置を返します。
- 一致しない場合は、項目がルート要素より小さいかどうかを確認し、ルート要素より小さい場合は、左側のサブツリーに移動します。
- ルート要素より大きい場合は、右のサブツリーに移動します。
- 一致するものが見つかるまで、上記の手順を再帰的に繰り返します。
- 要素が見つからないか、ツリー内に存在しない場合は、NULL を返します。
ここで、例を使用して二分木での検索を理解しましょう。上記で形成された二分探索木を使用します。以下のツリーからノード 20 を見つける必要があるとします。
ステップ1：
ステップ2：
ステップ3:
ここで、二分探索ツリー内の要素を検索するアルゴリズムを見てみましょう。
二分探索木内の要素を検索するアルゴリズム
Search (root, item) Step 1 - if (item = root → data) or (root = NULL) return root else if (item <root 2 → data) return search(root left, item) else right, end if step - < pre> <p>Now let's understand how the deletion is performed on a binary search tree. We will also see an example to delete an element from the given tree.</p> <h3>Deletion in Binary Search tree</h3> <p>In a binary search tree, we must delete a node from the tree by keeping in mind that the property of BST is not violated. To delete a node from BST, there are three possible situations occur -</p> <ul> <li>The node to be deleted is the leaf node, or,</li> <li>The node to be deleted has only one child, and,</li> <li>The node to be deleted has two children</li> </ul> <p>We will understand the situations listed above in detail.</p> <p> <strong>When the node to be deleted is the leaf node</strong> </p> <p>It is the simplest case to delete a node in BST. Here, we have to replace the leaf node with NULL and simply free the allocated space.</p> <p>We can see the process to delete a leaf node from BST in the below image. In below image, suppose we have to delete node 90, as the node to be deleted is a leaf node, so it will be replaced with NULL, and the allocated space will free.</p> <img src="//techcodeview.com/img/ds-tutorial/58/binary-search-tree-15.webp" alt="Binary Search tree"> <p> <strong>When the node to be deleted has only one child</strong> </p> <p>In this case, we have to replace the target node with its child, and then delete the child node. It means that after replacing the target node with its child node, the child node will now contain the value to be deleted. So, we simply have to replace the child node with NULL and free up the allocated space.</p> <p>We can see the process of deleting a node with one child from BST in the below image. In the below image, suppose we have to delete the node 79, as the node to be deleted has only one child, so it will be replaced with its child 55.</p> <p>So, the replaced node 79 will now be a leaf node that can be easily deleted.</p> <img src="//techcodeview.com/img/ds-tutorial/58/binary-search-tree-16.webp" alt="Binary Search tree"> <p> <strong>When the node to be deleted has two children</strong> </p> <p>This case of deleting a node in BST is a bit complex among other two cases. In such a case, the steps to be followed are listed as follows -</p> <ul> <li>First, find the inorder successor of the node to be deleted.</li> <li>After that, replace that node with the inorder successor until the target node is placed at the leaf of tree.</li> <li>And at last, replace the node with NULL and free up the allocated space.</li> </ul> <p>The inorder successor is required when the right child of the node is not empty. We can obtain the inorder successor by finding the minimum element in the right child of the node.</p> <p>We can see the process of deleting a node with two children from BST in the below image. In the below image, suppose we have to delete node 45 that is the root node, as the node to be deleted has two children, so it will be replaced with its inorder successor. Now, node 45 will be at the leaf of the tree so that it can be deleted easily.</p> <img src="//techcodeview.com/img/ds-tutorial/58/binary-search-tree-17.webp" alt="Binary Search tree"> <p>Now let's understand how insertion is performed on a binary search tree.</p> <h3>Insertion in Binary Search tree</h3> <p>A new key in BST is always inserted at the leaf. To insert an element in BST, we have to start searching from the root node; if the node to be inserted is less than the root node, then search for an empty location in the left subtree. Else, search for the empty location in the right subtree and insert the data. Insert in BST is similar to searching, as we always have to maintain the rule that the left subtree is smaller than the root, and right subtree is larger than the root.</p> <p>Now, let's see the process of inserting a node into BST using an example.</p> <img src="//techcodeview.com/img/ds-tutorial/58/binary-search-tree-18.webp" alt="Binary Search tree"> <br> <img src="//techcodeview.com/img/ds-tutorial/58/binary-search-tree-19.webp" alt="Binary Search tree"> <h3>The complexity of the Binary Search tree</h3> <p>Let's see the time and space complexity of the Binary search tree. We will see the time complexity for insertion, deletion, and searching operations in best case, average case, and worst case.</p> <h3>1. Time Complexity</h3> <table class="table"> <tr> <th>Operations</th> <th>Best case time complexity</th> <th>Average case time complexity</th> <th>Worst case time complexity</th> </tr> <tr> <td> <strong>Insertion</strong> </td> <td>O(log n)</td> <td>O(log n)</td> <td>O(n)</td> </tr> <tr> <td> <strong>Deletion</strong> </td> <td>O(log n)</td> <td>O(log n)</td> <td>O(n)</td> </tr> <tr> <td> <strong>Search</strong> </td> <td>O(log n)</td> <td>O(log n)</td> <td>O(n)</td> </tr> </table> <p>Where 'n' is the number of nodes in the given tree.</p> <h3>2. Space Complexity</h3> <table class="table"> <tr> <th>Operations</th> <th>Space complexity</th> </tr> <tr> <td> <strong>Insertion</strong> </td> <td>O(n)</td> </tr> <tr> <td> <strong>Deletion</strong> </td> <td>O(n)</td> </tr> <tr> <td> <strong>Search</strong> </td> <td>O(n)</td> </tr> </table> <ul> <li>The space complexity of all operations of Binary search tree is O(n).</li> </ul> <h2>Implementation of Binary search tree</h2> <p>Now, let's see the program to implement the operations of Binary Search tree.</p> <p> <strong>Program:</strong> Write a program to perform operations of Binary Search tree in C++.</p> <p>In this program, we will see the implementation of the operations of binary search tree. Here, we will see the creation, inorder traversal, insertion, and deletion operations of tree.</p> <p>Here, we will see the inorder traversal of the tree to check whether the nodes of the tree are in their proper location or not. We know that the inorder traversal always gives us the data in ascending order. So, after performing the insertion and deletion operations, we perform the inorder traversal, and after traversing, if we get data in ascending order, then it is clear that the nodes are in their proper location.</p> <pre> #include using namespace std; struct Node { int data; Node *left; Node *right; }; Node* create(int item) { Node* node = new Node; node->data = item; node->left = node->right = NULL; return node; } /*Inorder traversal of the tree formed*/ void inorder(Node *root) { if (root == NULL) return; inorder(root->left); //traverse left subtree cout<data <right); traverse right subtree } node* findminimum(node* cur) *to find the inorder successor* { while(cur->left != NULL) { cur = cur->left; } return cur; } Node* insertion(Node* root, int item) /*Insert a node*/ { if (root == NULL) return create(item); /*return new node if tree is empty*/ if (item data) root->left = insertion(root->left, item); else root->right = insertion(root->right, item); return root; } void search(Node* &cur, int item, Node* &parent) { while (cur != NULL && cur->data != item) { parent = cur; if (item data) cur = cur->left; else cur = cur->right; } } void deletion(Node*& root, int item) /*function to delete a node*/ { Node* parent = NULL; Node* cur = root; search(cur, item, parent); /*find the node to be deleted*/ if (cur == NULL) return; if (cur->left == NULL && cur->right == NULL) /*When node has no children*/ { if (cur != root) { if (parent->left == cur) parent->left = NULL; else parent->right = NULL; } else root = NULL; free(cur); } else if (cur->left && cur->right) { Node* succ = findMinimum(cur->right); int val = succ->data; deletion(root, succ->data); cur->data = val; } else { Node* child = (cur->left)? cur->left: cur->right; if (cur != root) { if (cur == parent->left) parent->left = child; else parent->right = child; } else root = child; free(cur); } } int main() { Node* root = NULL; root = insertion(root, 45); root = insertion(root, 30); root = insertion(root, 50); root = insertion(root, 25); root = insertion(root, 35); root = insertion(root, 45); root = insertion(root, 60); root = insertion(root, 4); printf('The inorder traversal of the given binary tree is -
'); inorder(root); deletion(root, 25); printf('
After deleting node 25, the inorder traversal of the given binary tree is -
'); inorder(root); insertion(root, 2); printf('
After inserting node 2, the inorder traversal of the given binary tree is -
'); inorder(root); return 0; } </data></pre> <p> <strong>Output</strong> </p> <p>After the execution of the above code, the output will be -</p> <img src="//techcodeview.com/img/ds-tutorial/58/binary-search-tree-20.webp" alt="Binary Search tree"> <p>So, that's all about the article. Hope the article will be helpful and informative to you.</p> <hr></root> 出力
スクロールホイールが機能しない
上記のコードを実行すると、出力は次のようになります -
それでは、この記事については以上です。この記事があなたにとって有益で有益であることを願っています。