8. 트리

 

💡 1분 핵심 요약 (TL;DR)

• ✅ 트리(Tree) — 계층적 자료를 표현하는 비순환 연결 자료구조. 루트를 중심으로 노드들이 뻗어나가는 형태
• ✅ 핵심 용어 — 루트 / 단말 노드(리프) / 차수(degree) / 레벨 / 높이(height)
• ✅ 이진 트리 — 모든 노드의 차수가 2 이하. 왼쪽·오른쪽 자식을 반드시 구별
• ✅ 이진 트리 3종류 — 포화(꽉 참) / 완전(왼쪽부터 순서대로) / 편향(한쪽만)
• ✅ 구현 방법 2가지 — 배열(인덱스 계산) vs 연결리스트(포인터 연결)

 

 

 

01 트리(Tree)란?

계층 구조를 표현하는 비선형·비순환 자료구조

 

트리(Tree)는 나무의 뿌리에서 가지가 뻗어나가는 모양처럼, 루트(root)라는 특별한 노드를 중심으로 하나 이상의 노드들이 계층적으로 연결된 자료구조입니다. 선형 자료구조(배열, 연결리스트)와 달리 비선형·비순환 구조이며, 회사 조직도나 컴퓨터 폴더 구조처럼 현실 세계의 계층 관계를 그대로 표현할 수 있습니다.

 

📖 트리의 응용 분야
· 폴더 구조 — 운영체제의 파일 시스템이 전형적인 트리 계층 구조
· 결정 트리(Decision Tree) — AI·머신러닝에서 의사결정 구조 표현에 활용
· 인공지능 게임 — 바둑·체스 AI의 수 계산에 거대한 결정 트리 사용
· 데이터베이스 인덱스 — B-트리, B+트리 등으로 빠른 검색 구현

 

 

02 트리 핵심 용어 총정리

시험에 꼭 나오는 용어 7가지 한눈에 정리

 

용어	정의	예시 (아래 트리 기준)
루트 노드 (Root)	계층에서 가장 높은 곳의 노드. 부모가 없음	노드 A
단말 노드 (Leaf Node)	자식 노드가 없는 노드. 차수 = 0	E, F, G, H, I, J
간선 (Edge)	노드와 노드를 연결하는 선. n개 노드 → n-1개 간선	A-B, A-C, B-E … 등
차수 (Degree)	한 노드가 가진 자식 노드의 수. 트리의 차수 = 노드 차수 중 최댓값	A의 차수 = 3 트리의 차수 = 3
레벨 (Level)	루트 = 레벨 1. 한 층 내려갈수록 +1 증가	A: 레벨1, B·C·D: 레벨2
높이 (Height)	트리가 가진 최대 레벨 값	높이 = 3
포리스트 (Forest)	트리들의 집합. 나무가 모이면 숲이 되듯	루트 제거 → 서브트리들의 집합

 

✓ 노드 관계 용어 빠른 정리
· 부모 노드 : 나를 자식으로 두는 바로 위 노드 (A는 B의 부모)
· 자식 노드 : 내가 연결하고 있는 아래 노드 (B는 A의 자식)
· 형제 노드 : 같은 부모를 가진 노드들 (B, C, D는 형제)
· 조상 노드 : 나에서 루트까지 경로상의 모든 노드
· 자손 노드 : 나의 서브트리에 속하는 모든 노드

 

 

 

03 이진 트리(Binary Tree) 완전 정리

자식이 최대 2개 — 왼쪽과 오른쪽은 반드시 구별

 

이진 트리(Binary Tree)는 모든 노드의 차수가 2 이하인 트리입니다. 자식이 없거나, 하나이거나, 최대 두 개까지만 가질 수 있으며, 왼쪽 자식과 오른쪽 자식은 위치가 다르므로 반드시 구별해야 합니다. 이진 트리의 서브트리도 반드시 이진 트리여야 합니다.

 

📐 이진 트리의 수학적 성질
· n개의 노드를 가진 이진 트리는 n-1개의 간선을 가짐
   → 루트를 제외한 모든 노드는 부모가 정확히 하나이기 때문
· 높이가 h인 이진 트리의 노드 수 : 최소 h개 ~ 최대 2ʰ-1개
   → 최소: 각 레벨에 노드 1개씩(편향 트리) / 최대: 모든 자리가 꽉 찬 경우(포화 트리)

 

이진 트리 3가지 종류 비교

종류	정의	핵심 포인트
포화 이진 트리 (Full Binary Tree)	각 레벨에 노드가 꽉 차있는 트리. 높이 k → 노드 수 = 2ᵏ - 1	노드 번호는 레벨 단위 좌→우 순서. 루트 오른쪽 자식 번호는 항상 3
완전 이진 트리 (Complete Binary Tree)	마지막 레벨을 제외한 모든 레벨이 꽉 차 있고, 마지막 레벨은 왼쪽부터 순서대로 채워진 트리	마지막 레벨에 빈곳이 있어도 되나 중간에 빈곳은 안 됨. 포화 ⊂ 완전 (역은 성립 ✗)
편향 이진 트리 (Skewed Binary Tree)	왼쪽 또는 오른쪽 서브트리만 계속 가지는 트리	노드가 n개일 때 높이 = n. 탐색 효율 최악 (연결리스트와 동일)

 

