자료구조 트리

카테고리 없음

자료구조 트리 - 연산

김준표 2025. 11. 8. 16:16

이진탐색트리의 특징

노드의 왼쪽 하위 트리에는 노드의 키보다 작은 키가있는 노드만 포함된다.
노드의 오른쪽 하위 트리에는 노드의 키보다 큰 키가있는 노드만 포함된다.
왼쪽 및 오른쪽 하위 트리도 각각 이진탐색트리 여야한다.
중복된 키를 허용하지 않는다.

Q. 트리와 그래프의 차이는 무엇인가요?

A. 트리는 부모-자식처럼 계층 구조를 가지며 사이클(순환)이 없는 구조이고 그래프는 특정한 계층 없이 노드들이 자유롭게 연결되어 사이클이 생길 수도 있는 구조이다.

Q. 왜 중복 키를 허용하지 않을까?

A. 이진탐색트리는 규칙을 기반으로 빠르게 탐색하기 위해 만들어진 구조인데 중복된 키가 들어오면 어느 쪽에 넣어야 하는지 기준이 모호해진다.

Q. 이진트리와 이진탐색트리의 차이점은?

A. 이진트리는 단순한 2차 구조이고, 이진탐색트리는 여기에 값의 크기 규칙이 추가된 정렬된 이진트리다.

Q. 이진트리와 이진탐색트리의 차이점은?

A. 트리가 균형 잡혀 있으면 높이가 log n이 되어, 탐색·삽입·삭제 모두 O(log n) 시간이 걸린다.

최악(평향트리)

Q. BST의 평균 / 최악 시간복잡도는?

A. 평균

트리가 균형 잡혀 있으면 높이가 log n이 되어, 탐색·삽입·삭제 모두 O(log n) 시간이 걸린다

최악(평향트리)

트리가 한쪽으로만 치우친 편향 트리가 되면, 사실상 연결 리스트처럼 되어 모든 연산이 O(n)까지 떨어진다.

- 삽입 순서가 정렬되어 있으면 linked list처럼 된다.

이진탐색트리의 구현 (C언어)

#include <stdio.h>

typedef struct Node {
    int data;              // 노드가 저장하는 값
    struct Node* left;     // 왼쪽 자식 노드(없으면 NULL)
    struct Node* right;    // 오른쪽 자식 노드(없으면 NULL)
} Node;

int main() {

    /*
    Node n3 = {3, NULL, NULL}; 의 의미

    Node n3;                 // Node 라는 구조체 변수 하나를 만든다.
    n3.data = 3;             // n3가 가진 값에 3을 저장한다.
    n3.left = NULL;          // 왼쪽 자식이 없으므로 NULL.
    n3.right = NULL;         // 오른쪽 자식도 없으므로 NULL.

    {3, NULL, NULL} 은 구조체 값을 순서대로 초기화하는 "구조체 초기화 문법"이다.
    */

    // 말단 노드들
    Node n3  = {3,  NULL, NULL};   // data=3, left=NULL, right=NULL
    Node n7  = {7,  NULL, NULL};   // data=7, left=NULL, right=NULL
    Node n12 = {12, NULL, NULL};   // data=12, left=NULL, right=NULL
    Node n18 = {18, NULL, NULL};   // data=18, left=NULL, right=NULL

    /*
    여기서 n3, n7, n12, n18은 말단 노드들.
    각각 독립된 Node 구조체 변수들이다.
    이렇게 정적으로 선언했기 때문에 메모리 할당 필요X
    */

    // 중간 노드들 (자식 연결)
    Node n5  = {5,  &n3,  &n7};
    /*
    n5.data = 5
    n5.left = &n3  →  n3의 주소를 저장 (왼쪽 자식으로 설정)
    n5.right = &n7 →  n7의 주소를 저장 (오른쪽 자식으로 설정)

    즉 n5 → left → n3
       n5 → right → n7
    형태로 트리 연결됨
    */

    Node n15 = {15, &n12, &n18};
    /*
    n15.data = 15
    n15.left  = &n12  →  12을 가진 노드가 왼쪽 자식
    n15.right = &n18  →  18을 가진 노드가 오른쪽 자식
    */

    // 루트 노드
    Node root = {0, &n5, &n15};
    /*
    root.data = 0
    root.left  = &n5   → 왼쪽 서브트리의 루트
    root.right = &n15  → 오른쪽 서브트리의 루트

    사진의 전체 트리 구조를 그대로 만든 것!
    */

    // 출력 테스트
    printf("root: %d\n", root.data);
    printf("root.left: %d\n", root.left->data);
    printf("root.right: %d\n", root.right->data);
    printf("root.left.left: %d\n", root.left->left->data);
    printf("root.left.right: %d\n", root.left->right->data);
    printf("root.right.left: %d\n", root.right->left->data);
    printf("root.right.right: %d\n", root.right->right->data);

    return 0;
}

