9. 이진 탐색 트리

 

• TL;DR
• 이진 탐색 트리(BST)는 왼쪽 < 루트 < 오른쪽 규칙을 따르는 이진 트리 기반의 탐색 자료구조
• 주요 연산은 탐색 / 삽입 / 삭제 / 개수 4가지이며, 삭제 연산이 가장 복잡함
• 순회 방법은 전위(루트→왼→오) / 중위(왼→루트→오) / 후위(왼→오→루트) 3가지
• 중위 순회를 하면 정렬된 순서(오름차순)로 데이터를 방문할 수 있음
• 탐색·삽입·삭제 평균 O(log n), 편향 트리(최악)에서는 O(n)으로 저하
• 실제 응용: 단어장 프로그램, 폴더 용량 계산 등

 

 

 

01  이진 탐색 트리(BST)란?

 

탐색(Search)은 일상에서도 매우 중요한 작업입니다. 사전에서 단어를 찾거나, 쇼핑몰에서 상품을 검색하는 것도 모두 탐색이죠. 컴퓨터에서 이 탐색 작업을 효율적으로 처리하기 위해 고안된 자료구조가 바로 이진 탐색 트리(BST, Binary Search Tree)입니다.

 

📖 이진 탐색 트리(BST) 정의
레코드의 집합에서 특정 레코드를 찾아내는 탐색에 특화된 이진 트리 기반의 자료구조.
배열과 선형 리스트의 단점을 보완하기 위해 연결리스트로 구성된 이진 트리를 사용하며, 원소의 삽입·삭제가 용이하다.

 

📌 탐색 관련 핵심 용어

 

용어	설명
레코드	자료를 체계적으로 관리하기 위해 구성한 일정한 단위 예) 학생 정보 1명분 (이름, 학번, 학과 등)
필드	레코드를 구성하는 하위 항목 예) 이름, 학번, 학과 각각이 필드
키(Key)	레코드를 구별하기 위한 고유한 값을 가진 필드 예) 학번처럼 중복이 없는 고유 식별자
파일	여러 레코드가 모여서 구성된 집합 예) 학생 전체 명부

 

📌 BST의 4가지 핵심 성질

 

번호	성질
①	모든 노드는 유일한 키를 가짐 (중복 없음)
②	왼쪽 서브 트리의 키들은 루트의 키보다 작음
③	오른쪽 서브 트리의 키들은 루트의 키보다 큼
④	왼쪽·오른쪽 서브 트리도 각각 이진 탐색 트리임 (재귀적 구조)

 

✓ 예시로 이해하기
루트가 18인 트리가 있다면:
· 왼쪽 서브 트리 = 18보다 작은 값들 (예: 7, 12, 15)
· 오른쪽 서브 트리 = 18보다 큰 값들 (예: 26, 22, 30)
이 규칙이 트리 전체에 재귀적으로 적용됩니다.

 

⚠️ BST의 한계
데이터 원소가 정렬되어 있어야 하며, 빈번한 삽입·삭제가 필요한 경우에는 부적합합니다.
삽입·삭제가 잦으면 트리가 한쪽으로 치우쳐 성능이 O(n)까지 저하될 수 있습니다.

 

 

 

02  BST의 4가지 연산

 

탐색 연산 Search

→

삽입 연산 Insert

→

삭제 연산 Delete

→

개수 연산 Count

 

🔍 탐색 연산 (Search)

 

탐색은 항상 루트 노드에서 시작하며, 찾는 키(key)값과 현재 노드의 키를 비교해가며 내려갑니다.

 

C 코드 — 노드 구조체 정의

#include <stdio.h>
#include <stdlib.h>

// BST 노드 구조체
typedef struct TreeNode {
    int key;                    // 키(데이터)
    struct TreeNode *left;    // 왼쪽 자식 포인터
    struct TreeNode *right;   // 오른쪽 자식 포인터
} TreeNode;

 

C 코드 — 재귀적 탐색 함수

TreeNode* search(TreeNode *root, int key) {
    if (root == NULL) return NULL;  // 탐색 실패

    if (key == root->key)        // 탐색 성공
        return root;
    else if (key < root->key)   // 왼쪽 서브 트리로 재귀 탐색
        return search(root->left, key);
    else                         // 오른쪽 서브 트리로 재귀 탐색
        return search(root->right, key);
}

 

