TUTORIAL · Data Structure
이진 검색 트리 반복 삽입
이 튜토리얼에서는 이진 검색 트리의 반복 삽입을 소개합니다.
이전 기사 이진 탐색 트리에서 BST에 노드를 삽입하는 재귀 적 접근 방식에 대해 논의했습니다. 이 게시물에서는 BST에 노드를 삽입하는 반복적 인 접근 방식에 대해 설명합니다. 반복 삽입 알고리즘에 추가 공간이 필요하지 않으므로 재귀 방법보다 좋습니다.
BST 반복 삽입 알고리즘
root를 BST의 루트 노드로,key를 삽입하려는 요소로 설정합니다.
-
삽입 할 노드 생성-
toinsert. -
두 개의 포인터를 초기화합니다.
curr는root를 가리키고prev는 null을 가리 킵니다. (curr는 트리를 가로 지르고prev는 트레일을 유지합니다). -
curr! =NULL동안 다음을 수행합니다.이전을curr로 업데이트하여 추적을 유지합니다.curr->data>key인 경우curr를curr->left로 설정하고 오른쪽 하위 트리를 삭제합니다.curr->data<key인 경우curr를curr->right로 설정하고 왼쪽 하위 트리를 삭제합니다.
-
prev==NULL이면 트리가 비어 있음을 의미합니다.root노드를 만듭니다. -
그렇지 않으면
prev->data>key이면prev의 왼쪽에toinsert를 삽입합니다.prev->left=toinsert. -
그렇지 않으면
prev->data<key인 경우prev의 오른쪽에toinsert를 삽입하고prev->right=toinsert를 삽입합니다.
BST 반복 삽입 그림
-
먼저
root노드를 생성하여 BST를 초기화하고 여기에5를 삽입합니다. -
3은5보다 작아서5의 왼쪽에 삽입됩니다. -
4는5보다 작지만3보다 커서3의 오른쪽에 삽입되고4의 왼쪽에 삽입됩니다. -
2는 현재 트리에서 가장 작은 요소이므로 가장 왼쪽에 삽입됩니다. -
1은 현재 트리에서 가장 작은 요소이므로 가장 왼쪽에 삽입됩니다. -
6은 현재 트리에서 가장 큰 요소이므로 가장 오른쪽에 삽입됩니다.
이것이 BST 안에 요소를 삽입하는 방법입니다.
BST 반복 삽입 구현
#include <iostream>
using namespace std;
class Node {
public:
int key;
Node *left, *right;
};
Node *newNode(int item) {
Node *temp = new Node;
temp->key = item;
temp->left = temp->right = NULL;
return temp;
}
void inorder(Node *root) {
if (root != NULL) {
inorder(root->left);
cout << root->key << " ";
inorder(root->right);
}
}
void insert(Node *&root, int key) {
Node *toinsert = newNode(key);
Node *curr = root;
Node *prev = NULL;
while (curr != NULL) {
prev = curr;
if (key < curr->key)
curr = curr->left;
else
curr = curr->right;
}
if (prev == NULL) {
prev = toinsert;
root = prev;
}
else if (key < prev->key)
prev->left = toinsert;
else
prev->right = toinsert;
}
int main() {
Node *root = NULL;
insert(root, 5);
insert(root, 3);
insert(root, 8);
insert(root, 6);
insert(root, 4);
insert(root, 2);
insert(root, 1);
insert(root, 7);
inorder(root);
}
BST 반복 삽입 알고리즘 복잡성
시간 복잡성
- 평균 사례
평균적인 경우 BST에 노드를 삽입하는 시간 복잡도는 이진 검색 트리의 높이 정도입니다. 평균적으로 BST의 높이는O(logn)입니다. 형성된 BST가 균형 BST 일 때 발생합니다. 따라서 시간 복잡도는 [Big Theta]:O(logn)의 순서입니다.
- 베스트 케이스
최상의 경우는 트리가 균형 잡힌 BST 일 때 발생합니다. 삽입의 최상의 경우 시간 복잡도는O(logn)의 순서입니다. 평균 케이스 시간 복잡성과 동일합니다.
- 최악의 경우
최악의 경우 루트에서 가장 깊은 리프 노드, 즉 트리의 전체 높이h로 이동해야 할 수 있습니다. 트리의 균형이 맞지 않는 경우, 즉 치우친 경우 트리의 높이가n이 될 수 있으므로 삽입 및 검색 작업의 최악의 경우 시간 복잡성은O(n)입니다.
공간 복잡성
반복 삽입 작업의 공간 복잡성은 추가 공간이 필요하지 않기 때문에O(1)입니다.
