트리 이론

Jaemyeong Lee·2024년 10월 11일

C#C#과 유니티로 만드는 MMORPG 게임 개발 시리즈 Rookiss 자료구조와 알고리즘

C#과 유니티로 만드는 MMORPG 게임 개발 시리즈

목록 보기

79/208

전체 코드

// 트리 입문
// 우선순위 큐 구현 할 때 힙트리로 구현
// 트리의 개념
// - 계층 구조를 갖는 데이터를 표현하기 위한 자료구조
// 노드 : 데이터를 표현
// 간선 : 노드의 계층 구조를 표현하기 위해 사용
/*
R1개발실 (Root)
├── 디자인팀
│   ├── 전투팀
│   ├── 경제팀
│   └── 스토리팀
├── 프로그래밍팀
│   ├── 서버팀
│   ├── 클라이언트팀
│   └── 엔진팀
└── 아트팀
    ├── 배경팀
    └── 캐릭터팀
*/
ex) 게임 신규 개발실 구성도

// 나무 같은 느낌이 듬
// 그래프를 이용해서 구현 가능
// 한쪽으로 연결하는 그래프도 있어서
// 트리도 일종의 그래프
// 기능이 제한된 그래프
// 순환 구조가 일어나면 안됨
// 한쪽 방향으로만 뻗어야됨
// 부모에 해당하는 노드는 딱 하나만 있어야함

// 트리 관련 용어
// 부모 노드
// 자식 노드
// 형제 노드
// 선조
// 자손
// 루트
// 잎
// 노드의 깊이
// 트리의 높이
// 트리의 재귀적 속성 및 서브트리

게임 신규 개발실 구성도

🌳 1. 트리(Tree)의 정의

✔️ 트리란?

트리(Tree)는 데이터를 계층적(Hierarchical) 구조로 표현하는 자료구조야.
트리는 여러 개의 데이터가 부모-자식 관계로 연결되어 있어.
각각의 데이터는 노드(Node)로 표현되고, 노드 간의 관계는 간선(Edge)으로 표현돼.
트리의 대표적인 예:
- 파일 시스템 (폴더-파일 구조)
- 회사 조직도
- 게임 씬 그래프(Scene Graph)

🌿 2. 트리의 구성 요소

✔️ 노드(Node)

각 데이터를 나타내는 기본 단위.
노드 하나하나가 각각의 데이터를 표현해.
예) 전투팀, 스토리팀 등

✔️ 간선(Edge)

노드 간의 연결선.
부모 노드와 자식 노드 사이의 관계를 나타내.
간선을 따라 내려가면 자식 노드로, 올라가면 부모 노드로 이동하는 구조야.

🌳 3. 트리의 특징

구분	설명
순환 없음	트리는 절대 순환(Cycle)이 존재하면 안 돼.
방향성	항상 한 방향(부모→자식)으로만 연결돼.
부모는 하나	모든 노드는 부모 노드가 최대 1개야. (루트 제외)
재귀적 구조	트리는 각 부분도 트리가 되는 재귀적 특성이 있어.
계층적 구조	루트에서 시작해 잎(리프)까지 이어지는 계층 구조.

🌐 4. 트리의 예시 - 게임 신규 개발실 조직도

R1개발실 (Root)
├── 디자인팀
│   ├── 전투팀
│   ├── 경제팀
│   └── 스토리팀
├── 프로그래밍팀
│   ├── 서버팀
│   ├── 클라이언트팀
│   └── 엔진팀
└── 아트팀
    ├── 배경팀
    └── 캐릭터팀

R1개발실: 최상위 노드, 즉 루트 노드.
디자인팀, 프로그래밍팀, 아트팀: 루트의 자식 노드.
각각 팀 아래에 세부 팀들이 자식 노드로 연결.

📖 5. 트리 용어 정리

용어	설명
부모 노드 (Parent)	자신보다 한 단계 위에 있는 노드
자식 노드 (Child)	자신보다 한 단계 아래 있는 노드
형제 노드 (Sibling)	같은 부모를 가진 노드들
선조 노드 (Ancestor)	해당 노드까지 가는 경로에 있는 모든 부모들
자손 노드 (Descendant)	해당 노드에서 뻗어나가는 모든 자식들
루트 노드 (Root)	트리의 최상단 노드. 부모가 없음
잎 노드 (Leaf)	자식이 없는 노드 (가장 끝단 노드)
깊이 (Depth)	루트부터 해당 노드까지의 간선 수
높이 (Height)	트리에서 가장 깊은 곳까지의 최대 깊이
서브트리 (Subtree)	특정 노드부터 시작되는 작은 트리

🌳 6. 트리의 재귀적 속성

트리는 자기 자신 안에 또 다른 트리를 품고 있는 구조야.
특정 노드를 기준으로 보면, 그 아래 전체는 또 하나의 서브트리가 돼.
이 때문에 트리 관련 알고리즘은 재귀적 접근이 자주 쓰여.

✅ 트리와 그래프의 관계

구분	트리	그래프
방향성	부모 → 자식 (단방향)	양방향 가능
순환	❌ 없음	⭕ 가능
부모 수	부모는 1개 (루트 제외)	부모 개수 제한 없음
구조	계층적	비계층적 가능

📊 트리의 구조적 특성 정리

속성	설명
노드 수(N)	트리에 있는 모든 노드 수
간선 수(E)	항상 `N-1`개 (사이클이 없으므로)
루트 노드	부모가 없는 유일한 노드
잎 노드	자식이 없는 노드
높이	루트에서 가장 깊은 노드까지의 거리

🌟 트리 기본 개념 요점 정리

개념	설명
계층적 자료구조	부모-자식 관계로 구성
순환 없음	사이클 존재 불가
한 방향 연결	부모 → 자식 방향성
부모는 1개	루트 제외하고 각 노드는 부모 1개
재귀적 특성	부분도 트리로 구성
주요 용어	부모, 자식, 형제, 선조, 자손, 루트, 잎, 깊이, 높이