트리(Tree)

신민기·2025년 10월 23일

자료구조

목록 보기
1/2
post-thumbnail

트리

트리는 비선형적인 자료구조로써 계층적인 자료를 표현하는데 적합한 자료구조이다.
이러한 구조를 트리리거 부르는 이유는 마치 실제 트리를 거꾸로 엎어놓은 것 같은 모양을 하고 있기 때문이다.

트리의 용어들

트리의 원을 노드라하고 선을 간선(엣지)라 한다.

트리는 한 개 이상의 노드로 이루어진 유한 집합이다.

이들 중 모든 노드의 위에 있는 있는 노드는 루트 노드라하고 그 외의 노드들은 서브 트리라고 불린다.

계층적인 구조에서 가장 높은 곳에 있는 노드인 A가 루트가 된다.

트리에서 루트와 서브트리는 간선으로 연결된다. 노드들 간에는 부모 관계, 형제 관계, 조상과 자손 관계가 존재한다.

  • 부모 노드(parent node): 어떤 노드 위에 바로 연결된 노드이다.(A는 B의 부모 노드)

  • 자식 노드(children node): 어떤 노드 아레에 바로 연결된 노드이다.(반대로 B는 A의 자식 노드)

  • 형제 관계(sibling): 같은 부모 노드의 자식 노드들이다.(B와 C는 형제 관계)

  • 조상 노드(ancestor node): 루트 노드부터 임의의 노드까지의 경로를 이루는 노드이다.

  • 후손 노드(dscendent node): 임의의 노드 하위에 연결된 모든 노드이다.

  • 단말노드(terminal node, leaf node): 자식 노드가 없는 노드이다.

  • 비단말 노드(nonterminal node): 단말 노드 이외에 노드이다.

  • 노드의 차수(degree): 어떤 노드가 가지고 있는 자식 노드의 개수를 의미한다.

  • 트리의 차수(Tree degree): 트리에 있는 노드의 차수 중 최댓값을 트리의 차수로 갖는다.

  • 레벨(level): 트리의 각층에 번호를 매기는 것으로서 정의에 의하여 루트에 레벨은 0이 되고(1도 될 수 있다.) 한 층씩 내려갈수록 1씩 증가한다.(A의 레벨은 0이고 B의 레벨은 1이다.)

  • 트리의 높이(height): 트리가 가지고 있는 최대 레벨을 말한다.

이진 트리

모든 노드가 2개의 서브 트리를 가지고 있는 트리를 이진 트리(binary tree)라고 한다.

이진 트리의 정의는 다음과 같다.

  • 공집합이거나

  • 루트와 왼쪽 서브 트리, 오른쪽 서브 트리로 구성된 노드들의 유한 집합으로 정의된다. 이진 트리의 서브 트리들은 모두 이진 트리여야한다.

포화 이진 트리

이진트리이면서 서브트리까지 모두 빈 곳 없이 꽉찬 트리를 말한다.

완전 이진 트리

노드가 상위 레벨부터 차례대로 왼쪽->오른쪽 순으로 채워져 있는 트리를 말한다.(포화 이진 트리는 완전 이진 트리 중 하나이다.)

