도입
배열이나 연결 리스트가 순서 중심 구조라면, 트리 구조는 관계 중심 구조에 가깝습니다. 어떤 데이터가 다른 데이터의 하위에 속하는지, 어떤 범위가 어떤 하위 범위들로 나뉘는지처럼 계층적 관계를 표현하는 데 강합니다.
그래서 트리는 단순히 노드를 많이 연결한 그림이 아니라, 탐색 순서와 부모-자식 관계, 서브트리 단위의 분해가 중요한 구조입니다. 검색, 우선순위 관리, 문자열 접두어 탐색, 외부 메모리 인덱싱처럼 성격이 다른 문제들이 모두 트리 계열 자료구조로 풀리는 이유도 여기에 있습니다.
즉 트리 구조를 이해한다는 것은 단순히 루트와 리프라는 용어를 아는 일이 아니라, 데이터를 계층형으로 모델링하고 그 위에서 탐색과 분할을 수행하는 관점을 이해하는 일에 가깝습니다.
필요성
트리가 중요한 이유는 단순히 교과서에서 많이 나오기 때문이 아닙니다. 실제 문제를 보면 데이터가 평평한 표 형태보다 계층 구조를 띠는 경우가 많고, 특정 범위만 빠르게 찾아야 하거나, 하위 구조 단위로 같은 연산을 반복해야 하는 경우도 자주 생깁니다.
이때 트리 구조는 서브트리라는 단위를 통해 큰 문제를 작은 문제로 나누고, 루트에서 시작해 필요한 가지로만 내려가는 방식으로 탐색 범위를 줄여 줍니다. 검색 트리, 힙, 트라이, B-트리가 서로 다른 문제를 다루면서도 모두 트리라는 공통 형식을 갖는 이유가 바로 이것입니다.
즉 트리는 하나의 자료구조 이름이라기보다, 계층과 분기와 재귀를 이용해 문제를 다루는 방식 전체에 더 가깝습니다.
- 데이터가 부모-자식 형태의 계층을 이룰 때
- 검색 범위를 단계적으로 줄이며 탐색해야 할 때
- 우선순위나 접두어처럼 특정 규칙을 구조 자체에 반영하고 싶을 때
- 큰 문제를 서브트리 단위로 재귀적으로 처리해야 할 때
정의
NIST 기준으로 트리는 루트에서 시작해 접근하는 자료구조로 설명됩니다. 각 노드는 leaf이거나 internal node이고, internal node는 하나 이상의 child를 가지며 그 child들의 parent가 됩니다. 같은 parent를 공유하는 노드들은 siblings입니다.
흥미로운 점은 자료구조 sense의 tree와 그래프 이론의 tree가 완전히 같은 개념은 아니라는 것입니다. 자료구조 쪽 트리는 보통 rooted이고 ordered이기 때문에, 같은 노드 수라도 왼쪽 자식이냐 오른쪽 자식이냐 같은 차이가 구조적으로 의미를 가질 수 있습니다.
즉 실무에서 말하는 트리 구조는 단순한 무순서 무사이클 그래프보다 더 강한 의미를 가진 경우가 많습니다. 루트, 자식 순서, 서브트리 경계가 실제 연산 의미에 직접 영향을 주기 때문입니다.
"트리 구조의 본질은 노드 수가 아니라
루트에서 시작해 서브트리 단위로 문제를 나누고 탐색하는 방식에 있습니다."
핵심 원리
트리는 재귀적 구조입니다. 루트 아래에는 여러 서브트리가 있고, 각 서브트리 역시 다시 같은 성격의 트리로 볼 수 있습니다. 그래서 크기 계산, 높이 계산, 순회, 검색처럼 많은 연산이 재귀적으로 정의됩니다.
또 트리의 성능을 이해할 때는 전체 노드 수뿐 아니라 높이(height)가 중요합니다. 특히 루트에서 리프까지의 경로가 길어질수록 탐색, 삽입, 삭제, 재귀 순회에서 실제 비용이 커지기 쉽습니다.
그래서 같은 트리 계열이라도 어떤 구조는 균형을 유지해 높이를 억제하고, 어떤 구조는 완전성(complete-ness)을 이용해 배열 표현을 쓰고, 어떤 구조는 문자열 접두어 규칙을 트리 모양에 직접 녹여 넣습니다.
즉 트리의 본질은 계층형 저장 그 자체보다, 서브트리와 높이를 이용해 연산 의미를 구조에 반영하는 데 있습니다.
Tree Thinking
1) 루트에서 시작한다
2) 현재 노드와 자식 관계를 본다
3) 필요한 서브트리로만 내려간다
4) 서브트리도 다시 같은 문제로 본다
5) 높이와 순회 순서가 실제 성능과 의미를 좌우한다핵심 용어
| 용어 | 의미 | 실무 해석 |
|---|---|---|
| Root | 트리의 시작 노드 | 대부분의 탐색과 연산이 여기서 출발 |
| Node | 트리를 이루는 기본 단위 | 값과 자식 포인터 또는 참조를 가진다 |
| Parent / Child | 부모-자식 관계 | 계층 구조와 이동 방향을 정의 |
| Sibling | 같은 부모를 가진 노드들 | 같은 레벨의 형제 노드 |
| Leaf | 자식이 없는 노드 | 말단 데이터 또는 종료 지점 역할 |
| Depth | 루트에서 해당 노드까지의 경로 길이 | 현재 노드가 몇 단계 아래에 있는지 |
| Height | 해당 노드에서 가장 먼 자손까지의 경로 길이 | 탐색/재귀 비용과 균형 정도를 읽는 기준 |
| Ancestor / Descendant | 조상 / 자손 관계 | 경로 상 포함 관계를 나타냄 |
| Subtree | 특정 노드를 루트로 하는 부분 트리 | 재귀와 분할 정복의 기본 단위 |
특히 depth와 height는 자주 헷갈립니다. depth는 위에서 아래로 내려온 거리이고, height는 현재 노드 아래에 얼마나 긴 경로가 남아 있는지를 말합니다. 트리 전체의 height는 루트의 height입니다.
순회
| 순회 방식 | 방문 순서 | 실무 해석 |
|---|---|---|
| Preorder | 루트 → 서브트리들 | 현재 노드를 먼저 처리해야 할 때 적합 |
| Inorder | 왼쪽 서브트리 → 루트 → 오른쪽 서브트리 | 이진 검색 트리에서 정렬 순 출력과 잘 맞음 |
| Postorder | 서브트리들 → 루트 | 자식 처리가 끝난 뒤 부모를 처리할 때 적합 |
| Level-order | 깊이 순서대로, 루트부터 레벨별 방문 | 너비 우선 탐색과 같고 큐 기반 구현이 자연스러움 |
전위·중위·후위는 깊이 우선 성격을 띠고, 레벨 순회는 루트에서부터 깊이별로 내려가는 너비 우선 성격을 가집니다. 특히 중위 순회는 왼쪽/루트/오른쪽이 분명한 이진 트리 맥락에서 가장 자연스럽습니다.
Traversal Overview
Preorder : root -> subtree
Inorder : left -> root -> right
Postorder : subtree -> root
Level-order: level by level from root기본 구조
가장 기본적인 방법은 각 노드가 부모나 자식에 대한 참조를 직접 갖는 포인터 기반 표현입니다. 일반 트리나 이진 트리는 이 방식이 가장 직관적이고, 서브트리 단위 연산과 재귀 구현이 쉽습니다.
반면 완전 이진 트리 계열에서는 배열 표현이 매우 강력합니다. Open Data Structures가 설명하듯, 노드를 breadth-first 순서로 배열에 두면 루트는 0번, 왼쪽 자식은 2i+1, 오른쪽 자식은 2i+2, 부모는 (i-1)/2 로 계산할 수 있습니다.
이 방식은 heap처럼 완전성 제약이 있는 구조에서는 포인터를 따로 저장하지 않아도 되기 때문에 매우 효율적입니다. 하지만 모양이 자유로운 일반 트리에는 잘 맞지 않습니다.
binary-tree/
├── pointer based
│ ├── value
│ ├── parent
│ ├── left
│ └── right
└── array based (complete binary tree)
├── root index = 0
├── left(i) = 2i + 1
├── right(i) = 2i + 2
└── parent(i) = (i - 1) / 2기본 구현
class Node<T> {
T value;
Node<T> left;
Node<T> right;
Node<T> parent;
Node(T value) {
this.value = value;
}
}
public void preorder(Node<Integer> node) {
if (node == null) return;
System.out.println(node.value); // root
preorder(node.left); // left subtree
preorder(node.right); // right subtree
}패턴 1. 이진 트리와 균형 트리
이진 트리는 각 노드가 최대 두 자식을 가지는 트리입니다. 왼쪽과 오른쪽이 구분되기 때문에 중위 순회, BST, heap 같은 중요한 구조의 기반이 됩니다.
문제는 이진 트리라고 해서 항상 효율적인 것은 아니라는 점입니다. 한쪽으로 길게 치우친 트리는 사실상 연결 리스트처럼 동작할 수 있습니다. 그래서 균형 트리는 리프들이 루트에서 너무 멀리 차이나지 않도록 제약을 둡니다.
대표적으로 AVL 트리는 각 노드의 두 서브트리 높이 차이가 최대 1이 되도록 유지하는 balanced binary search tree이고, NIST 기준으로 조회·삽입·삭제가 O(log n) 입니다.
Binary Tree
- 각 노드의 자식 수가 최대 2개
Balanced Binary Tree
- 리프들이 루트에서 지나치게 멀어지지 않도록 제약
- 필요하면 rotation 으로 재균형패턴 2. 이진 검색 트리(BST)
이진 검색 트리는 각 노드의 왼쪽 서브트리 키가 현재 노드보다 작고, 오른쪽 서브트리 키가 더 크다는 규칙을 유지합니다. 이 규칙 덕분에 루트에서 비교를 반복하며 필요한 방향으로만 내려가 검색 범위를 줄일 수 있습니다.
또 BST에서는 중위 순회가 자연스럽게 정렬 순 출력을 만들어 냅니다. 그래서 정렬된 순회와 검색을 동시에 지원해야 하는 문제에서 매우 자주 등장합니다.
다만 BST의 실제 성능은 높이에 크게 좌우됩니다. 불변식만 지켜도 지나치게 치우친 트리가 될 수 있기 때문에, 실무에서는 AVL이나 red-black tree 같은 balanced BST가 더 자주 쓰입니다.
패턴 3. 힙, 트라이, B-트리
| 구조 | 핵심 규칙 | 실무 해석 |
|---|---|---|
| Heap | complete tree + 부모가 더 extreme 한 key | priority queue, heap sort 의 기반 |
| Trie | 공통 prefix 마다 노드를 둠 | 문자열/접두어 검색에 적합 |
| B-tree | 여러 자식을 갖는 balanced search tree | 디스크/외부 메모리 인덱스에 적합 |
힙은 complete tree 위에 heap property를 얹은 구조입니다. 부모 키가 자식보다 더 크거나 더 작은 방향으로 정렬되어 있기 때문에, 루트에서 최소값 또는 최대값을 빠르게 얻는 priority queue와 잘 맞습니다.
트라이는 문자열 저장을 위해 공통 접두어마다 노드를 두는 트리입니다. 그래서 일반 비교 기반 검색과 달리, 문자열 길이와 접두어 공유 구조를 직접 활용할 수 있습니다.
B-트리는 한 노드가 여러 자식을 갖는 balanced search tree이며, NIST는 느린 메모리(예: 디스크)에서 높이와 접근 횟수를 작게 유지하는 데 좋은 구조라고 설명합니다. 그래서 데이터베이스 인덱스나 파일 시스템 인덱스 문맥에서 자주 등장합니다.
한계와 주의점
첫째, 트리는 높이에 민감합니다. 같은 노드 수라도 편향된 트리는 탐색 경로가 길어지고, 재귀 깊이도 함께 커집니다. 따라서 균형 유지가 필요한지, 편향이 허용되는 문제인지 먼저 판단해야 합니다.
둘째, 트리 종류마다 불변식이 다르기 때문에 서로 바꿔 생각하면 안 됩니다. BST는 정렬 검색에 강하지만 최소/최대 우선순위 추출만을 위해 존재하는 구조가 아니고, heap은 priority queue에 강하지만 전체 정렬 순 검색과는 잘 맞지 않습니다.
셋째, 포인터 기반 트리는 구현과 디버깅 난이도가 생각보다 높습니다. 부모/자식 연결이 잘못되면 서브트리 전체가 깨질 수 있고, 회전이나 삭제 연산은 특히 실수가 많습니다.
- 높이가 커지면 탐색과 재귀 비용이 함께 커질 수 있음
- BST, heap, trie, B-tree 는 모두 트리지만 불변식과 목적이 다름
- 삭제, 회전, 병합 같은 연산은 포인터 연결 실수가 잦음
- 완전 이진 트리가 아니라면 배열 표현이 항상 좋은 선택은 아님
자주 하는 실수
- 트리와 그래프 이론의 tree 를 완전히 같은 의미로 생각함
- BST 와 heap 을 비슷한 검색 트리로 착각함
- 중위 순회가 모든 트리에서 자연스럽게 정의된다고 생각함
- 트리 성능을 노드 수만 보고 판단하고 height 를 놓침
- 완전 이진 트리가 아닌데도 배열 표현을 무리하게 적용함
- 삭제 연산 후 부모/자식 링크 갱신을 빠뜨려 구조를 망가뜨림
실무 루틴
- 먼저 데이터가 정말 계층형 인지, 아니면 단순 순차 구조면 충분한지 판단한다.
- 트리에 넣을 불변식 이 무엇인지 정한다. 예를 들어 정렬, 우선순위, 접두어, 완전성 같은 규칙이다.
- 검색/삽입/삭제 성능이 height 에 얼마나 민감한지 본다.
- 포인터 기반 표현이 맞는지, complete binary tree 라면 배열 표현 이 더 나은지 검토한다.
- 순회 방식은 문제 목적에 맞춰 정한다. 정렬 출력이면 중위, 부모 우선이면 전위, 자식 후처리면 후위, 레벨별 처리면 BFS가 자연스럽다.
- 불균형이 걱정되면 BST 대신 balanced tree 계열을 먼저 고려한다.
디버깅
2i+1, 2i+2, (i-1)/2 가 깨지지 않는지 확인한다.점검 체크리스트
- 이 트리의 불변식은 무엇인가
- 루트와 부모/자식 링크가 올바른가
- 순회 결과가 기대한 의미와 맞는가
- height 가 비정상적으로 커지지 않았는가
- 배열 기반이라면 parent/child index 계산이 맞는가요약
- ✅ 트리 구조는 루트와 부모-자식 관계를 기준으로 데이터를 계층적으로 다루는 자료구조다.
- ✅ 자료구조 관점의 tree는 보통 rooted 이고 ordered 하게 다뤄진다.
- ✅ depth, height, subtree, ancestor, descendant 같은 용어를 구분해야 구조를 정확히 읽을 수 있다.
- ✅ 전위·중위·후위·레벨 순회는 각각 방문 의미가 다르다.
- ✅ 이진 트리는 가장 기본적인 형태이고, balanced tree는 높이 편향을 줄이기 위한 제약을 가진다.
- ✅ BST는 정렬 불변식, heap은 우선순위 불변식, trie는 prefix 불변식, B-tree는 외부 메모리 친화성을 구조에 반영한다.
- ✅ 트리 성능은 노드 수뿐 아니라 height 에 크게 좌우된다.
- ✅ 좋은 트리 설계는 자료형 이름보다도 불변식과 표현 방식이 문제에 맞는지부터 확인한다.