*출처 : ChatGPT

이진탐색트리 탐색과 구현

탐색 과정

루트에서 탐색 시작
탐색할 값을 루트 노드와 비교한다.
비교를 통해 방향 결정
- 탐색 값이 현재 노드의 값보다 작으면 왼쪽 자식 노드로 이동
- 탐색 값이 현재 노드의 값보다 크면 오른쪽 자식 노드로 이동
일치하는 값이 나올 때까지 반복
탐색 값이 현재 노드의 값과 같으면 탐색 성공
해당 노드의 위치를 반환한다.
찾지 못한 경우
탐색 도중 더 이상 내려갈 노드(왼쪽 또는 오른쪽)가 없으면,
트리에 해당 값이 존재하지 않음(null 반환)

이진탐색트리에서 16을 찾는 과정

이진탐색트리 탐색 구현(C언어)

#include <stdio.h>

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

// 이진탐색트리 탐색 함수
// 이진탐색트리에서 'target' 값을 가진 노드를 찾아 반환하는 함수
Node* search(Node* root, int target) {

    // 1) 현재 노드가 NULL이면 (더 이상 내려갈 곳이 없으면)
    //    → 트리 안에 target이 없다는 뜻이므로 NULL 반환
    if (root == NULL) return NULL;

    // 2) 현재 노드의 값이 target과 같다면
    //    → 해당 노드를 찾았으므로 그 노드의 주소를 반환
    if (root->data == target) return root;

    // 3) 찾는 값이 현재 노드보다 작다면 왼쪽 서브트리를 탐색
    //    이진탐색트리 특성: 왼쪽엔 항상 더 작은 값들이 위치
    if (target < root->data)
        return search(root->left, target);

    // 4) 찾는 값이 현재 노드보다 크다면 오른쪽 서브트리를 탐색
    //    오른쪽엔 항상 더 큰 값들이 위치
    else
        return search(root->right, target);
}

int main() {
    // 리프 노드들
    Node n4  = {4,  NULL, NULL};
    Node n6  = {6,  NULL, NULL};
    Node n15 = {15, NULL, NULL};
    Node n17 = {17, NULL, NULL};

    // 중간 노드들
    Node n5  = {5,  &n4,  &n6};
    Node n16 = {16, &n15, &n17};

    // 루트 노드
    Node root = {7, &n5, &n16};

    // 탐색할 값
    int target = 16;

    // 탐색 수행
    Node* result = search(&root, target);

    if (result != NULL)
        printf("%d found at address %p\n", result->data, (void*)result);
    else
        printf("%d not found\n", target);

    return 0;
}

*출처 : ChatGPT

Q. 재귀와 반복문으로 각각 구현할 수 있을까?

A. 재귀는 구조가 직관적이지만 스택 오버플로우 위험이 있고, 반복문은 스택을 사용하지 않아 더 효율적이다.

Q. 탐색 함수에서 NULL을 만나면 왜 실패라고 판단하는지?

NULL에 도달했다는 것은 “값이 있어야 할 위치가 비어 있다”는 뜻이며, 따라서 탐색 실패이다.

이진탐색트리 삽입과 구현

탐색 과정

루트에서 탐색 시작
삽입할 새 데이터를 루트 노드와 비교한다.
비교하며 하향 이동
- 새 데이터가 현재 노드보다 작으면 왼쪽 자식으로 이동
- 새 데이터가 현재 노드보다 크면 오른쪽 자식으로 이동
말단 노드에 도달
이동하려는 방향의 자식 노드가 없으면, 그 자리에 새 노드를 생성한다.
삽입 수행
- 부모보다 작으면 왼쪽 자식으로 연결
- 부모보다 크면 오른쪽 자식으로 연결
- 중복 데이터는 삽입하지 않는다.

