Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 구현하는 이진 탐색 트리(BST) 삽입·삭제·탐색 프로그램

이진 탐색 트리(Binary Search Tree, BST)는 정렬된 상태를 유지하는 이진 트리로, 모든 노드가 다음과 같은 성질을 만족해야 합니다.

  • 노드의 오른쪽 서브트리에는 부모 노드의 키보다 큰 키가 위치합니다.
  • 노드의 왼쪽 서브트리에는 부모 노드의 키보다 작은 키가 위치합니다.
  • 모든 키 값은 중복 없이 고유합니다.
  • 각 노드는 최대 두 개의 자식 노드만 가질 수 있습니다.

이러한 구조 덕분에 BST는 탐색, 삽입, 삭제 연산을 평균적으로 O(log n)의 시간 복잡도로 빠르게 처리할 수 있습니다.

클래스 설계 개요

이 예제에서 구현하는 BST 클래스는 다음과 같은 주요 기능을 제공합니다.

  • search() : 트리에서 특정 값을 찾고, 해당 값이 위치한 깊이(depth)를 출력합니다. 루트부터 시작해 값의 크기를 비교하며 왼쪽 또는 오른쪽 자식으로 이동합니다.
  • insert() : 새로운 값을 트리에 삽입합니다. 트리가 비어 있으면 루트로 삽입하고, 그렇지 않으면 값의 크기를 비교해 왼쪽 또는 오른쪽 자식으로 재귀적으로 내려가 적절한 위치에 추가합니다.
  • del() : 트리에서 특정 값을 삭제합니다. 삭제 대상 노드의 자식 상태에 따라 네 가지 경우(case)로 나누어 처리합니다.
    • casea() : 왼쪽·오른쪽 자식이 모두 없는 리프(leaf) 노드인 경우
    • caseb() : 자식이 하나만 있는 경우(왼쪽만 존재하거나 오른쪽만 존재)
    • casec() : 자식이 둘 다 있는 경우 — 오른쪽 서브트리에서 가장 작은 값(중위 후속자, inorder successor)을 찾아 대체합니다.
  • inorder() : 왼쪽 → 루트 → 오른쪽 순서로 순회합니다(오름차순 출력).
  • preorder() : 루트 → 왼쪽 → 오른쪽 순서로 순회합니다.
  • postorder() : 왼쪽 → 오른쪽 → 루트 순서로 순회합니다.
  • show() : 트리의 구조를 들여쓰기 형태로 화면에 출력합니다.

전체 예제 코드

#include <iostream>
#include <cstdlib>
using namespace std;

struct nod // 노드 선언
{
    int info;
    struct nod *l;
    struct nod *r;
} *r;

class BST
{
public: // 함수 선언
    void search(nod *, int);
    void find(int, nod **, nod **);
    void insert(nod *, nod *);
    void del(int);
    void casea(nod *, nod *);
    void caseb(nod *, nod *);
    void casec(nod *, nod *);
    void preorder(nod *);
    void inorder(nod *);
    void postorder(nod *);
    void show(nod *, int);
    BST()
    {
        r = NULL;
    }
};

// 항목의 위치를 찾는 함수 (부모와 위치를 함께 반환)
void BST::find(int i, nod **par, nod **loc)
{
    nod *ptr, *ptrsave;
    if (r == NULL)
    {
        *loc = NULL;
        *par = NULL;
        return;
    }
    if (i == r->info)
    {
        *loc = r;
        *par = NULL;
        return;
    }
    if (i < r->info)
        ptr = r->l;
    else
        ptr = r->r;
    ptrsave = r;
    while (ptr != NULL)
    {
        if (i == ptr->info)
        {
            *loc = ptr;
            *par = ptrsave;
            return;
        }
        ptrsave = ptr;
        if (i < ptr->info)
            ptr = ptr->l;
        else
            ptr = ptr->r;
    }
    *loc = NULL;
    *par = ptrsave;
}

// 탐색 함수: 깊이 정보와 함께 결과 출력
void BST::search(nod *root, int data)
{
    int depth = 0;
    nod *temp = root;
    while (temp != NULL)
    {
        depth++;
        if (temp->info == data)
        {
            cout << "\n데이터를 깊이 " << depth << "에서 찾았습니다" << endl;
            return;
        }
        else if (temp->info > data)
            temp = temp->l;
        else
            temp = temp->r;
    }
    cout << "\n데이터를 찾을 수 없습니다" << endl;
    return;
}

