개요
이 튜토리얼에서는 이진 탐색 트리(Binary Search Tree, BST)에서 합이 주어진 숫자와 같아지는 모든 쌍(pair)을 찾는 프로그램을 작성해 보겠습니다.
핵심 아이디어는 트리의 노드 값을 두 개의 별도 리스트(왼쪽 경로와 오른쪽 경로)에 저장한 뒤, 정렬된 배열에서 두 포인터를 사용하는 것처럼 양 끝에서부터 값을 비교해 나가는 것입니다. 그럼 문제 해결 단계를 하나씩 살펴보겠습니다.
문제 해결 단계
이진 트리를 위한 구조체(
struct Node)를 생성합니다.이진 탐색 트리에 새 노드를 삽입하는 함수를 작성합니다.
BST에서는 루트보다 작은 값은 항상 왼쪽에, 큰 값은 오른쪽에 위치한다는 점을 기억하세요.
트리의 왼쪽 노드와 오른쪽 노드를 각각 저장할 빈 리스트 두 개를 초기화합니다.
왼쪽 또는 오른쪽 노드가 NULL이 되거나 두 리스트가 모두 비워질 때까지 트리를 순회합니다.
반복문을 사용해 왼쪽 노드 리스트에 모든 요소를 저장합니다.
반복문을 사용해 오른쪽 노드 리스트에 모든 요소를 저장합니다.
각 리스트에서 마지막 노드를 가져옵니다.
두 값을 비교합니다.
왼쪽 노드의 값이 오른쪽 노드의 값보다 크거나 같으면 반복문을 종료합니다.
두 값의 합이 주어진 숫자와 같으면 해당 쌍을 출력하고 두 노드를 리스트에서 제거합니다.
두 값의 합이 주어진 숫자보다 작으면 왼쪽 리스트의 마지막 노드를 제거하고 해당 노드의 오른쪽 자식으로 이동합니다.
두 값의 합이 주어진 숫자보다 크면 오른쪽 리스트의 마지막 노드를 제거하고 해당 노드의 왼쪽 자식으로 이동합니다.
예제 코드
전체 코드를 살펴보겠습니다.
#include<bits/stdc++.h>
using namespace std;
struct Node{
int data;
Node *left, *right, *root;
Node(int data) {
this->data = data;
left = NULL;
right = NULL;
root = NULL;
}
};
Node* insertNewNode(Node *root, int data){
if (root == NULL) {
root = new Node(data);
return root;
}
if (root->data < data) {
root->right = insertNewNode(root->right, data);
}
else if (root->data > data) {
root->left = insertNewNode(root->left, data);
}
return root;
}
void findThePairs(Node *node, int target) {
vector<Node*> left_side_nodes;
vector<Node*> right_side_nodes;
Node *current_left = node;
Node *current_right = node;
while (current_left != NULL || current_right != NULL || (left_side_nodes.size() > 0 && right_side_nodes.size() > 0)) {
while (current_left != NULL) {
left_side_nodes.push_back(current_left);
current_left = current_left->left;
}
while (current_right != NULL) {
right_side_nodes.push_back(current_right);
current_right = current_right->right;
}
Node *left_side_node = left_side_nodes[left_side_nodes.size() - 1];
Node *right_side_node = right_side_nodes[right_side_nodes.size() - 1];
int left_side_value = left_side_node->data;
int right_side_value = right_side_node->data;
if (left_side_value >= right_side_value) {
break;
}
if (left_side_value + right_side_value < target) {
left_side_nodes.pop_back();
current_left = left_side_node->right;
}
else if (left_side_value + right_side_value > target) {
right_side_nodes.pop_back();
current_right = right_side_node->left;
}
else {
cout << left_side_node->data << " " << right_side_node->data << endl;
right_side_nodes.pop_back();
left_side_nodes.pop_back();
current_left = left_side_node->right;
current_right = right_side_node->left;
}
}
}
int main() {
Node *root = NULL;
root = insertNewNode(root, 25);
root = insertNewNode(root, 20);
root = insertNewNode(root, 30);
root = insertNewNode(root, 15);
root = insertNewNode(root, 21);
root = insertNewNode(root, 19);
root = insertNewNode(root, 31);
findThePairs(root, 50);
}위 코드는 값 25, 20, 30, 15, 21, 19, 31로 이진 탐색 트리를 구성한 뒤, 합이 50이 되는 모든 쌍을 찾는 예제입니다.
실행 결과
위 코드를 실행하면 다음과 같은 결과가 출력됩니다.
19 31 20 30
복잡도 분석
시간 복잡도: O(n) — 각 노드는 최대 한 번씩만 방문되므로 전체 트리 순회에 선형 시간이 걸립니다.
공간 복잡도: O(h) — h는 트리의 높이이며, 두 개의 리스트에는 최대 트리 높이만큼의 노드만 저장됩니다.
마무리
이번 튜토리얼에서는 두 개의 리스트와 투 포인터 방식을 활용해 이진 탐색 트리에서 목표 합계를 만족하는 모든 쌍을 효율적으로 찾는 방법을 배웠습니다. 진행하면서 궁금한 점이 있다면 댓글로 남겨주세요.