Q. BST에 삽입 시 어떤 경로를 따라 내려가나요?

BST는 새로 삽입할 값과 현재 노드의 값을 비교하며 내려간다.

삽입 값 < 현재 노드 값 → 왼쪽으로 이동
삽입 값 > 현재 노드 값 → 오른쪽으로 이동

이 비교를 반복하면서 NULL을 처음 만나는 자리가 새로운 노드가 삽입될 위치가 된다.

Q. BST에 삽입 시 어떤 경로를 따라 내려가나요?

BST는 새로 삽입할 값과 현재 노드의 값을 비교하며 내려간다.

삽입 값 < 현재 노드 값 → 왼쪽으로 이동
삽입 값 > 현재 노드 값 → 오른쪽으로 이동

이 비교를 반복하면서 NULL을 처음 만나는 자리가 새로운 노드가 삽입될 위치가 된다.

Q. 중복 키가 들어오면 어떻게 처리하나요?

기본적인 BST에서는 중복 키를 허용하지 않기 때문에 삽입을 거부하고 아무 작업도 하지 않는다.

트리에서 3을 삽입하는 과정

이진탐색트리 삽입 구현(C언어)

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

typedef struct Node {
    int data;
    struct Node* left;
    struct Node* right;
} Node;

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

// 탐색 함수
Node* search(Node* root, int target) {
    if (root == NULL) return NULL;
    if (root->data == target) return root;

    if (target < root->data)
        return search(root->left, target);
    else
        return search(root->right, target);
}

//        삽입 함수 
Node* insert(Node* root, int data) {

    // 1) 트리에서 내려가다가 비어 있는 곳(NULL)을 만나면
    //    그 위치가 새 노드가 들어갈 자리이다.
    //    즉, 탐색(search)에서는 실패이지만,
    //    삽입(insert)에서는 새 노드를 만들어 넣는 지점.
    if (root == NULL)
        return createNode(data);

    // 2) 삽입할 값이 현재 노드보다 작으면
    //    왼쪽 서브트리로 내려간다.
    //    (BST 규칙: smaller → left)
    //    insert(root->left) 결과를 root->left로 다시 연결해 줘야
    //    부모 노드와의 연결이 유지된다.
    if (data < root->data)
        root->left = insert(root->left, data);

    // 3) 삽입할 값이 현재 노드보다 크면
    //    오른쪽 서브트리로 내려간다.
    //    (BST 규칙: bigger → right)
    else if (data > root->data)
        root->right = insert(root->right, data);

    // 4) 값이 동일하면 (data == root->data)
    //    BST는 중복 값을 허용하지 않기 때문에 아무것도 하지 않고 root 반환.
    //    return root는 공통적으로 마지막에 실행된다.

    return root; // 루트 유지 (부모에게 이어주기 위해 항상 반환)
}

int main() {
    Node* root = NULL;

    // 기본 트리 구성
    root = createNode(7);
    root->left = createNode(5);
    root->right = createNode(16);

    root->left->left = createNode(4);
    root->left->right = createNode(6);

    root->right->left = createNode(15);
    root->right->right = createNode(17);

    printf("Before insertion (inorder): 4 5 6 7 15 16 17\n");

    root = insert(root, 3);

    printf("After insertion (inorder): 3 4 5 6 7 15 16 17\n");

    if (search(root, 3) != NULL)
        printf("3 inserted successfully\n");
    else
        printf("3 insertion failed\n");

    return 0;
}

*출처 : ChatGPT

Q. 삽입 함수가 항상 root를 return하는 이유는?

삽입 과정에서 서브트리가 바뀔 수 있으므로, 변경된 노드들을 연결하기 위해 최종적으로 root를 return해 전체 트리를 유지하기 위함이다.
변경된 서브트리를 부모에게 다시 연결시키기 위해 return이 필요하다.

Q. 재귀함수 insert에서 'root->left = insert(root->left, data);' 이게 왜 필요한가?

이 코드는 재귀 호출이 끝난 뒤 변경된 왼쪽 서브트리를 다시 현재 노드의 왼쪽 포인터에 연결하기 위해서 필요하다.

