이진 탐색 트리 반복자란?
이진 트리를 위한 반복자(iterator)를 만든다고 가정해 봅시다. 이 반복자는 두 가지 핵심 메서드를 제공해야 합니다.
- next(): 다음으로 작은 원소를 반환하는 메서드
- hasNext(): 다음 원소가 존재하는지 여부를 불리언(Boolean) 값으로 반환하는 메서드
예를 들어 다음과 같은 트리가 있다고 가정하겠습니다.
함수 호출 순서가 [next(), next(), hasNext(), next(), hasNext(), next(), hasNext(), next(), hasNext()]라면, 출력 결과는 [3, 7, true, 9, true, 15, true, 20, false]가 됩니다.
문제 해결 접근 방법
이 문제는 스택(Stack)을 활용한 중위 순회(Inorder Traversal) 방식으로 해결할 수 있습니다. 각 메서드의 동작 로직은 다음과 같습니다.
1. next() 메서드
- 스택의 최상단(top) 노드를 현재 노드(curr)로 가져온 후, 해당 노드를 스택에서 제거(pop)합니다.
- 현재 노드의 오른쪽 자식이 존재한다면, 오른쪽 서브트리에서 중위 순회상 다음 노드(중위 계승자, inorder successor)들을 스택에 push합니다.
- 현재 노드의 값을 반환합니다.
2. hasNext() 메서드
- 스택이 비어 있지 않으면
true, 비어 있으면false를 반환합니다.
반복자가 생성될 때 루트 노드부터 왼쪽 자식을 따라가며 모든 노드를 스택에 미리 쌓아두면, next() 호출 시마다 항상 O(1)에 최솟값을 꺼낼 수 있습니다.
C++ 구현 예제
다음은 위 알고리즘을 C++로 구현한 전체 코드입니다.
#include <bits/stdc++.h>
using namespace std;
class TreeNode{
public:
int val;
TreeNode *left, *right;
TreeNode(int data){
val = data;
left = right = NULL;
}
};
void insert(TreeNode **root, int val){
queue<TreeNode*> q;
q.push(*root);
while(q.size()){
TreeNode *temp = q.front();
q.pop();
if(!temp->left){
if(val != NULL)
temp->left = new TreeNode(val);
else
temp->left = new TreeNode(0);
return;
} else {
q.push(temp->left);
}
if(!temp->right){
if(val != NULL)
temp->right = new TreeNode(val);
else
temp->right = new TreeNode(0);
return;
}else{
q.push(temp->right);
}
}
}
TreeNode *make_tree(vector<int> v){
TreeNode *root = new TreeNode(v[0]);
for(int i = 1; i<v.size(); i++){
insert(&root, v[i]);
}
return root;
}
class BSTIterator {
public:
stack <TreeNode*> st;
void fillStack(TreeNode* node){
while(node && node->val != 0){
st.push(node);
node=node->left;
}
}
BSTIterator(TreeNode* root) {
fillStack(root);
}
/** @return 다음으로 작은 숫자를 반환 */
int next() {
TreeNode* curr = st.top();
st.pop();
if(curr->right && curr->right->val != 0){
fillStack(curr->right);
}
return curr->val;
}
/** @return 다음으로 작은 숫자가 존재하는지 여부를 반환 */
bool hasNext() {
return !st.empty();
}
};
main(){
vector<int> v = {7,3,15,NULL,NULL,9,20};
TreeNode *root = make_tree(v);
BSTIterator ob(root);
cout << "Next: " << ob.next() << endl;
cout << "Next: " << ob.next() << endl;
cout << ob.hasNext() << endl;
cout << "Next: " << ob.next() << endl;
cout << ob.hasNext() << endl;
cout << "Next: " << ob.next() << endl;
cout << ob.hasNext() << endl;
cout << "Next: " << ob.next() << endl;
cout << ob.hasNext() << endl;
}입력
BSTIterator ob(root); ob.next() ob.next() ob.hasNext() ob.next() ob.hasNext() ob.next() ob.hasNext() ob.next() ob.hasNext()
출력
Next: 3 Next: 7 1 Next: 9 1 Next: 15 1 Next: 20 0
시간 및 공간 복잡도 분석
- hasNext(): 스택의 상태만 확인하므로 O(1)입니다.
- next(): 평균적으로 O(1)의 시간 복잡도를 가집니다. 각 노드는 반복자의 전체 생명주기 동안 정확히 한 번씩만 스택에 push되고 pop되기 때문입니다.
- 공간 복잡도: 트리의 높이에 비례하여 O(h)입니다. 균형 잡힌 BST의 경우 O(log n), 편향된 트리의 경우 최악 O(n)까지 증가할 수 있습니다.
이처럼 스택 기반의 지연 평가(lazy evaluation) 방식을 사용하면, 트리 전체를 미리 순회하지 않고도 필요할 때마다 다음 원소를 효율적으로 얻을 수 있습니다.