⚠️ 자주 틀리는 포인트 — 포화 vs 완전
· 포화 이진 트리는 항상 완전 이진 트리입니다 (포화 ⊂ 완전)
· 그러나 완전 이진 트리가 항상 포화 이진 트리는 아닙니다 (마지막 레벨이 덜 찰 수 있음)
· 시험에서 "포화이진트리는 완전이진트리다 → O / 완전이진트리는 포화이진트리다 → X"

 

 

04 이진 트리 구현 — 배열 vs 연결리스트

두 방법의 차이와 각각의 인덱스 계산 규칙

 

배열 표현법 · 노드에 번호를 붙여 그 번호를 배열 인덱스로 사용 · 포화/완전 이진 트리에 가장 적합 · ⚠️ 루트 노드의 인덱스를 1로 가정 (1-based)    → C 배열은 기본이 0-based이므로 arr[0]은 사용하지 않음 · 인덱스 i인 노드 기준:   - 왼쪽 자식: 2i   - 오른쪽 자식: 2i+1   - 부모: i÷2 (정수 나눗셈) · 단점: 편향 트리에서 메모리 낭비 심각

연결리스트 표현법 · 각 노드가 데이터 + 왼쪽 포인터 + 오른쪽 포인터를 가짐 · 리프 노드의 포인터 영역 → null · 편향 트리도 메모리 낭비 없이 구현 가능 · 노드 삽입·삭제 시 포인터 주소만 변경 → 배열보다 효율적 · 단점: 포인터 저장 공간 추가 필요

 

배열 인덱스 계산 예시

 

배열 표현법 — 인덱스 계산 규칙 (1-based, 루트 인덱스 = 1)

/* 노드 번호(인덱스)가 i 일 때 */
/* ※ 루트 = 1 (1-based). C 배열은 0-based이므로 arr[0]은 비워둠 */

왼쪽 자식 = 2 * i;
오른쪽 자식 = 2 * i + 1;
부모 노드   = i / 2;          /* 정수 나눗셈 */

/* 예시: 인덱스 3번 노드 */
왼쪽 자식 = 3 * 2   = 6번
오른쪽 자식 = 3 * 2 + 1 = 7번
부모 노드 = 3 / 2   = 1번 (루트)

 

연결리스트 노드 구조

 

✅ 연결리스트 노드 구조 (C 스타일)

typedef struct TreeNode {
    int data;                        // 데이터 필드
    struct TreeNode *left;        // 왼쪽 자식 포인터
    struct TreeNode *right;      // 오른쪽 자식 포인터 (리프면 NULL)
} TreeNode;

 

✓ 언제 어떤 방법을 쓸까?
· 배열 → 포화·완전 이진 트리처럼 구조가 고정되고 삽입·삭제가 적을 때
· 연결리스트 → 삽입·삭제가 자주 발생하거나 편향 트리처럼 빈 공간이 많을 때
· 실무에서는 대부분 연결리스트 방식을 사용

 

 

📌 핵심 정리

· 트리 : 루트를 중심으로 노드들이 계층적으로 연결된 비선형·비순환 자료구조
· 간선 수 : n개 노드 → n-1개 간선 (루트 제외한 모든 노드에 부모-자식 간선 1개)
· 차수(degree) : 노드가 가진 자식 수. 트리의 차수 = 전체 노드 중 최대 차수
· 레벨 : 루트=1, 한 층 내려갈수록 +1. 높이 = 최대 레벨
· 이진 트리 : 모든 노드 차수 ≤ 2. 왼쪽·오른쪽 자식 위치 구별 필수
· 포화 이진 트리 : 높이 k → 노드 수 = 2ᵏ-1. 포화 ⊂ 완전 (역은 성립 ✗)
· 완전 이진 트리 : 마지막 레벨 왼쪽부터 순서대로 채워짐. 중간 빈곳 불가
· 편향 이진 트리 : 한쪽 서브트리만 가짐. 탐색 효율 최악
· 배열 구현 : 인덱스 i → 왼쪽 자식 2i, 오른쪽 자식 2i+1, 부모 i÷2
· 연결리스트 구현 : 데이터 + 왼쪽/오른쪽 포인터. 삽입·삭제에 효율적

 

 

태그 : 트리 자료구조란이진트리란포화이진트리 완전이진트리 차이트리 노드 차수 레벨 높이이진트리 배열 구현이진트리 연결리스트 구현편향이진트리란트리 단말노드 리프노드자료구조 트리 종류 정리이진트리 인덱스 계산법