BST에 삽입하기
이진 탐색 트리를 만들어 보세요.
BST에 삽입하기은(는) CoddyKit의 무료 C Academy 강의입니다. 이것은 4개 중 2번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 C Academy 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. C Academy 강의에는 총 4개의 강의가 포함되어 있습니다.
BST 정렬 규칙
이진 검색 트리(BST)는 한 가지 규칙이 추가된 이진 트리입니다. 모든 노드에서 왼쪽 하위 트리의 모든 값은 더 작고 오른쪽 하위 트리의 모든 값은 더 큽니다.
이 정렬 규칙 덕분에 트리의 높이에 비례하는 시간 안에 검색, 삽입, 삭제를 수행할 수 있습니다.
값이 들어갈 위치
삽입할 때는 루트에서 시작해 값을 비교합니다. 새 값이 더 작으면 왼쪽으로, 더 크면 오른쪽으로 이동합니다.
빈 위치(NULL)에 도달할 때까지 반복하며, 그 위치가 바로 새 노드가 들어갈 자리입니다.
/* insert 7 into:
* 10
* / \
* 5 15
* 7 < 10 -> left; 7 > 5 -> right of 5
*/create_node 도우미
삽입은 새 리프 노드를 만들므로, 노드를 할당하고 초기화하는 생성자를 재사용합니다.
새로 삽입된 노드는 항상 리프이므로 두 자식은 NULL로 시작합니다.
Node *create_node(int value) {
Node *n = malloc(sizeof(Node));
if (!n) return NULL;
n->value = value;
n->left = n->right = NULL;
return n;
}재귀적 삽입
가장 깔끔한 삽입 방법은 재귀적으로 수행하고, 경우에 따라 새로 만들어진 하위 트리의 루트를 반환하는 것입니다.
하위 트리가 비어 있으면 새 노드를 반환합니다. 그렇지 않으면 왼쪽 또는 오른쪽으로 재귀 호출하고 그 결과를 다시 연결한 다음, 바뀌지 않은 루트를 반환합니다.
Node *insert(Node *root, int value) {
if (root == NULL)
return create_node(value);
if (value < root->value)
root->left = insert(root->left, value);
else if (value > root->value)
root->right = insert(root->right, value);
return root; /* equal: ignore duplicate */
}루트를 반환하는 이유
하위 트리의 루트를 반환하면 부모가 한 줄로 연결을 다시 설정할 수 있습니다. root->left = insert(root->left, v)와 같습니다.
하위 트리가 비어 있었다면 반환된 새 노드가 자식이 됩니다. 비어 있지 않았다면 같은 루트가 반환되므로 연결은 바뀌지 않습니다.
/* The assignment does double duty:
* - empty case: stores the new node
* - non-empty: stores the same pointer back (no-op)
*/
root->left = insert(root->left, value);중복 처리
실제 BST는 같은 값에 어떻게 대응할지 결정해야 합니다. 일반적인 선택은 중복을 무시하는 것입니다. insert가 같은 경우에 대한 분기를 두지 않는 방식으로 이를 구현합니다.
노드마다 개수를 저장하거나 중복 값을 항상 한쪽으로 보내는 방법도 있습니다.
if (value < root->value)
root->left = insert(root->left, value);
else if (value > root->value)
root->right = insert(root->right, value);
/* value == root->value -> do nothing */BST 만들기
값의 순서를 차례로 삽입하면 삽입 순서에 따라 형태가 달라지는 트리가 만들어집니다.
여기서는 여러 숫자를 삽입하고 루트의 바로 아래 자식들을 출력하여 정렬 규칙이 지켜지는지 확인합니다.
#include <stdio.h>
#include <stdlib.h>
typedef struct Node { int value; struct Node *left, *right; } Node;
Node *create_node(int v){ Node *n=malloc(sizeof(Node)); n->value=v; n->left=n->right=NULL; return n; }
Node *insert(Node *r,int v){
if(!r) return create_node(v);
if(v<r->value) r->left=insert(r->left,v);
else if(v>r->value) r->right=insert(r->right,v);
return r;
}
int main(void){
Node *root = NULL;
int data[] = {10,5,15,3,7};
for(int i=0;i<5;i++) root=insert(root,data[i]);
printf("root=%d left=%d right=%d\n", root->value, root->left->value, root->right->value);
return 0;
}반복문을 이용한 삽입
재귀 없이 삽입할 수도 있습니다. 포인터로 아래쪽을 따라가면서 부모를 기억하고, 빈 위치를 찾을 때까지 내려갑니다.
그런 다음 새 노드를 부모의 올바른 쪽에 연결합니다.
void insert_iter(Node **rootp, int value) {
Node *cur = *rootp, *parent = NULL;
while (cur) {
parent = cur;
cur = (value < cur->value) ? cur->left : cur->right;
}
Node *n = create_node(value);
if (!parent) *rootp = n;
else if (value < parent->value) parent->left = n;
else parent->right = n;
}삽입 순서가 트리 형태를 결정합니다
1,2,3,4,5를 정렬된 순서로 삽입하면 연결 리스트처럼 보이는 퇴화 트리가 만들어지고, 높이는 개수와 같아집니다.
균형 잡힌 순서로 삽입하면 높이를 log(n)에 가깝게 유지할 수 있습니다. 균형은 검색 속도에 직접적인 영향을 줍니다.
/* sorted insert 1..5 ->
* 1
* \
* 2
* \
* 3 (height = 4, like a list)
*/삽입 비용
각 삽입은 루트에서 리프까지 하나의 경로를 따라가므로 트리의 높이에 비례하는 작업을 수행합니다.
균형 잡힌 트리에서는 대략 log(n)번 비교하고, 퇴화 트리에서는 n번까지 비교할 수 있습니다. 이것이 자체 균형 트리가 존재하는 이유입니다.
전체 삽입 예제
이 프로그램은 값을 삽입한 다음 노드 수를 세어 서로 다른 값 다섯 개가 저장되고 중복 값 하나가 무시되었는지 확인합니다.
중복된 10은 개수를 늘리지 않습니다. insert가 같은 값을 버리기 때문입니다.
#include <stdio.h>
#include <stdlib.h>
typedef struct Node { int value; struct Node *left, *right; } Node;
Node *cn(int v){ Node *n=malloc(sizeof(Node)); n->value=v; n->left=n->right=NULL; return n; }
Node *insert(Node *r,int v){
if(!r) return cn(v);
if(v<r->value) r->left=insert(r->left,v);
else if(v>r->value) r->right=insert(r->right,v);
return r;
}
int count(Node *r){ return r? 1+count(r->left)+count(r->right):0; }
int main(void){
Node *root=NULL;
int d[]={10,5,15,10,20};
for(int i=0;i<5;i++) root=insert(root,d[i]);
printf("count=%d\n", count(root));
return 0;
}빠른 확인
삽입 동작을 생각해 보십시오.
복습
BST 삽입은 새 값을 각 노드와 비교하면서, 더 작으면 왼쪽으로 더 크면 오른쪽으로 이동하다가 빈 위치를 찾을 때까지 계속합니다.
재귀 형태는 하위 트리의 루트를 반환하므로 부모가 연결을 깔끔하게 다시 연결할 수 있습니다. 삽입 비용은 트리 높이에 비례하므로 삽입 순서가 중요합니다.
자주 묻는 질문
“BST에 삽입하기” 강의는 무료인가요?
네 — “BST에 삽입하기” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 C Academy 강의 전체를 잠금 해제할 수 있습니다. C Academy 강의에는 총 4개의 강의가 포함되어 있습니다.
“BST에 삽입하기”에서 뭘 배우나요?
이진 탐색 트리를 만들어 보세요. 브라우저에서 직접 실행하는 실습 코드로 C Academy을(를) 배우며, 24/7 AI 튜터가 강의를 진행하면서 질문에 답변해줍니다.
C Academy을(를) 시작하는 데 경험이 필요한가요?
사전 경험은 필요하지 않습니다. CoddyKit의 C Academy은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 2번째 강의입니다.
“BST에 삽입하기” 강의는 얼마나 걸리나요?
대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.
이 C Academy 강의에서 코드를 작성하고 실행할 수 있나요?
네. 모든 C Academy 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.