이진트리의 성질

  • n개의 노드를 가진 이진 트리는 정확하게 n-1의 간선을 가진다. 그 이유는 이진트리에서의 노드는 루트를 제외하면 정확하게 하나의 부모 노드를 가진다. 그리고 부모와 자식 간에는 정확하게 하나의 간선만이 존재한다. 따라서고 부모와 자식 간에는 정확하게 하나의 간선만이 존재한다. 따라서 간서의 개수는 n-1이다.

  • 높이가 h인 이진 트리의 경우, 최소 h개의 노드를 가지며 최대 2h−12^h-1개의 노드를 가진다. 그 이유는 한 레벨에는 적어도 하나의 노드는 존재해야 하므로 높이가 h인 이진 트리는 적어도 h개의 노드를 가진다. 또한 하나의 노드는 최대 2개의 자식을 가질 수 있으므로 레벨 i에서의 노드의 최대개수는 2i−12^{i-1}이 된다. 따라서 전체 노드 개수는 ∑i=1h2i−1=2h−1\sum_{i=1}^{h} 2^{i-1}=2^h-1이 된다.(루트의 레벨이 1일 때의 예)

  • n개의 노드를 가지는 이진 트리의 높이는 최대 n이거나 최소 [log2(n+1)log_2(n+1)]이 된다. 그 이유는 레벨 당 최소한 하나의 노드는 있어야 하므로 높이가 n을 넘을 수는 없다. 그리고 앞의 성질에서 높이 h의 이진 트리가 가질 수 있는 노드의 최대값은 2h−12^h-1이다. 따라서 n≤2h−1n\le2^h-1의 부등식이 성립하고 양변에 log를 취하여 정리하면 h≥log2(n+1)h \ge log_2(n+1)이 된다. h는 정수이어야 하므로 [h≥log2(n+1)h \ge log_2(n+1)]이 된다. [···]은 올림 연산으로 [2.4]는 3이 된다.(루트의 레벨이 1일 때의 예)

이진 트리의 순회

순회(traversal) : 트리에 속하는 모든 노드를 한 번씩 방문하여 노드가 가지고 있는 데이터를 목적에 맞게 처리하는 것

이진 트리의 순회에서 서브 트리는 전체 이진 트리와 구조가 같기 때문에 서브 트리에게도 전체 이진 트리와 똑같은 방법을 적용할 수 있다.

이진 트리를 순회하는 표준적인 방법에는 전위, 중위, 후위의 3가지 방법이 있다.

"n0=n_0= 자식을 가지지 않은 노드 수, n1=n_1= 자식을 한 개 가진 노드 수, n2=n_2= 자식을 두 개 가진 노드 수" 일 때 함수를 호출하는 횟수는 n0+n1+n2+n0×2+n1n_0+n_1+n_2+n_0×2+n_1이다.

  • 전위 순회
    전위 순회는 루트를 먼저 방문하고 다음에 왼쪽 서브트리, 오른쪽 서브트리 순으로 방문한다.

코드 

void preorder(TreeNode *root) {
    if (root != NULL) {
        printf("[%d] ", root->data);    // 노드 방문
        preorder(root->left);           // 왼쪽 서브트리 순회
        preorder(root->right);          // 오른쪽 서브트리 순회
    }
}
  • 중위 순회
    중위 순회는 왼쪽 서브트리, 루트, 오른쪽 서브트리 순으로 방문한다.

코드

void inorder(TreeNode *root) {
    if (root != NULL) {
        inorder(root->left);            // 왼쪽 서브트리 순회
        printf("[%d] ", root->data);    // 노드 방문
        inorder(root->right);           // 오른쪽 서브트리 순회
    }
}
  • 후위 순회
    후위 순회는 왼쪽 서브트리, 오른쪽 서브트리, 루트 순으로 방문한다.

코드

void postorder(TreeNode *root) {
    if (root != NULL) {
        postorder(root->left);          // 왼쪽 서브트리 순회
        postorder(root->right);         // 오른쪽 서브트리 순회
        printf("[%d] ", root->data);    // 노드 방문
    }
}

  • 레벨 순회(level order)

    각 노드를 레벨 순으로 검사하는 순회 방법이다.
    동일한 레벨의 경우에는 좌에서 우로 방문한다.
    전위/중위/후위는 스택을 사용하지만(코드에는 스택이 나타나지 않지만 순환 호출을 하였기 때문에 간접적으로 스택을 사용한 것이다.)
    레벨 순회는 큐를 사용한다.

void level_order(TreeNode *ptr) {
    QueueType q;
    init_queue(&q);
    if (ptr == NULL) return;
    
    enqueue(&q, ptr);
    while (!is_empty(&q)) {
        ptr = dequeue(&q);
        printf(" [%d] ", ptr->data);
        if (ptr->left) {
            enqueue(&q, ptr->left);
        }
        if (ptr->right) {
            enqueue(&q, ptr->right);
        }
    }
}