insert(root->left, data)는 왼쪽 서브트리에 데이터를 삽입한 뒤, 삽입이 반영된 서브트리의 루트 노드 주소를 반환한다.
그 반환값을 다시 root->left에 저장해야 트리가 끊기지 않고 유지된다.

Q.왜 포인터에다가 연결해야 될까?

재귀는 아래로 내려가면서 삽입을 수행하고, 위로 돌아오면서 트리 구조를 다시 연결하는 방식으로 동작한다.(반환하며)

새 노드가 삽입되면 왼쪽·오른쪽 서브트리의 구조가 바뀔 수 있기 때문에
그 변경된 서브트리를 부모 노드가 다시 연결해야 한다.

이진탐색트리 삭제와 구현

이진탐색트리에서 특정 노드를 삭제한다. 이진탐색트리에서 노드를 삭제하는 세 가지 방법이 있다.

1. 삭제할 노드가 말단 노드일 경우

2. 삭제할 노드에 자식이 한 개만 있는 경우

노드를 삭제하고 자식 노드를 삭제된 노드의 부모와 직접 연결한다.

2. 삭제할 노드에 자식이 두개 있을 경우

탐색 과정

삭제할 노드를 찾는다.
루트에서 시작하여 삭제하려는 값과 현재 노드의 값을 비교하며 탐색한다.
값이 작으면 왼쪽으로, 크면 오른쪽으로 이동한다.
대체할 노드를 선택한다.

삭제할 노드를 기준으로 오른쪽 자식 중에서 가장 작은 노드
삭제할 노드를 기준으로 왼쪽 자식 중에 가장 큰 노드
즉, 삭제하고 싶은 노드 키에 가장 근접한 노드로 선택하면 된다. (3,4,5,12,13,14,15,17,18,19)

값을 교체하고, 대체 노드를 삭제한다.

삭제할 노드의 값을 대체 노드의 값으로 바꾼다.
이후, 원래 대체 노드 위치에서 삭제를 수행한다.

15를 삭제하는 과정

이진탐색트리 삭제 구현(C언어)

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

typedef struct Node {
    int data;
    struct Node* left;
    struct Node* right;
} Node;

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

// 탐색 함수
Node* search(Node* root, int target) {
    if (root == NULL) return NULL;
    if (root->data == target) return root;

    if (target < root->data)
        return search(root->left, target);
    else
        return search(root->right, target);
}

// 오른쪽 서브트리에서 가장 작은 값 찾기
Node* minValueNode(Node* node) {
    Node* curr = node;
    while (curr->left != NULL)
        curr = curr->left;
    return curr;
}

//        삭제 함수
Node* deleteNode(Node* root, int key) {

    if (root == NULL) 
        return NULL;

    if (key < root->data) {
        root->left = deleteNode(root->left, key);
    }
    else if (key > root->data) {
        root->right = deleteNode(root->right, key);
    }
    else {
        // CASE 1: leaf 노드
        if (root->left == NULL && root->right == NULL) {
            free(root);
            return NULL;
        }

        // CASE 2: 자식이 하나만 있음
        else if (root->left == NULL) {
            Node* temp = root->right;
            free(root);
            return temp;
        }
        else if (root->right == NULL) {
            Node* temp = root->left;
            free(root);
            return temp;
        }

        // CASE 3: 자식이 둘 다 있음
        Node* temp = minValueNode(root->right);
        root->data = temp->data;
        root->right = deleteNode(root->right, temp->data);
    }

    return root;
}

// 테스트용 메인
int main() {
    Node* root = NULL;

    // 기본 트리 구성 (삽입 없이 직접 구성)
    root = createNode(7);
    root->left = createNode(5);
    root->right = createNode(16);

    root->left->left = createNode(4);
    root->left->right = createNode(6);

    root->right->left = createNode(15);
    root->right->right = createNode(17);

    printf("Before deletion (inorder): 4 5 6 7 15 16 17\n");

    printf("Deleting 5...\n");
    root = deleteNode(root, 5);

    printf("After deletion (inorder): 4 6 7 15 16 17\n");

    if (search(root, 5) == NULL)
        printf("5 deleted successfully\n");
    else
        printf("5 still exists\n");

    return 0;
}

