Nagie's DevStory
[DATA STRUCTURE] 10. 이진 탐색 트리(Binary Search Tree) 본문
[DATA STRUCTURE] 10. 이진 탐색 트리(Binary Search Tree)
Nagie 2023. 11. 25. 21:05이진 탐색 트리(Binary Search Tree, BST)는 각 노드가 최대 두 개의 자식 노드를 가지며, 각 노드의 왼쪽 서브 트리는
해당 노드보다 작은 값, 오른쪽 서브 트리는 해당 노드보다 큰 값으로 구성된 이진 트리이다.
이 특성 덕에 효율적인 탐색과 정렬된 데이터 저장이라는 장점을 가지고 있지만,
데이터의 균형을 유지하는 추가적인 작업이 필요하며 최악의 경우 성능이 저하되는 단점을 가지고 있다.
위와 같은 단점을 해결한 균형 트리는 대표적으로 AVL 트리, 레드-블랙 트리, B 트리, 스플레이 트리 등이 있다.
#pragma once
#include <iostream>
struct Node {
int data;
Node* left;
Node* right;
Node(int d) : data(d), left(nullptr), right(nullptr) {}
};
class BinarySearchTree {
private:
Node* root = nullptr;
void insert_impl(Node* curr, int value) {
if (value < curr->data) {
if (!curr->left) {
curr->left = new Node(value);
} else {
insert_impl(curr->left, value);
}
} else {
if (!curr->right) {
curr->right = new Node(value);
} else {
insert_impl(curr->right, value);
}
}
}
Node* erase_impl(Node* node, int value) {
if (!node) {
return nullptr;
}
if (value < node->data) {
node->left = erase_impl(node->left, value);
} else if (value > node->data) {
node->right = erase_impl(node->right, value);
} else {
if (node->left && node->right) {
auto succ = successor(node);
node->data = succ->data;
node->right = erase_impl(node->right, succ->data);
} else {
auto tmp = node->left ? node->left : node->right;
delete node;
return tmp;
}
}
return node;
}
Node* find_impl(Node* curr, int value) {
if (curr == nullptr) {
return nullptr;
}
if (value == curr->data) {
return curr;
} else {
if (value < curr->data) {
return find_impl(curr->left, value);
} else {
return find_impl(curr->right, value);
}
}
}
void inorder_impl(Node* curr) {
if (curr != nullptr) {
inorder_impl(curr->left);
std::cout << curr->data << ", ";
inorder_impl(curr->right);
}
}
Node* successor(Node* node) {
auto curr = node->right;
while (curr && curr->left) {
curr = curr->left;
}
return curr;
}
void delete_tree(Node* node) {
if (node) {
delete_tree(node->left);
delete_tree(node->right);
delete node;
}
}
public:
~BinarySearchTree() {
delete_tree(root);
}
void insert(int value) {
if (!root) {
root = new Node(value);
} else {
insert_impl(root, value);
}
}
void erase(int value) {
root = erase_impl(root, value);
}
Node* find(int value) {
return find_impl(root, value);
}
void inorder() {
inorder_impl(root);
}
};
특징
1. 정렬된 구조 : 각 노드의 왼쪽 서브 트리는 해당 노드보다 작은 값, 오른쪽 서브 트리는 해당 노드보다 큰 값이기 때문에
중위 순회를 통해 트리를 순회하면 정렬된 순서로 데이터를 조회할 수 있다.
2. 효율적인 탐색 : 탐색 작업의 시간 복잡도는 트리의 높이에 비례하며 평균적으로 O(h) 즉 O(log n)이다.
다만 최악의 상황에는 트리가 연결 리스트와 유사한 형태가 되어 O(n)의 시간 복잡도를 가질 수 있다.
3. 효율적인 삽입과 삭제 : 데이터를 삽입하거나 삭제할 때도 탐색과 마찬가지로 트리의 높이에 비례하는 시간이 소요된다.
장점
1. 효율적인 탐색 : 탐색 작업이 효율적이다.
2. 정렬된 데이터 저장 : 중위 순회를 통해 데이터를 정렬된 순서로 조회할 수 있다.
3. 간단한 구현 : 다른 트리와 비교했을 때 상대적으로 구현하기가 간단한 편이며 직관적이다.
(특징이 곧 장점이다.)
단점
1. 균형 유지가 필요 : 삽입, 삭제 작업이 연속적으로 일어날 경우 트리가 한쪽으로 치우쳐 불균형한 상태가 될 수 있다.
이를 해결하기 위해 균형을 유지하는 추가적인 작업이 필요하며, 이 과정이 상당히 복잡할 수 있다.
2. 최악의 경우 성능 하락 : 트리가 한쪽으로 치우쳐지면 연결 리스트와 유사한 구조가 되어 탐색, 삽입, 삭제 작업의 성능이
최악의 경우 O(n)에 가까워질 수 있다.
3. 메모리 사용량 증가 : 포인터를 사용하여 노드를 저장하므로 메모리 사용량이 증가할 수 있다.