// 삽입 함수
void BST::insert(nod *tree, nod *newnode)
{
    if (r == NULL)
    {
        r = new nod;
        r->info = newnode->info;
        r->l = NULL;
        r->r = NULL;
        cout << "루트 노드가 추가되었습니다" << endl;
        return;
    }
    if (tree->info == newnode->info)
    {
        cout << "이미 트리에 존재하는 원소입니다" << endl;
        return;
    }
    if (tree->info > newnode->info)
    {
        if (tree->l != NULL)
        {
            insert(tree->l, newnode);
        }
        else
        {
            tree->l = newnode;
            (tree->l)->l = NULL;
            (tree->l)->r = NULL;
            cout << "왼쪽에 노드가 추가되었습니다" << endl;
            return;
        }
    }
    else
    {
        if (tree->r != NULL)
        {
            insert(tree->r, newnode);
        }
        else
        {
            tree->r = newnode;
            (tree->r)->l = NULL;
            (tree->r)->r = NULL;
            cout << "오른쪽에 노드가 추가되었습니다" << endl;
            return;
        }
    }
}

// 삭제 함수
void BST::del(int i)
{
    nod *par, *loc;
    if (r == NULL)
    {
        cout << "트리가 비어 있습니다" << endl;
        return;
    }
    find(i, &par, &loc);
    if (loc == NULL)
    {
        cout << "트리에 해당 항목이 없습니다" << endl;
        return;
    }
    if (loc->l == NULL && loc->r == NULL)
    {
        casea(par, loc);
        cout << "항목이 삭제되었습니다" << endl;
    }
    if (loc->l != NULL && loc->r == NULL)
    {
        caseb(par, loc);
        cout << "항목이 삭제되었습니다" << endl;
    }
    if (loc->l == NULL && loc->r != NULL)
    {
        caseb(par, loc);
        cout << "항목이 삭제되었습니다" << endl;
    }
    if (loc->l != NULL && loc->r != NULL)
    {
        casec(par, loc);
        cout << "항목이 삭제되었습니다" << endl;
    }
    free(loc);
}

// casea: 자식이 없는 노드 삭제
void BST::casea(nod *par, nod *loc)
{
    if (par == NULL)
    {
        r = NULL;
    }
    else
    {
        if (loc == par->l)
            par->l = NULL;
        else
            par->r = NULL;
    }
}

// caseb: 자식이 하나인 노드 삭제
void BST::caseb(nod *par, nod *loc)
{
    nod *child;
    if (loc->l != NULL)
        child = loc->l;
    else
        child = loc->r;
    if (par == NULL)
    {
        r = child;
    }
    else
    {
        if (loc == par->l)
            par->l = child;
        else
            par->r = child;
    }
}

// casec: 자식이 둘인 노드 삭제 (중위 후속자로 대체)
void BST::casec(nod *par, nod *loc)
{
    nod *ptr, *ptrsave, *suc, *parsuc;
    ptrsave = loc;
    ptr = loc->r;
    while (ptr->l != NULL)
    {
        ptrsave = ptr;
        ptr = ptr->l;
    }
    suc = ptr;
    parsuc = ptrsave;
    if (suc->l == NULL && suc->r == NULL)
        casea(parsuc, suc);
    else
        caseb(parsuc, suc);
    if (par == NULL)
    {
        r = suc;
    }
    else
    {
        if (loc == par->l)
            par->l = suc;
        else
            par->r = suc;
    }
    suc->l = loc->l;
    suc->r = loc->r;
}

// 전위 순회 (루트 - 왼쪽 - 오른쪽)
void BST::preorder(nod *ptr)
{
    if (r == NULL)
    {
        cout << "트리가 비어 있습니다" << endl;
        return;
    }
    if (ptr != NULL)
    {
        cout << ptr->info << " ";
        preorder(ptr->l);
        preorder(ptr->r);
    }
}

// 중위 순회 (왼쪽 - 루트 - 오른쪽)
void BST::inorder(nod *ptr)
{
    if (r == NULL)
    {
        cout << "트리가 비어 있습니다" << endl;
        return;
    }
    if (ptr != NULL)
    {
        inorder(ptr->l);
        cout << ptr->info << " ";
        inorder(ptr->r);
    }
}

// 후위 순회 (왼쪽 - 오른쪽 - 루트)
void BST::postorder(nod *ptr)
{
    if (r == NULL)
    {
        cout << "트리가 비어 있습니다" << endl;
        return;
    }
    if (ptr != NULL)
    {
        postorder(ptr->l);
        postorder(ptr->r);
        cout << ptr->info << " ";
    }
}

