트리(Tree)란?
트리 자료구조를 이해하는 것은 자료구조 전반과 알고리즘(특히 탐색, 재귀) 공부에서 중요하다. 트리의 정의부터 살펴보자면 계층적 구조(hierarchical structure)를 표현하는 비선형 자료구조다. 선형 구조는 데이터가 순차적으로 나열되어 1:1로 연결되는 구조를 말하고 비선형 구조는 데이터가 일렬로 나열되지 않고 다대다로 연결되는 구조를 뜻한다.
예를 들어 회사 조직도, 폴더 구조, 가계도 등이 트리 구조의 형태를 띤다.
cf) 선형 자료구조 : 스택, 큐
기본 용어
| 용어 | 설명 |
| 노드(Node) | 데이터가 저장되는 하나의 단위 (예: 폴더, 사람, 값 등) |
| 루트(Root) | 트리의 가장 위에 있는 노드 (시작점) |
| 간선(Edge) | 노드와 노드를 연결하는 선 |
| 부모(Parent) | 아래에 자식 노드를 가지는 노드 |
| 자식(Child) | 부모 노드 아래에 연결된 노드 |
| 형제(Sibling) | 같은 부모를 공유하는 노드 |
| 리프(Leaf) | 자식이 없는 노드 |
| 서브트리(Subtree) | 어떤 노드를 루트로 하는 하위 트리 |
| 레벨(Level) | 루트로부터의 거리 (간선 수) |
| 차수(Degree) | 노드가 가지고 있는 자식 노드의 갯수 |
트리 구조 예시
트리의 특징
1. 사이클이 없음 ➡️순환구조 불가
2. N개의 노드가 있으면 항상 N-1개의 간선이 있음
3. 루트에서 리프까지 단 하나의 경로만 존재
트리의 종류
| 종류 | 설명 |
| 이진 트리(Binary Tree) | 각 노드가 최대 2개의 자식을 가짐 (왼쪽, 오른쪽) |
| 완전 이진 트리 | 마지막 레벨을 제외한 모든 레벨이 꽉 차 있음 |
| 포화 이진 트리 | 모든 노드가 0개 또는 2개의 자식을 가짐 |
| 이진 탐색 트리 (BST) | 왼쪽 < 부모 < 오른쪽 규칙을 따름 |
| 균형 트리 (AVL, Red-Black Tree 등) | 한쪽으로 치우치지 않도록 높이 균형 유지 |
| 힙 (Heap) | 부모 ≥ 자식(최대 힙) or 부모 ≤ 자식(최소 힙) |
| 트라이 (Trie) | 문자열 저장용 트리 (예: 자동완성) |
이진 트리(Binary Tree)
1) 개념
각 노드가 최대 2개의 자식(left, right) 갖는 트리를 의미한다. 이진 트리의 서브 트리는 공집합일 수 있다. 즉, 0~2개의 자식 노드가 존재할 수 있고, 모든 노드의 차수는 2 이하이다. 이진 트리에는 서브 트리간의 순서가 존재해 왼쪽 서브 트리와 오른쪽 서브 트리는 구별된다.
2) 일반 트리와 비교
| 이진 트리 | 일반 트리 | |
| 자식 노드의 개수 | 2개 이하 | 무관 |
| 노드의 개수 | 하나도 갖지 않을 수 있음 | 1개 이상 |
| 서브 트리 간 순서 | 존재 | 존재 X |
3) 구현 예시
class Node {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
class BinaryTree {
constructor() {
this.root = null;
}
insert(value) {
const newNode = new Node(value);
if (!this.root) {
this.root = newNode;
return;
}
// BFS로 비어 있는 자리 찾기 (단순 삽입)
const queue = [this.root];
while (queue.length) {
const node = queue.shift();
if (!node.left) {
node.left = newNode;
return;
} else if (!node.right) {
node.right = newNode;
return;
} else {
queue.push(node.left, node.right);
}
}
}
preorder(node = this.root) {
if (!node) return;
console.log(node.value);
this.preorder(node.left);
this.preorder(node.right);
}
}
// 사용 예시
const tree = new BinaryTree();
tree.insert(1);
tree.insert(2);
tree.insert(3);
tree.insert(4);
tree.preorder(); // 1 2 4 3완전 이진 트리(Complete Binary Tree)
1) 개념
마지막 레벨을 제외하고 모두 채워져 있는 트리 구조.
2) 특징
- 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있다.
- 이때, 마지막 레벨은 완전히 차 있지 않아도 되지만, 노드가 '왼쪽에서 -> 오른쪽으로' 먼저 채워져야 한다.
- 힙(Heap)의 기반 구조
- 완전 이진 트리는, 배열을 사용해 표현 가능하다.
3) 구현 예시
class CompleteBinaryTree {
constructor() {
this.tree = [];
}
insert(value) {
this.tree.push(value);
}
getParent(index) {
return this.tree[Math.floor((index - 1) / 2)];
}
print() {
console.log(this.tree);
}
}
const cbt = new CompleteBinaryTree();
cbt.insert(1);
cbt.insert(2);
cbt.insert(3);
cbt.insert(4);
cbt.insert(5);
cbt.print(); // [1,2,3,4,5]포화 이진 트리(Full Binary Tree)
1) 개념
각 레벨에 노드가 꽉 차 있는 이진 트리로, 각 노드에 레벨 단위로 왼쪽에서 오른쪽으로 번호를 붙일 수 있다. 부여된 번호는 항상 일정하다.
2) 특징
- 포화 이진 트리는 모든 레벨이 노드로 가득 차 있는 트리이다.
- 모든 말단 노드가 '동일한 깊이 or 레벨'을 갖는다.
- 트리의 노드 개수 = [2^k-1 개] 이며, 이때 k 는 트리의 높이이다.
이진 탐색 트리 (Binary Search Tree, BST)
1) 개념
왼쪽 < 부모 < 오른쪽 규칙을 따름
2) 특징
- 왼쪽 < 루트 < 오른쪽
- 탐색, 삽입, 삭제가 효율적 (평균 O(log n))
3) 구현예시
class BSTNode {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
class BST {
constructor() {
this.root = null;
}
insert(value) {
const newNode = new BSTNode(value);
if (!this.root) return (this.root = newNode);
let current = this.root;
while (true) {
if (value < current.value) {
// 현재 값이 부모와 비교해서 작은 값이면 왼쪽에 넣기
if (!current.left) return (current.left = newNode);
current = current.left;
} else {
// 현재 값이 부모와 비교해서 큰 값이면 오른쪽에 넣기
if (!current.right) return (current.right = newNode);
current = current.right;
}
}
}
search(value) {
let current = this.root;
while (current) {
if (value === current.value) return true;
current = value < current.value ? current.left : current.right;
}
return false;
}
}
// 사용 예시
const bst = new BST();
bst.insert(10);
bst.insert(5);
bst.insert(15);
// 10
// / \
// 5 10
console.log(bst.search(5)); // true
console.log(bst.search(7)); // false
트라이 (Trie, Prefix Tree)
1) 개념
문자열 저장용 트리 (예: 자동완성)
2) 특징
- 문자열 검색/자동완성에 특화된 트리
- 각 노드가 문자 하나씩을 가짐
3) 구현예시
class TrieNode {
constructor() {
this.children = {};
this.isEndOfWord = false;
}
}
class Trie {
constructor() {
this.root = new TrieNode();
}
// 단어를 사전에 넣기
insert(word) {
let node = this.root;
for (let ch of word) {
if (!node.children[ch]) node.children[ch] = new TrieNode();
node = node.children[ch]; // isEndOfWord 찍어주기 위해
}
node.isEndOfWord = true;
}
// 사전에 단어 있는지 검색
search(word) {
let node = this.root;
for (let ch of word) {
if (!node.children[ch]) return false;
node = node.children[ch];
}
return node.isEndOfWord;
}
// 사전에 해당 단어로 시작하는 말 있는지 검색
startsWith(prefix) {
let node = this.root;
for (let ch of prefix) {
if (!node.children[ch]) return false;
node = node.children[ch];
}
return true;
}
}
// 사용 예시
const trie = new Trie();
trie.insert("cat");
trie.insert("car");
console.log(trie.search("car")); // true → "car"가 완전히 있음
console.log(trie.startsWith("ca")); // true → "ca"로 시작하는 단어 있음
console.log(trie.search("cap")); // false → "cap"은 없음
균형 이진 트리 (Balanced Binary Tree)
1) 개념
트리의 왼쪽과 오른쪽 서브트리의 높이 차이가 일정 수준 이하로 유지되는 이진 탐색 트리
즉, 한쪽으로 쏠리지 않고 “균형 잡힌” 형태를 유지하는 트리
2) 특징
- 기본 구조 : 이진 탐색 트리 (BST) 기반
- 왼쪽, 오른쪽 서브트리 높이 차 ≤ 1 (혹은 일정 범위)
- 삽입/삭제 시 회전(Rotation)을 통해 균형 복원
- 삽입 / 삭제 / 탐색 모두 O(log n)
- 대표 종류 : AVL 트리, Red-Black 트리, B-Tree, B+Tree 등
트리 순회
트리는 비선형 구조라서 순회(Traversal) 방식이 중요하다.
순회는 많이 알려진 방법인 깊이우선탐색(DFS), 너비우선탐색(BFS) 으로 나눌 수 있다.
깊이우선탐색의 탐색방법에는 3가지가 존재하는데 전위 순회, 중위 순회, 후위 순회가 있다.
너비우선탐색은 레벨 순으로 차례대로 탐색하는 레벨 순회 방식이다.
1. 전위 순회(Preorder)
- 루트 ➡️왼쪽 ➡️ 오른쪽
- 방문순서 : 12 → 2 → 6 → 3 → 8 → 16 → 10 ....
- 구현 코드
// 노드 구조 정의
class Node {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
// 전위 순회 함수 (루트 → 왼쪽 → 오른쪽)
function preorder(node) {
if (!node) return;
console.log(node.value); // ① 루트 방문
preorder(node.left); // ② 왼쪽 자식 탐색
preorder(node.right); // ③ 오른쪽 자식 탐색
}
// 트리 구성 예시
// A
// / \
// B C
// / \ \
// D E F
const root = new Node('A');
root.left = new Node('B');
root.right = new Node('C');
root.left.left = new Node('D');
root.left.right = new Node('E');
root.right.right = new Node('F');
// 전위 순회 실행
preorder(root); // A B D E C F
2. 중위 순회(Inorder)
- 왼쪽 ➡️ 루트 ➡️ 오른쪽
- 방문순서 : 3 → 6 → 8 → 2 → 16 → 12 → 4 → 10 → 7 ...
- 구현 코드
// 노드 구조 정의
class Node {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
// 중위 순회 함수 (왼쪽 → 루트 → 오른쪽)
function inorder(node) {
if (!node) return;
inorder(node.left); // ① 왼쪽 자식 탐색
console.log(node.value); // ② 루트 방문
inorder(node.right); // ③ 오른쪽 자식 탐색
}
// 트리 구성 예시
// A
// / \
// B C
// / \ \
// D E F
const root = new Node('A');
root.left = new Node('B');
root.right = new Node('C');
root.left.left = new Node('D');
root.left.right = new Node('E');
root.right.right = new Node('F');
// 중위 순회 실행
inorder(root); // D B E A C F
3. 후위 순회(Postorder)
- 왼쪽 ➡️ 오른쪽 ➡️ 루트
- 방문순서 : 3 → 8 → 6 → 16 → 2 → 4 → 9 → 1 → 7 → 10 → 12
- 구현 코드
// 노드 구조 정의
class Node {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
// 후위 순회 함수 (왼쪽 → 오른쪽 → 루트)
function postorder(node) {
if (!node) return;
postorder(node.left); // ① 왼쪽 자식 탐색
postorder(node.right); // ② 오른쪽 자식 탐색
console.log(node.value); // ③ 루트 방문
}
// 트리 구성 예시
// A
// / \
// B C
// / \ \
// D E F
const root = new Node('A');
root.left = new Node('B');
root.right = new Node('C');
root.left.left = new Node('D');
root.left.right = new Node('E');
root.right.right = new Node('F');
// 후위 순회 실행
postorder(root); // D E B F C A
4. 레벨 순회(Level Order)
- 위에서 아래로, 왼쪽에서 오른쪽으로 (BFS)
- 큐(Queue)를 이용해서 한 레벨씩 순회
- 방문순서 : 0 → 1 → 2 → 3 → 4 → 5 → 6
- 구현 코드
// 노드 구조 정의
class Node {
constructor(value) {
this.value = value;
this.left = null;
this.right = null;
}
}
// 레벨 순회 함수 (BFS)
function levelOrder(root) {
if (!root) return;
const queue = [root]; // 방문할 노드를 저장하는 큐
while (queue.length > 0) {
const node = queue.shift(); // 큐 맨 앞의 노드 꺼내기
console.log(node.value); // 방문
// 왼쪽, 오른쪽 자식이 있다면 큐에 추가
if (node.left) queue.push(node.left);
if (node.right) queue.push(node.right);
}
}
// 트리 구성 예시
// A
// / \
// B C
// / \ \
// D E F
const root = new Node('A');
root.left = new Node('B');
root.right = new Node('C');
root.left.left = new Node('D');
root.left.right = new Node('E');
root.right.right = new Node('F');
// 레벨 순회 실행
levelOrder(root); // A B C D E F참고
- https://simmigyeong.tistory.com/23
- https://medium.com/quantum-ant/%ED%8A%B8%EB%A6%AC-tree-cec69cfddb14
-
'개발지식 > 자료구조' 카테고리의 다른 글
| [자료구조] 탐욕법(Greedy Algorithm) (0) | 2025.11.25 |
|---|---|
| [자료구조] 그래프(Graph) (0) | 2025.11.17 |
| [자료구조] 탐색(검색) 알고리즘 (Search Algorithm) (0) | 2025.11.04 |
| [자료구조] 정렬 (Sort) - 병합 정렬, 퀵 정렬 (0) | 2025.10.27 |
| [자료구조] 힙(Heap)과 우선순위 큐(Priority Queue) (0) | 2025.10.20 |