이진 탐색 트리(Binary Search Tree)가 하나 있다고 가정해 봅시다. 우리는 단 하나의 메서드만 작성해야 하며, 이 메서드는 매개변수로 전달된 값을 트리에 삽입하는 역할을 합니다. 중요한 점은 삽입 연산이 끝난 후에도 트리가 여전히 BST의 성질을 유지해야 한다는 것입니다.
예를 들어 다음과 같은 트리가 있다고 합시다.
여기에 5를 삽입하면 트리는 아래와 같이 변합니다.
접근 방법
이 문제는 다음 단계를 따라 해결할 수 있습니다.
- 삽입 메서드는 재귀적으로 동작하며, insert()라는 이름으로 값 v를 인자로 받습니다.
- 루트가 null이라면 주어진 값 v로 새 노드를 생성하고, 그 노드를 루트로 만듭니다.
- 루트의 값이 v보다 크다면 왼쪽 서브트리에 삽입합니다.
- 루트의 left := insert(루트의 left, v)
- 그렇지 않다면 오른쪽 서브트리에 삽입합니다. 즉, 루트의 right := insert(루트의 right, v)
- 마지막으로 루트를 반환합니다.
예제 (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;
}
void tree_level_trav(TreeNode*root){
if (root == NULL) return;
cout << "[";
queue<TreeNode *> q;
TreeNode *curr;
q.push(root);
q.push(NULL);
while (q.size() > 1) {
curr = q.front();
q.pop();
if (curr == NULL){
q.push(NULL);
}
else {
if(curr->left)
q.push(curr->left);
if(curr->right)
q.push(curr->right);
if(curr->val == 0 || curr == NULL){
cout << "null" << ", ";
}
else{
cout << curr->val << ", ";
}
}
}
cout << "]"<<endl;
}
class Solution {
public:
TreeNode* insertIntoBST(TreeNode* root, int val) {
if(!root)return new TreeNode(val);
if(root->val > val){
root->left = insertIntoBST(root->left, val);
}
else root->right = insertIntoBST(root->right, val);
return root;
}
};
main(){
Solution ob;
vector<int> v = {4,2,7,1,3};
TreeNode *root = make_tree(v);
tree_level_trav(ob.insertIntoBST(root, 5));
}
동작 원리
Solution 클래스의 insertIntoBST() 메서드가 핵심 로직입니다. 루트가 null인 경우 새 노드를 생성해 반환하고, 그렇지 않으면 삽입할 값과 현재 노드의 값을 비교합니다. 값이 더 작으면 왼쪽 서브트리로, 크거나 같으면 오른쪽 서브트리로 재귀 호출을 진행하며, 빈 자리를 찾으면 그 위치에 새 노드를 연결합니다. 이 과정 덕분에 삽입 후에도 트리는 항상 BST의 성질을 유지하게 됩니다.
이 알고리즘의 시간 복잡도는 트리의 높이 h에 비례하여 O(h)입니다. 균형 잡힌 트리라면 O(log n), 최악의 경우(편향된 트리)에는 O(n)이 됩니다.
입력
[4,2,7,1,3] 5
출력
[4,2,7,1,3,5]