📖 코드 포인트
· root == NULL : 찾는 키가 없는 경우(탐색 실패). 삽입 시에는 이 위치가 새 노드 자리가 됨
· 재귀 호출 : BST의 구조적 특성(서브 트리도 BST)을 활용해 같은 함수를 반복 적용
· 반환값 : 찾은 노드의 포인터를 반환. 없으면 NULL 반환

 

상황	동작
key == 루트의 키값	탐색 성공! 해당 노드가 찾는 노드
key < 루트의 키값	왼쪽 서브 트리로 이동하여 탐색 재시작
key > 루트의 키값	오른쪽 서브 트리로 이동하여 탐색 재시작
탐색 중 NULL(빈 노드) 도달	탐색 실패 — 해당 키는 트리에 없음

 

⏱️ BST 시간 복잡도 성능 비교

 

연산	평균 (균형 트리)	최악 (편향 트리)	최악이 되는 조건
탐색	O(log n)	O(n)	데이터가 오름/내림차순으로 삽입되어 트리가 한쪽으로 쏠릴 때
삽입	O(log n)	O(n)	편향 트리에서 삽입 위치를 찾기 위해 전체 노드를 순회해야 할 때
삭제	O(log n)	O(n)	편향 트리에서 후계자 탐색까지 전체 노드를 거쳐야 할 때

 

❌ 편향 트리(Skewed Tree)란?
예를 들어 1, 2, 3, 4, 5를 순서대로 삽입하면 모든 노드가 오른쪽으로만 연결됩니다.
이렇게 되면 트리가 사실상 연결 리스트와 동일해져서 BST의 장점인 O(log n) 성능을 전혀 살릴 수 없습니다.

이를 해결하기 위해 AVL 트리, 레드-블랙 트리 같은 자가 균형 BST가 고안되었습니다.

 

 

➕ 삽입 연산 (Insert)

 

✓ 삽입 연산의 핵심 원칙
BST에서는 같은 키 값을 갖는 노드가 없어야 합니다.
탐색에 실패한 위치 = 새로운 노드를 삽입할 위치
따라서 삽입 전에 반드시 탐색을 먼저 수행해야 합니다.

 

① 탐색 수행 삽입할 키로 탐색 시작

→

② 실패 위치 확인 탐색이 실패한 NULL 위치 확인

→

③ 노드 삽입 해당 위치에 새 노드 추가

 

슈도코드 (Pseudocode) — 삽입 연산 전체 흐름

insert (root, n)

if KEY(n) = KEY(root)                  // 중복 키 — 삽입 불가
    then return;

else if KEY(n) < KEY(root)          // 삽입 키가 더 작으면 왼쪽
    if LEFT(root) = NULL
        then LEFT(root) ← n;           // 왼쪽이 비었으면 바로 삽입
        else insert(LEFT(root), n);   // 아니면 왼쪽 서브트리로 재귀

else                                    // 삽입 키가 더 크면 오른쪽
    if RIGHT(root) = NULL
        then RIGHT(root) ← n;        // 오른쪽이 비었으면 바로 삽입
        else insert(RIGHT(root), n); // 아니면 오른쪽 서브트리로 재귀

 

C 코드 — 재귀적 삽입 함수

TreeNode* insert(TreeNode *root, int key) {
    if (root == NULL) {                       // 빈 자리 발견 → 새 노드 생성
        TreeNode *n = (TreeNode*)malloc(sizeof(TreeNode));
        n->key = key;
        n->left = n->right = NULL;
        return n;
    }
    if (key == root->key)                    // 중복 키 → 그냥 반환
        return root;
    else if (key < root->key)               // 왼쪽 서브트리로 재귀
        root->left = insert(root->left, key);
    else                                      // 오른쪽 서브트리로 재귀
        root->right = insert(root->right, key);
    return root;
}

 