*출처 : ChatGPT

이진탐색트리 순회

순회 방식으로는 현재 노드를 순회하는 순서에 따라 전위순회, 중위순회, 후위순회가 있다.

순회란 트리 구조에서 모든 노드를 일정한 규칙에 따라 한 번씩 방문하는 과정을 말한다.

DFS와 BFS에 대해

DFS(Depth-First Search)는 깊이를 우선으로 탐색하는 방식이다.
즉, 한 방향으로 끝까지 내려가고, 막히면 뒤로 돌아와서 다음 노드를 탐색한다.

구현 방법으로는 주로 재귀와 스택을 사용한다.

주로 모든 경우의 수를 탐새할 때 사용한다.

BFS(Breadth-First Search) 너비를 우선으로

즉, 같은 레벨(층)의 노드들을 먼저 탐색하고 난 뒤, 그 다음 레벨을 탐색하는 방식이다.

루트(시작점)를 큐에 넣고
큐에서 하나씩 꺼내며
그 노드의 자식들(왼→오) 을 큐에 추가
큐가 빌 때까지 반복

구현 방법으로는 큐를 사용한다.

주로 가까운 노드를 먼저 탐색해야 할 때나 최단 거리로 탐색해야 할 때 사용한다.

Q. 어떤 상황에서 DFS를 쓰고 어떤 상황에서 BFS를 쓰나요?

A. DFS는 경로 탐색이나 깊이 우선 탐색이 필요한 문제(미로, 백트래킹 등)에 적합하고,
BFS는 최단 거리나 레벨 단위 탐색이 필요한 문제(그래프 최단 경로 등)에 적합하다.

Q. DFS는 stack(재귀), BFS는 queue를 사용하는 이유?

A. DFS는 마지막에 방문한 지점으로 되돌아가는 LIFO 구조라 스택을 사용하고,
BFS는 먼저 방문한 지점을 먼저 탐색해야 하는 FIFO 구조라 큐를 사용한다.

전위순회(DFS)

전위순회는 트리에서 루트 노드를 가장 먼저 방문한 뒤, 루트를 기준으로 왼쪽에 있는 서브트리를 모두 순서대로 탐색하고, 왼쪽을 전부 끝내면 오른쪽 서브트리를 탐색하는 방식의 순회 방법이다.

“루트 → 왼쪽 서브트리 → 오른쪽 서브트리” 순서로 노드를 방문하는 방법이다

0 -> 5-> 3-> 7 -> 16 -> 12 -> 18

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

typedef struct Node {
    int data;
    struct Node* left;
    struct Node* right;
} Node;