// 트리 구조 출력
void BST::show(nod *ptr, int level)
{
    int i;
    if (ptr != NULL)
    {
        show(ptr->r, level + 1);
        cout << endl;
        if (ptr == r)
            cout << "Root->: ";
        else
        {
            for (i = 0; i < level; i++)
                cout << " ";
        }
        cout << ptr->info;
        show(ptr->l, level + 1);
    }
}

int main()
{
    int c, n, item;
    BST bst;
    nod *t;
    while (1)
    {
        cout << "1.원소 삽입" << endl;
        cout << "2.원소 삭제" << endl;
        cout << "3.원소 탐색" << endl;
        cout << "4.중위 순회" << endl;
        cout << "5.전위 순회" << endl;
        cout << "6.후위 순회" << endl;
        cout << "7.트리 출력" << endl;
        cout << "8.종료" << endl;
        cout << "메뉴를 선택하세요 : ";
        cin >> c;
        switch (c)
        {
        case 1:
            t = new nod;
            cout << "삽입할 숫자 입력 : ";
            cin >> t->info;
            bst.insert(r, t);
            break;
        case 2:
            if (r == NULL)
            {
                cout << "트리가 비어 있어 삭제할 것이 없습니다" << endl;
                continue;
            }
            cout << "삭제할 숫자 입력 : ";
            cin >> n;
            bst.del(n);
            break;
        case 3:
            cout << "탐색:" << endl;
            cin >> item;
            bst.search(r, item);
            break;
        case 4:
            cout << "BST 중위 순회 결과:" << endl;
            bst.inorder(r);
            cout << endl;
            break;
        case 5:
            cout << "BST 전위 순회 결과:" << endl;
            bst.preorder(r);
            cout << endl;
            break;
        case 6:
            cout << "BST 후위 순회 결과:" << endl;
            bst.postorder(r);
            cout << endl;
            break;
        case 7:
            cout << "BST 출력:" << endl;
            bst.show(r, 1);
            cout << endl;
            break;
        case 8:
            exit(1);
        default:
            cout << "잘못된 선택입니다" << endl;
        }
    }
}

실행 결과

1.원소 삽입
2.원소 삭제
3.원소 탐색
4.중위 순회
5.전위 순회
6.후위 순회
7.트리 출력
8.종료
메뉴를 선택하세요 : 1
삽입할 숫자 입력 : 6
루트 노드가 추가되었습니다
...
메뉴를 선택하세요 : 1
삽입할 숫자 입력 : 7
오른쪽에 노드가 추가되었습니다
...
메뉴를 선택하세요 : 1
삽입할 숫자 입력 : 5
왼쪽에 노드가 추가되었습니다
...
메뉴를 선택하세요 : 1
삽입할 숫자 입력 : 4
왼쪽에 노드가 추가되었습니다
...
메뉴를 선택하세요 : 3
탐색:
7
데이터를 깊이 2에서 찾았습니다
...
메뉴를 선택하세요 : 3
탐색:
1
데이터를 찾을 수 없습니다
...
메뉴를 선택하세요 : 4
BST 중위 순회 결과:
4 5 6 7
...
메뉴를 선택하세요 : 5
BST 전위 순회 결과:
6 5 4 7
...
메뉴를 선택하세요 : 6
BST 후위 순회 결과:
4 5 7 6
...
메뉴를 선택하세요 : 7
BST 출력:
      7
Root->: 6
   5
      4
...
메뉴를 선택하세요 : 2
삭제할 숫자 입력 : 1
트리에 해당 항목이 없습니다
...
메뉴를 선택하세요 : 2
삭제할 숫자 입력 : 5
항목이 삭제되었습니다
...
메뉴를 선택하세요 : 7
BST 출력:
   7
Root->: 6
4
...
메뉴를 선택하세요 : 8

정리

이 프로그램은 C++ 클래스를 활용해 이진 탐색 트리의 핵심 연산인 탐색, 삽입, 삭제, 세 가지 순회 방식을 모두 구현한 예제입니다. 특히 삭제 연산은 자식 노드의 개수에 따라 세 가지 경우로 나누어 처리하며, 자식이 둘인 경우에는 오른쪽 서브트리의 최솟값(중위 후속자)으로 대체하는 표준적인 방법을 사용합니다. 중위 순회 결과가 항상 오름차순으로 정렬되어 출력되는 점을 확인하면 BST의 정렬 특성을 쉽게 이해할 수 있습니다.