📖 코드 포인트
· root == NULL 도달 : 탐색 실패 위치 = 새 노드를 삽입할 자리
· 중복 키 처리 : KEY(n) = KEY(root)이면 아무 작업 없이 바로 return (BST는 중복 불허)
· 재귀 호출 : 삽입할 키와 현재 노드를 비교해 왼쪽/오른쪽으로 내려가며 빈 자리를 탐색

 

 

🗑️ 삭제 연산 (Delete) — 가장 복잡한 연산

 

노드 삭제는 BST에서 가장 복잡한 연산입니다. 삭제 후에도 BST의 성질(왼쪽 < 루트 < 오른쪽)을 반드시 유지해야 하기 때문입니다. 삭제할 노드의 자식 수에 따라 처리 방법이 달라집니다.

경우	처리 방법
Case 1 단말 노드(자식 없음) 삭제	가장 단순한 경우. 노드를 그냥 삭제하면 됨. 단, 부모 노드의 링크 필드(자식을 가리키는 포인터)를 NULL로 변경해야 함.
Case 2 자식이 하나인 노드 삭제	삭제할 노드를 제거하고, 유일한 자식을 부모 노드에 직접 연결. 삭제 노드가 부모의 왼쪽/오른쪽 자식인지, 자식이 왼쪽/오른쪽인지 모두 고려해야 함.
Case 3 자식이 둘인 노드 삭제	중위 후속자(Inorder Successor)를 찾아서 삭제 위치에 복사한 뒤, 후계자 노드를 삭제. 후계자 = 오른쪽 서브 트리의 최솟값 (또는 왼쪽 서브 트리의 최댓값)

 

📖 중위 후속자(Inorder Successor)란?
중위 순회(왼→루트→오) 기준으로 삭제 노드 바로 다음에 방문될 노드를 의미합니다.
이 값은 삭제 노드보다 크면서 가장 작은 값이므로, 그 자리에 들어와도 BST 성질이 유지됩니다.

· 중위 후속자 위치 : 오른쪽 서브 트리에서 가장 왼쪽(= 가장 작은) 노드
· 중위 전임자(Inorder Predecessor) : 왼쪽 서브 트리에서 가장 오른쪽(= 가장 큰) 노드

예) 노드 18 삭제 시
· 중위 후속자 = 오른쪽 서브 트리의 최솟값 → 22
· 중위 전임자 = 왼쪽 서브 트리의 최댓값 → 12
→ 22 또는 12 중 하나를 18 위치에 복사한 뒤, 원래 22(또는 12)를 삭제

 

 

🔢 개수 연산 (Count)

 

🔢 개수 연산 방법
전체 노드 수 = 왼쪽 서브 트리 노드 수 + 오른쪽 서브 트리 노드 수 + 1(루트)

모든 노드를 순회하면서 count 변수를 증가시키는 방식으로도 구현 가능.
이진 트리의 전체 노드 개수를 세기 위해서는 모든 노드의 순회가 필요합니다.

 

슈도코드 (Pseudocode) — 개수 연산

count_node(x)

if x = NULL                               // 빈 노드 → 0 반환
    then return 0;
    else return 1 + count_node(x.left)  // 루트 1 + 왼쪽 + 오른쪽
                    + count_node(x.right);

 

C 코드 — 재귀적 노드 개수 계산 함수

int count_node(TreeNode *x) {
    if (x == NULL)                                // 빈 노드 → 0 반환
        return 0;
    else
        return 1 + count_node(x->left)  // 현재 노드(1) + 왼쪽 서브트리
                 + count_node(x->right); // + 오른쪽 서브트리
}

 

📖 코드 포인트
· x == NULL : 트리가 없거나 리프 노드의 자식에 도달한 경우 — 0을 반환해 합산을 종료
· return 1 + ... : 현재 노드 자신(1) + 왼쪽 서브트리 개수 + 오른쪽 서브트리 개수
· 재귀 구조 : 모든 노드를 빠짐없이 방문하는 후위 순회와 동일한 흐름으로 동작

 

 

 

03  BST의 3가지 순회 방법

 

순회(Traversal)란 트리에 속하는 모든 노드를 중복 없이 한 번씩 방문하여 데이터를 처리하는 작업입니다. 선형 자료구조(배열, 리스트 등)는 순회 방법이 하나뿐이지만, 트리는 비선형 자료구조이므로 루트와 좌·우 서브 트리를 어떤 순서로 방문하느냐에 따라 3가지 방법으로 나뉩니다.

 