레벨 순회의 코드는 큐에 노드가 남아있으면 계속 반복하는 코드로 이루어져있다.
먼저 큐에 있는 노드를 꺼내어 방문한 다음, 그 노드의 자식 노드를 큐에 삽입하는 것으로 한번의 반복을 끝낸다.
이러한 반복을 큐에 더 이상의 노드가 없을 때까지 계속한다.

위와 같은 이진 트리가 있을 때 각 탐색이 어떻게 실행되는지 보여주겠다.

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

// 노드 구조체 정의
typedef struct Node {
    int data;
    struct Node* left;
    struct Node* right;
} Node;

// 노드 생성 함수
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = data;
    newNode->left = newNode->right = NULL;
    return newNode;
}

// 전위 순회 (Preorder: Root → Left → Right)
void preorder(Node* root) {
    if (root == NULL) return;
    printf("%d ", root->data);
    preorder(root->left);
    preorder(root->right);
}

// 중위 순회 (Inorder: Left → Root → Right)
void inorder(Node* root) {
    if (root == NULL) return;
    inorder(root->left);
    printf("%d ", root->data);
    inorder(root->right);
}

// 후위 순회 (Postorder: Left → Right → Root)
void postorder(Node* root) {
    if (root == NULL) return;
    postorder(root->left);
    postorder(root->right);
    printf("%d ", root->data);
}

// 🌿 레벨 순회 (Level-order Traversal)
void levelorder(Node* root) {
    if (root == NULL) return;
    Node* queue[100];
    int front = 0, rear = 0;
    queue[rear++] = root;
    while (front < rear) {
        Node* cur = queue[front++];
        printf("%d ", cur->data);
        if (cur->left) queue[rear++] = cur->left;
        if (cur->right) queue[rear++] = cur->right;
    }
}

int main() {
    // 트리 구성
    //         1
    //        / \
    //       2   3
    //      / \
    //     4   5
    Node* root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);

    printf("전위 순회: ");
    preorder(root);
    printf("\n");

    printf("중위 순회: ");
    inorder(root);
    printf("\n");

    printf("후위 순회: ");
    postorder(root);
    printf("\n");

    printf("레벨 순회: ");
    levelorder(root);
    printf("\n");

    return 0;
}

노드의 개수

노드의 개수를 세기 위해서는 트리 안의 노드들을 전체적으로 순회하여야 한다. 각각의 서브트리에 대하여 순환 호출한 다음, 반환되는 값에 1을 더하여 반환하면 된다.(1을 더하는 이유는 서브트리 뿐만 아니라 자기자신까지 포함하여 세기 때문이다.)

코드

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

// 트리 노드 구조체 정의
typedef struct TreeNode {
    int data;
    struct TreeNode* left;
    struct TreeNode* right;
} TreeNode;

// 노드 개수를 구하는 함수
int get_node_count(TreeNode* node) {
    int count = 0;
    if (node != NULL)
        count = 1 + get_node_count(node->left) + get_node_count(node->right);
    return count;
}

// 새 노드를 만드는 함수
TreeNode* create_node(int data) {
    TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return node;
}

int main() {
    TreeNode* root = create_node(1);
    root->left = create_node(2);
    root->right = create_node(3);
    root->left->left = create_node(4);
    root->left->right = create_node(5);

    printf("트리의 노드 개수: %d\n", get_node_count(root));

    return 0;
}

이러한 방식으로 단말 노드의 개수도 구할 수 있다
단말 노드의 개수를 구할 때에는 노드의 각각의 서브트리가 NULL인지 판단하면 구할 수 있다.

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

// 트리 노드 구조체 정의
typedef struct TreeNode {
    int data;
    struct TreeNode* left;
    struct TreeNode* right;
} TreeNode;

// 리프 노드 개수를 세는 함수
int get_leaf_count(TreeNode* node) {
    int count = 0;
    if (node != NULL) {
        if (node->left == NULL && node->right == NULL) {
            return 1;  // 양쪽 자식이 없으면 리프 노드!
        }
        else {
            count = get_leaf_count(node->left) + get_leaf_count(node->right);
        }
    }
    return count;
}

