이번 포스팅에서는 이진 검색 트리에 대해 알아보겠습니다. 이 기사는 과정의 중요한 주제이므로 기술적 배경을 가진 학생들에게 매우 유용하고 유익할 것입니다.
이진 검색 트리로 직접 이동하기 전에 먼저 트리에 대한 간략한 설명을 살펴보겠습니다.
나무란 무엇인가?
트리는 데이터를 계층적 형태로 표현하는 데 사용되는 일종의 데이터 구조입니다. 이는 계층 구조를 시뮬레이션하기 위해 함께 연결된 노드라고 불리는 개체 또는 엔터티의 컬렉션으로 정의할 수 있습니다. 트리는 트리의 데이터가 선형 또는 순차적으로 저장되지 않으므로 비선형 데이터 구조입니다.
이제 이진 검색 트리라는 주제를 시작하겠습니다.
이진 검색 트리란 무엇입니까?
이진 검색 트리는 요소를 정렬하기 위해 어떤 순서를 따릅니다. 이진 탐색 트리에서는 왼쪽 노드의 값이 부모 노드보다 작아야 하고, 오른쪽 노드의 값이 부모 노드보다 커야 합니다. 이 규칙은 루트의 왼쪽 및 오른쪽 하위 트리에 재귀적으로 적용됩니다.
예를 들어 이진 검색 트리의 개념을 이해해 봅시다.
위 그림에서 루트 노드는 40이고, 왼쪽 하위 트리의 모든 노드는 루트 노드보다 작고, 오른쪽 하위 트리의 모든 노드는 루트 노드보다 크다는 것을 알 수 있습니다.
마찬가지로 루트 노드의 왼쪽 자식이 왼쪽 자식보다 크고 오른쪽 자식보다 작은 것을 볼 수 있습니다. 따라서 이진 탐색 트리의 특성도 만족한다. 따라서 위 이미지의 트리는 이진 검색 트리라고 말할 수 있습니다.
위의 트리에서 노드 35의 값을 55로 변경하면 트리가 이진 검색 트리가 될지 여부를 확인한다고 가정합니다.
위 트리에서 루트 노드의 값은 40으로 왼쪽 자식 노드인 30보다 크고 오른쪽 자식 노드인 30(즉, 55)보다는 작습니다. 따라서 위 트리는 이진 검색 트리의 속성을 만족하지 않습니다. 따라서 위의 트리는 이진 검색 트리가 아닙니다.
이진 검색 트리의 장점
- 어떤 하위 트리에 원하는 요소가 있는지에 대한 힌트가 항상 있으므로 이진 검색 트리에서 요소를 검색하는 것은 쉽습니다.
- 배열 및 연결 목록에 비해 BST에서는 삽입 및 삭제 작업이 더 빠릅니다.
이진 검색 트리 생성의 예
이제 예제를 사용하여 이진 검색 트리가 생성되는 것을 살펴보겠습니다.
데이터 요소가 다음과 같다고 가정합니다. - 45, 15, 79, 90, 10, 55, 12, 20, 50
- 먼저, 삽입해야 합니다. 넷 다섯 나무의 뿌리로서 나무에 들어갑니다.
- 그런 다음 다음 요소를 읽으십시오. 루트 노드보다 작으면 왼쪽 하위 트리의 루트로 삽입하고 다음 요소로 이동합니다.
- 그렇지 않고 요소가 루트 노드보다 크면 오른쪽 하위 트리의 루트로 삽입합니다.
이제 주어진 데이터 요소를 사용하여 이진 검색 트리를 생성하는 과정을 살펴보겠습니다. 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> 산출
위 코드를 실행한 후 출력은 다음과 같습니다.
이것이 기사의 전부입니다. 이 기사가 귀하에게 도움이 되고 유익한 정보가 되기를 바랍니다.