순회 종류	방문 순서	특징
전위 순회 (Preorder)	루트 → 왼쪽 → 오른쪽	루트를 가장 먼저 방문. 트리 복사 등에 활용
중위 순회 (Inorder)	왼쪽 → 루트 → 오른쪽	정렬된 순서(오름차순)로 방문. BST에서 가장 유용한 순회
후위 순회 (Postorder)	왼쪽 → 오른쪽 → 루트	루트를 가장 마지막 방문. 폴더 용량 계산 등에 활용

 

✓ 중위 순회가 정렬 순서인 이유
BST의 성질상 왼쪽 < 루트 < 오른쪽이므로,
왼쪽 서브 트리를 모두 방문 → 루트 → 오른쪽 서브 트리 순으로 가면
자연스럽게 작은 값부터 큰 값 순서(사전식/오름차순)로 방문하게 됩니다.

 

📖 이진 트리 순회의 재귀적 특성
이진 트리는 전체 트리와 서브 트리의 구조가 동일합니다.
따라서 전체 트리 순회에 사용한 알고리즘을 서브 트리에도 그대로 적용할 수 있습니다. (재귀 구조)

 

 

 

04  실제 응용 사례

 

📚 응용 1 — 나의 단어장 이진 탐색 트리로 단어장 프로그램 구현 가능. 각 노드의 레코드 = "단어" + "의미" 두 필드로 구성. · 입력(i) : 단어·의미 입력하여 노드 추가 · 삭제(d) : 단어 입력으로 해당 노드 제거 · 단어 탐색(w) : 단어 → 의미 출력 · 의미 탐색(m) : 의미 → 단어 출력 · 사전 출력(p) : 중위 순회로 알파벳 순 출력 · 종료(q) : 프로그램 종료

💾 응용 2 — 폴더 용량 계산 이진 탐색 트리 순회를 폴더 용량 계산에 응용. 단, 이진 트리이므로 하나의 폴더 안에 하위 폴더는 최대 2개까지만 가능. · 서브 폴더의 용량을 모두 계산한 후 루트 폴더 계산 · 후위 순회 방식 사용 (자식 → 자식 → 부모 순으로 계산) · 하위 폴더 용량을 먼저 계산해 반환하는 구조

 

✓ 폴더 용량 계산에 후위 순회를 쓰는 이유
부모 폴더의 용량을 알려면 자식 폴더의 용량을 먼저 알아야 합니다.
후위 순회(왼→오→루트)는 자식을 먼저 처리하고 부모를 마지막에 처리하는 구조이므로,
하위 폴더 용량을 합산하여 상위 폴더로 반환하는 계산에 딱 맞습니다.

 

 

📌 핵심 정리

· BST 정의 : 왼쪽 서브 트리 키 < 루트 키 < 오른쪽 서브 트리 키를 만족하는 이진 트리
· 시간 복잡도 : 평균 O(log n) / 편향 트리(최악) O(n) — 균형 유지가 핵심
· 탐색 연산 : 루트에서 시작, 키 비교로 좌/우 이동, 재귀 구조로 구현
· 삽입 연산 : 탐색 실패 위치가 삽입 위치, 반드시 탐색 먼저 수행
· 삭제 연산 : 단말 노드 / 자식 1개 / 자식 2개 세 경우 구분 처리
· 중위 후속자 : 오른쪽 서브 트리의 최솟값 — Case 3 삭제 시 후계자로 사용
· 전위 순회 : 루트 → 왼쪽 → 오른쪽
· 중위 순회 : 왼쪽 → 루트 → 오른쪽 (결과: 오름차순 정렬)
· 후위 순회 : 왼쪽 → 오른쪽 → 루트 (폴더 용량 계산에 활용)

 

 

태그 : 이진탐색트리란BST 자료구조이진트리 순회 종류전위순회 중위순회 후위순회 차이BST 삭제 연산이진탐색트리 탐색방법C언어 자료구조중위순회 정렬순서후계자 노드란BST 응용 사례