Node* createNode(int data) {
    Node* node = malloc(sizeof(Node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return node;
}

// 전위순회: Root → Left → Right
void preorder(Node* root) {
    if (root == NULL) return;

    printf("%d ", root->data);   // 1) 루트 출력
    preorder(root->left);        // 2) 왼쪽 방문
    preorder(root->right);       // 3) 오른쪽 방문
}

int main() {
    // 트리 구성 (너가 준 그림 그대로)
    Node* root = createNode(0);

    root->left = createNode(5);
    root->right = createNode(15);

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

    root->right->left = createNode(12);
    root->right->right = createNode(18);

    printf("Preorder traversal: ");
    preorder(root);
    printf("\n");

    return 0;
}

*출처 : ChatGPT

중위순회(DFS)

중위순회는 트리에서 왼쪽 서브트리를 먼저 모두 방문하고, 그 다음 현재 노드를 방문한 뒤, 마지막으로 오른쪽 서브트리를 방문하는 순회 방식이다.

"왼쪽 서브트리 -> 루트 -> 오른쪽 서브트리" 순서로 노드를 방문하는 방법이다.

3 -> 5 -> 7-> 0 -> 12-> 15 -> 18

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

typedef struct Node {
    int data;
    struct Node* left;
    struct Node* right;
} Node;

Node* createNode(int data) {
    Node* node = malloc(sizeof(Node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return node;
}

// 중위순회: Left → Root → Right
void inorder(Node* root) {
    if (root == NULL) return;

    inorder(root->left);         // 1) 왼쪽 방문
    printf("%d ", root->data);   // 2) 루트 출력
    inorder(root->right);        // 3) 오른쪽 방문
}

int main() {
    // 트리 구성 (너가 준 그림 그대로)
    Node* root = createNode(0);

    root->left = createNode(5);
    root->right = createNode(15);

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

    root->right->left = createNode(12);
    root->right->right = createNode(18);

    printf("Inorder traversal: ");
    inorder(root);
    printf("\n");

    return 0;
}

*출처 : ChatGPT

후위순회(DFS)

후위순회는 트리에서 왼쪽 서브트리를 먼저 모두 방문하고, 그 다음 오른쪽 서브 트리를 모두 방문하고, 마지막으로 루트를 방문하는 순회 방식이다.

"왼쪽 서브트리 -> 오른쪽 서브트리 -> 루트" 순서로 노드를 방문하는 방법이다.

3 -> 7 -> 5 -> 12 -> 18 -> 15-> 0

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

typedef struct Node {
    int data;
    struct Node* left;
    struct Node* right;
} Node;

Node* createNode(int data) {
    Node* node = malloc(sizeof(Node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return node;
}

// 후위순회: Left → Right → Root
void postorder(Node* root) {
    if (root == NULL) return;

    postorder(root->left);   // 1) 왼쪽 방문
    postorder(root->right);  // 2) 오른쪽 방문
    printf("%d ", root->data); // 3) 루트 출력
}

int main() {
    Node* root = createNode(0);

    root->left = createNode(5);
    root->right = createNode(15);

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

    root->right->left = createNode(12);
    root->right->right = createNode(18);

    printf("Postorder traversal: ");
    postorder(root);
    printf("\n");

    return 0;
}

*출처 : ChatGPT

레벨순회(BFS)

레벨순회는 트리를 위에서 아래로, 같은 레벨(층)에 있는 노드들을 왼쪽에서 오른쪽 순서대로 차례대로 방문하는 탐색 방식이다.

0 -> 5 -> 15 -> 3 -> 7 -> 12 -> 18

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

typedef struct Node {
    int data;
    struct Node* left;
    struct Node* right;
} Node;

Node* createNode(int data) {
    Node* node = malloc(sizeof(Node));
    node->data = data;
    node->left = NULL;
    node->right = NULL;
    return node;
}

// 간단한 큐 구현
typedef struct Queue {
    Node* arr[100];
    int front, rear;
} Queue;

void enqueue(Queue* q, Node* value) {
    q->arr[q->rear++] = value;
}

Node* dequeue(Queue* q) {
    return q->arr[q->front++];
}

int isEmpty(Queue* q) {
    return q->front == q->rear;
}

// 레벨순회(BFS)
void levelOrder(Node* root) {
    if (root == NULL) return;

    Queue q = { .front = 0, .rear = 0 };
    enqueue(&q, root);

    while (!isEmpty(&q)) {
        Node* curr = dequeue(&q);
        printf("%d ", curr->data);

        if (curr->left) enqueue(&q, curr->left);
        if (curr->right) enqueue(&q, curr->right);
    }
}

int main() {
    Node* root = createNode(0);

    root->left = createNode(5);
    root->right = createNode(15);

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

    root->right->left = createNode(12);
    root->right->right = createNode(18);

    printf("Level-order traversal (BFS): ");
    levelOrder(root);
    printf("\n");

    return 0;
}

*출처 : ChatGPT

트리 간선의 개수 구하기

트리는 사이클 없이 모든 노드가 연결된 그래프이므로, 전체 노드를 하나로 연결하는 데 필요한 간선의 최소 개수는 노드 수에서 1을 뺀 값(N−1)이다.

사이클이란? 출발해서 다시 자기 자신으로 돌아오는 길이 있는 구조.

Q. 트리는 왜 N개의 노드가 있으면 간선은 N−1개인가요?
트리는 모든 노드가 하나의 연결된 구조를 이루면서도 사이클이 없어야 하기 때문에,
각 노드를 연결하는 데 꼭 필요한 간선만 존재하여 노드 수 N에서 루트 1개를 제외한 모든 노드가 부모와 연결되면서 총 N−1개의 간선이 생긴다.

현재글자료구조 트리 - 연산

김준표

김준표님의 블로그 입니다.

Swift, IOS, 개발,

Today :
Yesterday :

김준표