// 노드 생성 함수
TreeNode* create_node(int data) {
    TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return node;
}

int main() {
    TreeNode* root = create_node(1);
    root->left = create_node(2);
    root->right = create_node(3);
    root->left->left = create_node(4);
    root->left->right = create_node(5);

    printf("트리의 리프 노드 개수: %d\n", get_leaf_count(root));

    return 0;
}

높이 구하기

각각의 서브트리의 높이를 비교하여 높은 쪽을 반환하여 최댓값을 구한다.

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

// 트리 노드 구조체 정의
typedef struct TreeNode {
    int data;
    struct TreeNode* left;
    struct TreeNode* right;
} TreeNode;


// 트리의 높이를 구하는 함수
int get_height(TreeNode* node) {
    int height = 0;
    if (node != NULL) {
        height = 1 + max(get_height(node->left), get_height(node->right));
    }
    return height;
}

// 노드 생성 함수
TreeNode* create_node(int data) {
    TreeNode* node = (TreeNode*)malloc(sizeof(TreeNode));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return node;
}

int main() {
    TreeNode* root = create_node(1);
    root->left = create_node(2);
    root->right = create_node(3);
    root->left->left = create_node(4);
    root->left->right = create_node(5);

    printf("트리의 높이: %d\n", get_height(root));

    return 0;
}

이진탐색트리

탐색작업을 효율적으로 하기 위한 이진 트리를 이용한 자료구조이다.

이진 탐색 트리의 정의는 다음과 같다.

  • 모든 원소의 키는 유일한 키를 가진다.
  • 왼쪽 서브 트리 키들은 루트 키보다 작다.
  • 오른쪽 서브 트리의 키들은 루트의 키보다 크다.
  • 왼쪽과 오른쪽 서브 트리도 이진 탐색 트리이다.

이진 탐색 트리의 탐색 방법

이진 탐색 트리의 탐색은 탐색 키 값이 루트 노드의 키 값보다 작으면 루트 노드의 왼쪽 자식노드를 기준으로 다시 시작하고 탐색 키 값이 루트 노드의 키 값보다 크면 루트 노드의 오른쪽 자식노드를 기준으로 다시 시작한다. 또한 비교 결과가 같으면 그 값을 반환하고(성공) node가 NULL이 된다면 NULL을 반환한다.(실패)

순환적인 탐색연산

TreeNode *search(TreeNode *node, int key)
{
    if(node == NULL) return NULL;
    if(key == node->data) return node;
    else if(key <= node->data) 
        return search(node->left, key);
    else 
        return search(node->right, key);
}

반복적인 탐색연산

TreeNode *search(TreeNode *node, int key)
{
    while(node != NULL) {
        if(key == node->data) return node;
        else if(key <= node->data) 
            node = node->left;
        else
            node = node->right;
    }
    return NULL;
}

이진 탐색트리부터는 코드가 길어져서 필요한 코드만 기재한다.

이진 탐색 트리를 탐색하는 방법은 순환적인 탐색연산보다 반복적인 탐색연산이 효율적이다.(순환은 반환을 해야하기 때문에 반복보다 오래 걸린다.)

전체 코드

#include <stdio.h>
#include <stdlib.h> // malloc, free 함수 사용을 위해 필요

// 1. TreeNode 구조체 정의
typedef struct TreeNode {
    int data;
    struct TreeNode* left;
    struct TreeNode* right;
} TreeNode;

