트리(Tree)
트리(Tree)란 무엇인가
트리는 데이터를 계층 구조로 표현하기 위한 자료구조다. 앞에서 다룬 배열, 스택, 큐는 모두 한 줄로 이어진 선형 구조였지만, 트리는 위아래 관계가 존재하는 비선형 구조다. 현실 세계에서 가장 쉽게 떠올릴 수 있는 예시는 컴퓨터의 폴더 구조다. 하나의 최상위 폴더 아래에 여러 폴더가 있고, 그 아래로 또 다른 폴더들이 이어진다. 이런 구조를 표현하기에 트리는 매우 적합하다.
선형 구조가 “순서대로 저장하고 꺼내는 것”에 초점이 맞춰져 있다면, 트리는 “관계와 구조를 표현하는 것”에 초점이 맞춰진 자료구조라고 이해하면 된다.
트리의 기본 용어
트리는 몇 가지 기본 용어를 함께 이해해야 구조가 보인다. 트리를 구성하는 각각의 데이터 하나를 노드(Node) 라고 부른다. 트리의 가장 위에 있는 노드는 루트 노드(Root Node) 다. 루트 노드를 기준으로 아래로 내려갈수록 단계가 깊어지는데, 이 단계를 레벨(Level) 이라고 한다.
어떤 노드의 바로 위에 연결된 노드는 부모 노드, 아래에 연결된 노드는 자식 노드다. 자식 노드가 하나도 없는 노드는 리프 노드(Leaf Node) 라고 부른다. 같은 부모를 가진 노드들은 형제 노드(Sibling) 관계다. 이런 용어들은 트리를 설명할 때 거의 항상 등장한다.
이진 트리(Binary Tree)
이진 트리는 트리 중에서도 가장 기본적인 형태다. 이진 트리의 핵심 규칙은 단 하나다. 각 노드는 최대 두 개의 자식만 가질 수 있다.
자식이 0개일 수도 있고, 1개 또는 2개일 수도 있지만, 3개 이상은 허용되지 않는다. 구조가 어떻게 생겼든 이 규칙만 지키면 이진 트리다.
o
/ \
o o ← 이진 트리 (O) o
/ | \
o o o ← 이진 트리 (X)완전 이진 트리(Complete Binary Tree)
완전 이진 트리는 이진 트리 중에서도 노드가 채워지는 방식에 규칙이 있는 트리다. 모든 레벨은 왼쪽부터 차례대로 채워져야 하며, 마지막 레벨을 제외한 모든 레벨은 노드가 가득 차 있어야 한다.
o
o o
o o o ← 완전 이진 트리 (O) o
o o
o o ← 완전 이진 트리 (X)이 규칙 덕분에 완전 이진 트리는 배열로 표현할 수 있다는 큰 장점이 있다.
완전 이진 트리를 배열로 표현하기
완전 이진 트리는 레벨 순서대로 노드를 배열에 저장하면 된다. 구현할 때는 계산을 쉽게 하기 위해 보통 0번 인덱스를 비워두고 1번부터 사용한다.
# 트리 구조
# 8
# 6 3
# 4 2 5
tree = [None, 8, 6, 3, 4, 2, 5]이렇게 저장하면 인덱스 계산만으로 부모와 자식 관계를 바로 알 수 있다.
i = 1 # 값 8
left_child = i * 2 # 2 -> 6
right_child = i * 2 + 1 # 3 -> 3
parent = i // 2 # 0 (루트)- 현재 인덱스 × 2 → 왼쪽 자식
- 현재 인덱스 × 2 + 1 → 오른쪽 자식
- 현재 인덱스 // 2 → 부모 노드
이 규칙 덕분에 포인터 없이도 트리 구조를 효율적으로 다룰 수 있다.
트리의 높이(Height)
트리의 높이는 루트 노드부터 가장 아래에 있는 리프 노드까지의 거리다. 루트를 레벨 0으로 두었을 때, 가장 깊은 레벨 번호가 트리의 높이가 된다.
o ← Level 0
o o ← Level 1
o o o ← Level 2
트리의 높이 = 2완전 이진 트리에서 각 레벨에 들어갈 수 있는 노드 수는 규칙적이다.
- Level 0 → 1개
- Level 1 → 2개
- Level 2 → 4개
- Level k → 2^k개
따라서 높이가 h인 완전 이진 트리에서 모든 노드가 꽉 차 있다면, 전체 노드 수는 다음과 같다.
1 + 2 + 4 + ... + 2^h = 2^(h+1) - 1반대로 노드의 개수가 N개라면, 트리의 높이는 대략 log₂N 수준이 된다. 즉, 노드 수가 크게 늘어나도 트리의 높이는 빠르게 커지지 않는다.
정리
트리는 데이터를 계층 구조로 표현하기 위한 비선형 자료구조다. 이진 트리는 각 노드가 최대 두 개의 자식을 가지는 트리이고, 완전 이진 트리는 노드가 왼쪽부터 차례대로 채워지는 규칙적인 이진 트리다. 완전 이진 트리는 배열로 표현할 수 있으며, 이 특성 덕분에 이후에 배울 다양한 자료구조의 기반이 된다.
