binary search tree c
작업, C ++ 구현, 장점 및 예제 프로그램을 포함한 C ++의 이진 검색 트리 (BST)에 대한 자세한 자습서 :
제품 테스터가되는 방법
일반적으로 불리는 이진 검색 트리 또는 BST는 다음 조건을 충족하는 이진 트리입니다.
- BST의 왼쪽 자식으로 배치 된 루트 노드보다 작은 노드입니다.
- BST의 오른쪽 자식으로 배치 된 루트 노드보다 큰 노드입니다.
- 왼쪽 및 오른쪽 하위 트리는 차례로 이진 검색 트리입니다.
특정 순서로 키를 정렬하는 이러한 배열은 프로그래머가 검색, 삽입, 삭제 등과 같은 작업을보다 효율적으로 수행 할 수 있도록합니다. 노드가 정렬되지 않은 경우 작업 결과를 얻기 전에 각 노드를 비교해야 할 수 있습니다.
=> 여기에서 전체 C ++ 교육 시리즈를 확인하십시오.
학습 내용 :
이진 검색 트리 C ++
샘플 BST는 아래와 같습니다.
이진 검색 트리는 이러한 특정 노드 순서 때문에 '순서있는 이진 트리'라고도합니다.
위의 BST에서 왼쪽 하위 트리에는 루트 (즉, 45)보다 작은 노드가 있고 오른쪽 하위 트리에는 45보다 큰 노드가 있음을 알 수 있습니다.
이제 BST의 몇 가지 기본 작업에 대해 설명하겠습니다.
기본 작동
# 1) 삽입
삽입 작업은 이진 검색 트리에 새 노드를 추가합니다.
이진 검색 트리 삽입 작업에 대한 알고리즘은 다음과 같습니다.
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) 노드에 자식이 하나 뿐인 경우
삭제할 노드에 자식이 하나만 있으면 자식을 노드에 복사하고 자식을 삭제합니다.
# 3) 노드에 두 자녀가있는 경우
삭제할 노드에 두 개의 자식이있는 경우 노드의 inorder 후속 작업을 찾은 다음 inorder 후속 작업을 노드에 복사합니다. 나중에 inorder 후속 작업을 삭제합니다.
두 개의 자식이있는 노드 6을 삭제하는 위의 트리에서 먼저 삭제할 해당 노드의 inorder 후속 작업을 찾습니다. 오른쪽 하위 트리에서 최소값을 찾아서 inorder 후속 작업을 찾습니다. 위의 경우 오른쪽 하위 트리의 최소값은 7입니다. 삭제할 노드에 복사 한 다음 inorder 후속 작업을 삭제합니다.
# 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 
Windows에서 .jar 파일을 실행하는 방법
위의 트리에서 값이 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를 탐색 할 때 정렬 된 시퀀스를 얻습니다.
아래 그림에서이를 보여주었습니다.
위의 트리에 대한 순회는 다음과 같습니다.
Inorder traversal (lnr) : 3 5678 9 10
사전 주문 순회 (nlr) : 7 5 3 6 9 8 10
주문 후 순회 (lrn) : 3 6 5 8 10 9 7
삽화
아래 주어진 데이터로 이진 검색 트리를 구성 해 보겠습니다.
45 30 60 65 70
첫 번째 요소를 루트 노드로 사용하겠습니다.
# 1) 45
다음 단계에서는 이진 검색 트리의 정의에 따라 데이터를 배치합니다. 즉 데이터가 부모 노드보다 작 으면 왼쪽 자식에 배치되고 데이터가 부모 노드보다 크면 데이터가 배치됩니다. 올바른 아이가 될 것입니다.
이러한 단계는 다음과 같습니다.
# 2) 30
# 3) 60
# 4) 65
# 5) 70
우리가 방금 생성 한 위의 BST에서 inorder traversal을 수행하면 시퀀스는 다음과 같습니다.
순회 시퀀스에 오름차순으로 정렬 된 요소가 있음을 알 수 있습니다.
이진 검색 트리 구현 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
삽입 정렬 이중 연결 목록 자바
수정 된 이진 검색 트리에 대한 Inorder traversal :
30 60 65 70
위의 프로그램에서는 순회 순회 시퀀스에 대한 BST를 출력합니다.
BST의 장점
# 1) 검색은 매우 효율적입니다
BST의 모든 노드가 특정 순서로되어 있으므로 특정 항목을 검색하는 것이 매우 효율적이고 빠릅니다. 전체 트리를 검색하고 모든 노드를 비교할 필요가 없기 때문입니다.
루트 노드를 검색중인 항목과 비교 한 다음 왼쪽 또는 오른쪽 하위 트리에서 검색해야하는지 여부를 결정하기 만하면됩니다.
# 2) 배열 및 연결 목록과 비교할 때 효율적인 작업
BST의 경우 항목을 검색 할 때 모든 단계에서 왼쪽 또는 오른쪽 하위 트리의 절반을 제거하여 검색 성능을 향상시킵니다. 이는 특정 항목을 검색하기 위해 모든 항목을 순차적으로 비교해야하는 배열 또는 연결 목록과는 대조적입니다.
# 3) 삽입 및 삭제가 더 빠름
연결 목록 및 배열과 같은 다른 데이터 구조와 비교할 때 삽입 및 삭제 작업도 더 빠릅니다.
BST의 응용
BST의 주요 응용 프로그램은 다음과 같습니다.
- BST는 데이터베이스 응용 프로그램에서 다단계 인덱싱을 구현하는 데 사용됩니다.
- BST는 사전과 같은 구조를 구현하는데도 사용됩니다.
- BST는 다양한 효율적인 검색 알고리즘을 구현하는 데 사용할 수 있습니다.
- BST는 온라인 상점과 같이 입력으로 정렬 된 목록이 필요한 애플리케이션에서도 사용됩니다.
- BST는 식 트리를 사용하여 식을 평가하는데도 사용됩니다.
결론
이진 검색 트리 (BST)는 이진 트리의 변형이며 소프트웨어 분야에서 널리 사용됩니다. BST의 각 노드는 특정 순서에 따라 배치되므로 정렬 된 이진 트리라고도합니다.
BST의 Inorder traversal은 오름차순으로 정렬 된 항목 순서를 제공합니다. BST를 검색에 사용하면 매우 효율적이며 시간 내에 수행됩니다. BST는 Huffman의 코딩, 데이터베이스의 다중 레벨 인덱싱 등과 같은 다양한 애플리케이션에도 사용됩니다.
=> 여기에서 인기있는 C ++ 교육 시리즈를 읽어보십시오.
추천 도서