// 2. 새 노드를 생성하는 헬퍼 함수
TreeNode* createNode(int data) {
    // 새 노드에 메모리 할당
    TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
    if (newNode == NULL) {
        printf("메모리 할당 오류\n");
        exit(1); // 오류 시 프로그램 종료
    }
    newNode->data = data;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

// 3. 제공된 'search' 함수 (반복 방식)
TreeNode* search(TreeNode* node, int key)
{
    // node가 NULL이 아닐 동안 (트리의 끝에 도달하지 않을 동안) 반복
    while (node != NULL) {
        if (key == node->data) {
            // 키를 찾았으면 해당 노드 반환
            return node;
        }
        else if (key <= node->data) {
            // 찾는 키가 현재 노드 데이터보다 작거나 같으면 왼쪽으로 이동
            node = node->left;
        }
        else {
            // 찾는 키가 현재 노드 데이터보다 크면 오른쪽으로 이동
            node = node->right;
        }
    }
    // 반복문이 끝날 때까지 못찾았으면 NULL 반환
    return NULL;
}

// 4. 트리의 모든 노드 메모리를 해제하는 함수 (후위 순회)
void freeTree(TreeNode* node) {
    if (node == NULL) {
        return;
    }
    freeTree(node->left);  // 왼쪽 서브트리 해제
    freeTree(node->right); // 오른쪽 서브트리 해제
    free(node);            // 현재 노드 해제
}


// 5. 메인 함수
int main() {
    // --- 이미지의 이진 탐색 트리 생성 ---
    TreeNode* root = createNode(18);

    root->left = createNode(7);
    root->left->left = createNode(3);
    root->left->right = createNode(12);

    root->right = createNode(26);
    root->right->right = createNode(31);
    root->right->right->left = createNode(27);
    // ------------------------------------

    int key1; // 트리에 존재하는 값
    int key2;
    printf("탐색할 값을 입력하시오: ");
    scanf("%d", &key1);
    printf("탐색할 값을 입력하시오: ");
    scanf("%d", &key2);
    TreeNode* result1 = search(root, key1);
    TreeNode* result2 = search(root, key2);


    // key1 (27) 탐색 결과
    if (result1 != NULL) {
        printf("키 %d(을)를 찾았습니다. (노드 값: %d)\n", key1, result1->data);
    }
    else {
        printf("키 %d(을)를 찾지 못했습니다.\n", key1);
    }

    // key2 (99) 탐색 결과
    if (result2 != NULL) {
        printf("키 %d(을)를 찾았습니다. (노드 값: %d)\n", key2, result2->data);
    }
    else {
        printf("키 %d(을)를 찾지 못했습니다.\n", key2);
    }

    // 할당된 트리 메모리 해제
    freeTree(root);

    return 0;
}

이진 탐색 트리에서 삽입연산

이진 탐색 트리에 원소를 삽입하기 위해서는 먼저 탐색을 수행해야한다. 그 이유는 같은 키 값을 갖는 노드가 없어야기 때문이고 또한 탐색에 실패한 위치가 바로 새로운 노드를 삽입하는 위치가 되기 때문이다.

코드

TreeNode* new_node(int item)
{
    TreeNode* temp = (TreeNode*)malloc(sizeof(TreeNode));
    temp->key = item;
    temp->left = temp->right = NULL;
    return temp;
}

TreeNode* insert_node(TreeNode* node, int key)
{
    if (node == NULL){
    	return new_node(key);
	}
    if (key == node->key){
        fprintf(stderr, "중복 key 값 오류\n");
    }
    else if (key < node->key){
        node->left = insert_node(node->left, key);
    }
    else{
        node->right = insert_node(node->right, key);
	}
    return node;
}

전체 코드

#include <stdio.h>
#include <stdlib.h> // malloc, free, stderr 사용

// 1. TreeNode 구조체 정의
// (제공된 코드에 맞게 멤버 변수 이름을 'key'로 사용)
typedef struct TreeNode {
    int key;
    struct TreeNode* left;
    struct TreeNode* right;
} TreeNode;

// 2. 제공된 'new_node' 함수 (새 노드 생성)
TreeNode* new_node(int item)
{
    // 새 노드에 메모리 할당
    TreeNode* temp = (TreeNode*)malloc(sizeof(TreeNode));
    if (temp == NULL) {
        fprintf(stderr, "메모리 할당 오류\n");
        exit(1);
    }
    temp->key = item;
    temp->left = temp->right = NULL;
    return temp;
}

// 3. 제공된 'insert_node' 함수 (재귀 방식 삽입)
TreeNode* insert_node(TreeNode* node, int key)
{
    // 트리가 비어 있으면 새 노드를 생성하여 반환
    if (node == NULL) {
        return new_node(key);
    }

    // 중복된 키 값 처리
    if (key == node->key) {
        fprintf(stderr, "중복 key 값(%d) 오류. 삽입하지 않습니다.\n", key);
    }
    // 키가 현재 노드보다 작으면 왼쪽 서브트리로 이동
    else if (key < node->key) {
        node->left = insert_node(node->left, key);
    }
    // 키가 현재 노드보다 크면 오른쪽 서브트리로 이동
    else {
        node->right = insert_node(node->right, key);
    }

    // 변경된(또는 변경되지 않은) 루트 노드의 포인터 반환
    return node;
}

// 4. 트리를 중위 순회하며 출력하는 함수 (검증용)
// (BST를 중위 순회하면 키 값이 정렬되어 나옵니다)
void inorder_traversal(TreeNode* node) {
    if (node != NULL) {
        inorder_traversal(node->left);  // 왼쪽
        printf("%d -> ", node->key);    // 루트
        inorder_traversal(node->right); // 오른쪽
    }
}

// 5. 트리의 모든 노드 메모리를 해제하는 함수
void freeTree(TreeNode* node) {
    if (node == NULL) {
        return;
    }
    freeTree(node->left);
    freeTree(node->right);
    free(node);
}

// 6. 메인 함수
int main() {
    TreeNode* root = NULL; // 트리의 루트 포인터, 처음엔 비어있음

    // 이미지에 있는 노드들을 삽입
    // (삽입 순서는 루트부터 임의로 정함)
    printf("노드를 삽입합니다...\n");
    root = insert_node(root, 18);
    root = insert_node(root, 7);
    root = insert_node(root, 26);
    root = insert_node(root, 3);
    root = insert_node(root, 12);
    root = insert_node(root, 31);
    root = insert_node(root, 27);

    // 삽입 결과 확인 (중위 순회)
    printf("\n--- 중위 순회 결과 (정렬된 순서) ---\n");
    inorder_traversal(root);
    printf("NULL\n");

    // 중복 값 삽입 시도
    printf("\n--- 중복 값(12) 삽입 시도 ---\n");
    root = insert_node(root, 12);

    // 중복 삽입 후 결과 (변화 없음)
    printf("\n--- 중복 삽입 시도 후 중위 순회 결과 ---\n");
    inorder_traversal(root);
    printf("NULL\n");

    // 메모리 해제
    freeTree(root);
    printf("\n트리 메모리 해제 완료.\n");

    return 0;
}

이진 탐색 트리에서 삭제 연산

노드를 삭제하려면 먼저 노드를 탐색하여야 한다는 것은 삽입과 마찬가지다. 노드를 탐색하였으면 다음의 3가지 경우를 고려하여야 한다.

  1. 삭제하려는 노드가 단말 노드일 경우
  2. 삭제하려는 노드가 하나의 왼쪽이나 오른쪽 서브 트리중 하나만 가지고 있는 경우
  3. 삭제하려는 노드가 두개의 서브트리 모두 가지고 있는 경우

  • 삭제하려는 노드가 단말 노드일 경우
    이 경우에서는 단말노드 아래에 더 이상의 노드가 없으므로 가장 쉽게 할 수 있다. 단말 노드의 부모노드를 찾아서 부모노드안의 링크필드를 NULL로 만든 다음 단말 노드를 동적 메모리 해제시키면 된다.(동적할당을 헀을 경우)

  • 삭제하려는 노드가 하나의 서브트리만 가지고 있는 경우
    이 경우에서는 자기 노드는 삭제하고 서브 트리는 자기 노드의 부모 노드에 붙여주면 된다.

  • 삭제하려는 노드가 두 개의 서브트리를 가지고 있는 경우
    이 경우는 이진 탐색 트리의 정의를 잘 봐야한다. 기준이 되는 루트의 왼쪽에는 루트보다 작은 수가 가야되고 오른쪽에는 루트보다 큰 수가 가야된다.
    그러므로 이 둘의 조건을 만족시킬 노드를 삭제하려는 노드의 서브트리들에서 찾아야하는데 두 가지 노드가 있다.
    왼쪽 서브트리에서 가장 큰 값이 있는 노드와 오른쪽 서브트리에서 가장 작은 값이 있는 노드가 해당된다. 이 노드들 중 아무거나 사용해도 상관이 없다.

코드

TreeNode* min_value_node(TreeNode* node)
{
    TreeNode* current = node;

    while (current->left != NULL)
        current = current->left;

    return current;
}

TreeNode* delete_node(TreeNode* root, int key)
{
    if (root == NULL) return root;

    if (key < root->key)
        root->left = delete_node(root->left, key);
    else if (key > root->key)
        root->right = delete_node(root->right, key);
    else { 
        if (root->left == NULL) {
            TreeNode* temp = root->right;
            free(root);
            return temp;
        }
        else if (root->right == NULL) {
            TreeNode* temp = root->left;
            free(root);
            return temp;
        }

        TreeNode* temp = min_value_node(root->right);

        root->key = temp->key;

        root->right = delete_node(root->right, temp->key);
    }
    return root;
}

전체 코드

#include <stdio.h>
#include <stdlib.h> // malloc, free, stderr 사용

// 1. TreeNode 구조체 정의
typedef struct TreeNode {
    int key;
    struct TreeNode* left;
    struct TreeNode* right;
} TreeNode;

// 2. 새 노드 생성 함수 (삽입 시 필요)
TreeNode* new_node(int item)
{
    TreeNode* temp = (TreeNode*)malloc(sizeof(TreeNode));
    if (temp == NULL) {
        fprintf(stderr, "메모리 할당 오류\n");
        exit(1);
    }
    temp->key = item;
    temp->left = temp->right = NULL;
    return temp;
}

// 3. 노드 삽입 함수 (트리 구성 시 필요)
TreeNode* insert_node(TreeNode* node, int key)
{
    if (node == NULL) {
        return new_node(key);
    }
    if (key == node->key) {
        // 중복 값은 무시 (오류 메시지 생략)
    }
    else if (key < node->key) {
        node->left = insert_node(node->left, key);
    }
    else {
        node->right = insert_node(node->right, key);
    }
    return node;
}

// 4. (제공된 함수) 오른쪽 서브트리에서 최소값 노드를 찾는 함수
// (삭제 시 자식이 둘인 노드를 대체할 노드를 찾기 위함)
TreeNode* min_value_node(TreeNode* node)
{
    TreeNode* current = node;

    // 가장 왼쪽 노드(최소값)를 찾아 이동
    while (current && current->left != NULL) // current가 NULL이 아닌지 확인 추가
        current = current->left;

    return current;
}

// 5. (제공된 함수) 노드 삭제 함수
TreeNode* delete_node(TreeNode* root, int key)
{
    // 1. 기본 단계 (트리가 비었으면 반환)
    if (root == NULL) return root;

    // 2. 삭제할 노드를 찾는 과정 (재귀 호출)
    if (key < root->key) {
        // 키가 루트보다 작으면 왼쪽 서브트리에서 삭제 시도
        root->left = delete_node(root->left, key);
    }
    else if (key > root->key) {
        // 키가 루트보다 크면 오른쪽 서브트리에서 삭제 시도
        root->right = delete_node(root->right, key);
    }
    // 3. 키를 찾은 경우 (key == root->key)
    else {
        // 경우 1: 자식 노드가 없거나 하나만 있는 경우
        if (root->left == NULL) {
            TreeNode* temp = root->right;
            free(root); // 현재 노드 메모리 해제
            return temp; // 오른쪽 자식을 (새로운) 루트로 반환
        }
        else if (root->right == NULL) {
            TreeNode* temp = root->left;
            free(root); // 현재 노드 메모리 해제
            return temp; // 왼쪽 자식을 (새로운) 루트로 반환
        }

        // 경우 2: 자식 노드가 둘 다 있는 경우
        // (오른쪽 서브트리에서 가장 작은 값(inorder successor)을 찾음)
        TreeNode* temp = min_value_node(root->right);

        // 찾은 후계자 노드의 키 값을 현재 노드(삭제할 노드)에 복사
        root->key = temp->key;

        // 원본 후계자 노드를 오른쪽 서브트리에서 삭제
        root->right = delete_node(root->right, temp->key);
    }
    return root; // 변경된 루트 포인터 반환
}

// 6. 트리를 중위 순회하며 출력하는 함수 (검증용)
void inorder_traversal(TreeNode* node) {
    if (node != NULL) {
        inorder_traversal(node->left);
        printf("%d -> ", node->key);
        inorder_traversal(node->right);
    }
}

// 7. 트리의 모든 노드 메모리를 해제하는 함수
void freeTree(TreeNode* node) {
    if (node == NULL) {
        return;
    }
    freeTree(node->left);
    freeTree(node->right);
    free(node);
}

// 8. 메인 함수 (삽입 및 삭제 테스트)
int main() {
    TreeNode* root = NULL;

    // --- 1. 이미지의 트리 구성 ---
    int keys[] = { 18, 7, 26, 3, 12, 31, 27 };
    int n = sizeof(keys) / sizeof(keys[0]);

    printf("--- 노드 삽입 중 ---\n");
    for (int i = 0; i < n; i++) {
        root = insert_node(root, keys[i]);
    }

    printf("\n--- 초기 트리 상태 (중위 순회) ---\n");
    inorder_traversal(root); // 3 -> 7 -> 12 -> 18 -> 26 -> 27 -> 31 -> NULL
    printf("NULL\n");

    // --- 2. 삭제 테스트 ---

    // 테스트 1: 리프 노드 삭제 (key: 3)
    printf("\n--- [테스트 1] 리프 노드 (3) 삭제 ---\n");
    root = delete_node(root, 3);
    inorder_traversal(root); // 7 -> 12 -> 18 -> 26 -> 27 -> 31 -> NULL
    printf("NULL\n");

    // 테스트 2: 자식이 1개인 노드 삭제 (key: 31)
    // (31은 왼쪽 자식 27을 가짐)
    printf("\n--- [테스트 2] 자식 1개인 노드 (31) 삭제 ---\n");
    root = delete_node(root, 31);
    inorder_traversal(root); // 7 -> 12 -> 18 -> 26 -> 27 -> NULL
    printf("NULL\n");

    // 테스트 3: 자식이 2개인 노드 삭제 (key: 18, 루트)
    // (후계자: 오른쪽 서브트리(26, 27)의 최소값인 26이 루트가 됨)
    printf("\n--- [테스트 3] 자식 2개인 노드 (18) 삭제 ---\n");
    root = delete_node(root, 18);
    inorder_traversal(root); // 7 -> 12 -> 26 -> 27 -> NULL
    printf("NULL\n");

    // 테스트 4: 존재하지 않는 노드 삭제 (key: 99)
    printf("\n--- [테스트 4] 없는 노드 (99) 삭제 시도 ---\n");
    root = delete_node(root, 99);
    inorder_traversal(root); // (변화 없음) 7 -> 12 -> 26 -> 27 -> NULL
    printf("NULL\n");


    // --- 3. 메모리 해제 ---
    printf("\n--- 최종 메모리 해제 ---\n");
    freeTree(root);
    printf("메모리 해제 완료.\n");

    return 0;
}

이진 탐색 트리의 분석

이진 탐색 트리에서의 탐색, 삽입, 삭제 연산의 시간복잡도는 좌우의 서브 트리가 균형을 이룰 경우에는 O(log2n)O(log_2n)이다.

하지만 최악의 경우에는 한쪽으로 치우치는 경사 트리가 되어서 트리의 높이가 n이 된다. 이 경우에는 탐색, 삽입, 삭제 연산의 시간복잡도는 O(n)O(n)이 된다.

이러한 최악의 경우를 방지하기 위해 트리의 높이를 [log2n][log_2n]으로 한정시키는 균형기법이 필요하다.

출처:
C언어로 쉽게 풀어쓴 자료구조

https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=4717010&logNo=60209552604

https://kangdy25.tistory.com/101

https://yoongrammer.tistory.com/71

profile
신민기
AI 어렵다
다음 포스트

그래프(Graph)

0개의 댓글