검색하고 해제하기
노드를 찾고 메모리를 반환해 보세요.
검색하고 해제하기은(는) CoddyKit의 무료 C Academy 강의입니다. 이것은 4개 중 4번째 강의입니다. 아래에서 전체 강의를 무료로 읽을 수 있으며, 내장 코드 에디터와 24/7 AI 튜터와 함께 브라우저에서 직접 실습할 수 있습니다. 이 강의는 C Academy 학습 경로의 일부이며, 진행 상황이 웹과 CoddyKit 앱에 동기화됩니다. C Academy 강의에는 총 4개의 강의가 포함되어 있습니다.
BST 검색
검색은 정렬 규칙을 활용합니다. 각 노드에서 대상 값을 노드의 값과 비교하고, 하나의 하위 트리로만 이동합니다.
각 단계에서 남은 노드의 절반을 버리므로 검색 비용은 트리의 크기가 아니라 높이에 비례합니다.
재귀 검색
재귀 검색에는 두 가지 기본 사례가 있습니다. 빈 하위 트리는 찾지 못했다는 뜻이고, 일치하는 값은 찾았다는 뜻입니다.
그 외에는 비교 결과에 따라 왼쪽 또는 오른쪽으로 재귀 호출을 합니다.
Node *search(Node *root, int target) {
if (root == NULL || root->value == target)
return root;
if (target < root->value)
return search(root->left, target);
return search(root->right, target);
}반복 검색
검색은 재귀의 오버헤드를 피하는 간단한 반복문으로도 구현할 수 있습니다.
대상을 찾거나 NULL에서 끝에 도달할 때까지 트리를 따라 포인터를 아래로 이동합니다.
Node *search_iter(Node *root, int target) {
while (root != NULL) {
if (target == root->value) return root;
root = (target < root->value)
? root->left : root->right;
}
return NULL; /* not found */
}검색 실행
이 프로그램은 BST를 만들고 존재하는 값과 존재하지 않는 값을 검색하여 각각 찾았는지 출력합니다.
NULL이 아닌 반환값은 찾았다는 뜻이고, NULL은 해당 값이 트리에 없다는 뜻입니다.
#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;
}
Node *search(Node *r,int t){
if(!r||r->value==t) return r;
return t<r->value ? search(r->left,t) : search(r->right,t);
}
int main(void){
Node *root=NULL;
int d[]={10,5,15,3,7};
for(int i=0;i<5;i++) root=insert(root,d[i]);
printf("7:%s 99:%s\n",
search(root,7)?"found":"no",
search(root,99)?"found":"no");
return 0;
}최솟값 찾기
BST에서 가장 작은 값은 가장 왼쪽에 있는 노드입니다. left가 NULL이 될 때까지 계속 따라가면 됩니다.
반대로 최댓값은 가장 오른쪽에 있는 노드입니다. 이러한 도우미 함수는 삭제와 범위 질의에 중요합니다.
Node *find_min(Node *root) {
if (root == NULL) return NULL;
while (root->left != NULL)
root = root->left;
return root;
}해제가 중요한 이유
모든 노드는 malloc으로 할당되므로 모든 노드는 free로 반환해야 합니다. 해제를 잊으면 메모리 누수가 발생합니다.
하지만 노드를 해제한 다음 그 노드의 자식 포인터를 읽을 수는 없으므로 해제하는 순서가 매우 중요합니다.
후위 순서로 해제하기
트리를 안전하게 해제하는 방법은 후위 순서를 사용하는 것입니다. 먼저 두 자식을 모두 해제한 다음 노드 자체를 해제합니다.
이렇게 하면 해당 노드의 메모리가 해제되기 전에 노드의 left와 right 포인터를 읽을 수 있습니다.
void free_tree(Node *root) {
if (root == NULL) return;
free_tree(root->left);
free_tree(root->right);
free(root);
}위험한 잘못된 순서
자식으로 재귀 호출하기 전에 노드를 해제하면 정의되지 않은 동작이 발생합니다. 하위 트리에 접근하려고 이미 해제된 메모리를 역참조하게 되기 때문입니다.
이는 대표적인 해제 후 사용 버그입니다. 항상 자식을 먼저 해제하십시오.
/* WRONG: use-after-free */
void bad_free(Node *root) {
if (!root) return;
free(root); /* freed here */
bad_free(root->left); /* reads freed memory! */
bad_free(root->right);
}댕글링 포인터 피하기
free_tree가 반환된 뒤에도 원래 루트 포인터에는 이전 주소가 남아 있지만 메모리는 사라집니다.
호출한 쪽에서 포인터를 다시 NULL로 설정하면 댕글링 포인터를 실수로 재사용하는 일을 막을 수 있습니다.
free_tree(root);
root = NULL; /* avoid a dangling pointer */해제된 노드 세기
후위 순회를 진행하면서 노드를 센 다음 각각 해제하면 해제가 제대로 작동하는지 확인할 수 있습니다.
이 프로그램은 트리를 만들고 해제한 뒤 몇 개의 노드가 해제되었는지 보고합니다.
#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 free_count(Node *r){
if(!r) return 0;
int c = free_count(r->left) + free_count(r->right);
free(r);
return c + 1;
}
int main(void){
Node *root=NULL;
int d[]={10,5,15,3,7};
for(int i=0;i<5;i++) root=insert(root,d[i]);
printf("freed=%d\n", free_count(root));
root = NULL;
return 0;
}검색과 해제를 함께 수행하기
완전한 수명 주기는 트리를 만들고 검색한 다음 해제하는 과정입니다. 세 작업을 모두 수행하면 프로그램의 정확성을 유지하고 메모리 누수를 막을 수 있습니다.
Valgrind 같은 도구를 사용하면 모든 malloc 호출에 free 호출이 대응하는지 확인할 수 있습니다.
/* lifecycle
* 1. insert values (allocate)
* 2. search as needed (read-only)
* 3. free_tree(root) (deallocate)
* 4. root = NULL (avoid dangling)
*/빠른 확인
안전한 메모리 해제를 생각해 보십시오.
복습
BST 검색은 단계마다 값을 비교하고 하나의 하위 트리로 내려가므로 높이에 비례하는 시간이 걸립니다. 최솟값은 가장 왼쪽 노드이고 최댓값은 가장 오른쪽 노드입니다.
트리는 후위 순서로 해제하여 자식이 부모보다 먼저 해제되도록 한 다음, 댕글링 포인터를 피하기 위해 루트를 NULL로 설정하십시오.
AI 튜터와 함께 C을(를) 배우세요 — 무료
브라우저에서 실제 코드를 작성하고 실행하며, 24/7 AI 튜터로부터 즉각적인 도움을 받고, 웹이나 앱에서 중단한 부분부터 계속 학습하세요.
- 코스
- 39
- 레슨
- 144
자주 묻는 질문
“검색하고 해제하기” 강의는 무료인가요?
네 — “검색하고 해제하기” 전체 내용을 이 웹사이트에서 무료로 읽을 수 있습니다. 인터랙티브하게 실습하려면(내장 코드 에디터와 24/7 AI 튜터), CoddyKit PRO로 업그레이드하면 C Academy 강의 전체를 잠금 해제할 수 있습니다. C Academy 강의에는 총 4개의 강의가 포함되어 있습니다.
“검색하고 해제하기”에서 뭘 배우나요?
노드를 찾고 메모리를 반환해 보세요. 브라우저에서 직접 실행하는 실습 코드로 C Academy을(를) 배우며, 24/7 AI 튜터가 강의를 진행하면서 질문에 답변해줍니다.
C Academy을(를) 시작하는 데 경험이 필요한가요?
사전 경험은 필요하지 않습니다. CoddyKit의 C Academy은(는) 초급자부터 고급 학습자까지를 위해 구성되어 있으므로, 여기서 시작하거나 처음부터 시작할 수 있으며 자신의 속도대로 진행할 수 있습니다. 이것은 4개 중 4번째 강의입니다.
“검색하고 해제하기” 강의는 얼마나 걸리나요?
대부분의 CoddyKit 강의는 약 5~10분이 소요됩니다. 각 강의는 간결하고 인터랙티브하여 꾸준한 진행이 가능하며, 웹과 앱에서 중단한 부분부터 바로 시작할 수 있습니다.
이 C Academy 강의에서 코드를 작성하고 실행할 수 있나요?
네. 모든 C Academy 강의에는 내장 코드 에디터가 포함되어 있으므로, 브라우저에서 바로 실제 코드를 작성하고 실행한 후 즉시 AI 피드백을 받을 수 있습니다 — 로컬 설정이 필요 없습니다.