728x90
반응형
1. 트리가 왜 필요할까?
지금까지 공부한 List나 Stack은 데이터가 1 → 2 → 3 처럼 한 줄로 연결되어 있다. 하지만 세상에는 한 줄로 표현이 안되는 것들이 존재한다.
- 컴퓨터 폴더 : c 드라이브 안에 Program Files 와 Users 가 있고 그 안에 다양한 폴더들이 존재한다.
- 회사 조직도 : 사장 밑 부사장 밑 부장 A, 부장 B ...
- HTML DOM : <body> 안에 <div> ...
이러한 계층(Hierarchy)을 표현하기 위해 만든 것이 바로 트리(Tree)다.
2. 핵심 용어 정리
트리를 다룰 때 반드시 사용하는 5가지 용어가 존재한다.
- 노드 (Node) : 트리를 구성하는 알맹이 하나하나 (데이터가 담긴 동그라미)
- 루트 (Root) : 트리의 가장 꼭대기. 시작점 (부모가 없는 유일한 노드)
- 리프 (Leaf) : 트리의 가장 밑바닥. (자식이 없는 노드, 말단 노드라고도 한다.)
- 간선 (Edge) : 노드와 노드를 연결하는 선
- 부모 / 자식 (Parent, Child) : 연결된 두 노드 중 위에 있는 것이 부모, 아래가 자식.
- 깊이 (Depth) : 루트에서 얼마나 멀리 떨어져 있는 가? (층 수)
3. 구현 방법(Java)
트리를 구현하는 방법은 크게 2가지가 존재한다.
3.1. 노드 클래스 연결하기 (가장 정석적인 방법)
LinkedList의 원리에서 포인터만 늘려놓는 개념이라고 볼 수 있다.
현재는 이진 트리를 구현한 소스코드다.
class Node {
int data; // 내 데이터
Node left; // 왼쪽 자식 주소 (없으면 null)
Node right; // 오른쪽 자식 주소 (없으면 null)
public Node(int data) {
this.data = data;
this.left = null;
this.right = null;
}
}
public class TreeExample {
public static void main(String[] args) {
// 1. 노드 생성
Node root = new Node(1); // 루트
Node leftChild = new Node(2);
Node rightChild = new Node(3);
// 2. 연결 (간선 연결)
root.left = leftChild;
root.right = rightChild;
/*
(1) <- root
/ \
(2) (3)
*/
}
}
3.2. 1차원 배열 사용 (힙 Heap 전용)
트리를 그냥 단순 1차원 배열을 이용하여 구현할 수 있다. 주로 꽉 차 있는 트리(완전 이진 트리)일 때에만 사용할 수 있다.
힙은 이후에 포스팅을 할 예정이다.
- 루트(Root)는 배열의 1번 인덱스에 넣는다.
- 부모가 i번이면 왼쪽은 i * 2 , 오른쪽은 i * 2 + 1로 구현한다.
int[] tree = new int[10];
tree[1] = 10; // Root
tree[2] = 5; // Root의 왼쪽 자식 (1 * 2)
tree[3] = 8; // Root의 오른쪽 자식 (1 * 2 + 1)- 장점 : 구현이 엄청 빠르고 간단하다.
- 단점 : 트리가 듬성듬성 비어있으면 메모리 낭비가 심하다.
4. 이진 트리(Binary Tree)란?
자식이 최대 2개인 트리를 이진 트리라고 한다.
- 컴퓨터는 0과 1을 좋아하기때문에 데이터 탐색을 할 때에도 반씩 잘라서 찾기(O(log N)) 가장 좋은 구조이기 때문에 이진 트리를 많이 사용한다.
- 앞으로 학습할 BST(이진 탐색 트리), Heap(힙), Red-Black Tree 가 모두 이진 트리의 변형이다.
728x90
반응형
'Coding Test > 자료구조' 카테고리의 다른 글
| 7. 우선순위 큐(Priority Queue) & 힙(Heap) (0) | 2026.02.10 |
|---|---|
| 6. 트리 순회(Traversal) (0) | 2026.02.09 |
| 4. 해시 (Hash) (0) | 2026.02.07 |
| 3. 스택(Stack) & 큐(Queue) & 덱(Deque) (1) | 2026.02.06 |
| 2. 리스트(List) (0) | 2026.02.06 |
