트리

이 Part에서 다루는 것

• 트리의 핵심 개념(루트/리프/깊이/높이)과 용어 정리
• 서브트리 관점으로 재귀가 트리에 잘 맞는 이유
• Node 설계, 생성/해제, 순회, 높이 계산 구현
• 게임 개발 맥락에서 트리의 실사용 포인트

학습 목표

• 트리 구조를 배열/리스트와 구분해 설명할 수 있다.
• 재귀 순회(PrintTree)와 높이 계산(GetHeight)을 직접 구현할 수 있다.
• 트리 코드에서 메모리 누수/널 처리 실수를 예방할 수 있다.

---

트리의 개념

정의

• 트리는 계층 관계를 표현하는 자료구조입니다.
• 노드(Node)는 데이터 단위, 간선(Edge)는 노드 간 연결입니다.
• 루트 하나에서 시작해 여러 자식으로 가지가 뻗는 구조를 가집니다.

개발실 조직도

          R1 개발실 (루트)
         /    |    \
   디자인  프로그래밍  아트
    /|\      /|\      /|\
  전투 경제 스토리  ...

• 선형 구조(배열/리스트)보다 “계층/분기”를 표현하기 쉽습니다.

핵심 용어

용어	설명
루트(root)	최상위 노드
부모/자식	바로 위/아래 연결 관계
형제(sibling)	같은 부모를 가진 노드
리프(leaf)	자식이 없는 노드
깊이(depth)	루트에서 현재 노드까지 간선 수
높이(height)	현재 노드에서 가장 깊은 리프까지 간선 수(또는 규약에 따라 노드 수)

이 문서의 구현 예제는 “리프 높이 = 1(노드 수 기준)” 규약을 사용합니다.

---

서브트리(Subtree)와 재귀

• 트리의 임의 노드를 루트로 보면 그 아래는 다시 트리입니다.
• 즉 “전체 문제”와 “부분 문제”의 모양이 같아서 재귀와 궁합이 좋습니다.

재귀 사고법:

1. 지금 노드에서 할 일 1개 수행
2. 각 자식에게 같은 일을 위임

---

트리 구현

Node 모델

struct Node
{
    explicit Node(const std::string& data) : data(data) {}

    std::string data;
    std::vector<Node*> children;
};

• 자식 수가 가변이므로 std::vector<Node*>를 사용합니다.
• STL에 일반 트리 컨테이너는 없어서 보통 직접 모델링합니다.

생성 예시

Node* CreateTree()
{
    Node* root = new Node("R1 개발실");

    Node* design = new Node("디자인");
    Node* programming = new Node("프로그래밍");
    Node* art = new Node("아트");

    root->children.push_back(design);
    root->children.push_back(programming);
    root->children.push_back(art);

    design->children.push_back(new Node("전투"));
    design->children.push_back(new Node("경제"));
    design->children.push_back(new Node("스토리"));

    return root;
}

해제 함수(누수 방지)

void DestroyTree(Node* root)
{
    if (root == nullptr)
        return;

    for (Node* child : root->children)
        DestroyTree(child);

    delete root;
}

• 생성(new)했다면 해제(delete)까지 짝을 맞춰야 합니다.
• 루트 1개만 알고 있어도 재귀 해제로 전체 트리를 정리할 수 있습니다.

---

PrintTree: 트리 순회(Preorder)

void PrintTree(const Node* root, int depth = 0)
{
    if (root == nullptr)
        return;

    std::cout << std::string(depth * 2, ' ') << root->data << '\n';

    for (const Node* child : root->children)
        PrintTree(child, depth + 1);
}

동작 원리:

• 현재 노드를 먼저 출력(Preorder)
• 이후 자식들을 순서대로 재귀 방문
• 자식이 없으면 반복문이 비어 자연스럽게 종료

복잡도:

• 시간 O(N) (모든 노드 1회 방문)
• 호출 스택 O(H) (H는 트리 높이)

---

GetHeight: 트리 높이 계산

정의(본 문서 규약):

• nullptr 높이 = 0
• 리프 높이 = 1

int GetHeight(const Node* root)
{
    if (root == nullptr)
        return 0;

    int maxChildHeight = 0;
    for (const Node* child : root->children)
        maxChildHeight = std::max(maxChildHeight, GetHeight(child));

    return maxChildHeight + 1;
}

핵심:

• “내 높이 = 가장 높은 자식 높이 + 1”
• 트리 DP의 가장 기본 패턴입니다.

---

트리와 게임 개발

• 게임에서 트리를 직접 다루는 예:
  • 스킬 트리, UI 계층, 씬 계층(Transform Parent-Child)
• 간접적으로는 더 자주 등장:
  • 힙(완전 이진트리 기반), BST/레드블랙트리(map/set 내부), 세그먼트 트리 등
• 그리고 그래프/탐색(DFS/BFS/A*)로 가는 중요한 빌드업 단계입니다.

체크 질문 (스스로 답해보기)

• PrintTree에서 depth 인자를 없애면 어떤 정보가 사라질까?
• GetHeight에서 리프 높이를 0으로 잡는 규약으로 바꾸려면 무엇을 수정해야 할까?
• CreateTree만 있고 DestroyTree가 없으면 어떤 문제가 생길까?

---