트리 기반 모델들이 머신러닝에 주를 이루고 있습니다.
예를 들어, xgboost, Light gbm 등 모두 decision tree를 기반으로 한 모델입니다. 이 트리 구조는 도대체 어떻게 공부해야 할까요?
혹시, 면접에서 트리 순회 질문이 나왔는데 제대로 대답하지 못했나요? 오늘은 완전 이진 트리와 트리 순회에 대해 쉽게 설명해드리겠습니다.
완전 이진 트리의 특징
완전 이진 트리는 마치 나무(tree)를 거꾸로 메단 것처럼 규칙적인 구조를 가지고 있습니다. 모든 레벨이 왼쪽부터 차근차근 채워지죠. 마지막 레벨을 제외한 모든 레벨은 꽉 차있어야 합니다.
예를 들어, 학교 체육대회 계주 달리기 팀을 구성한다고 생각해 보죠. 각 학년마다 인원을 골고루 배치하고, 마지막 6학년만 조금 적게 넣는 방식입니다.
완전 이진 트리의 주요 특징은 3가지 입니다.
- 모든 노드는 최대 2개의 자식을 가질 수 있습니다.
- 마지막 레벨을 제외하고는 모든 레벨이 완전히 채워져 있습니다.
- 마지막 레벨의 노드들은 왼쪽부터 채워져야 합니다.
실제로 많은 기업들이 완전 이진 트리 구조를 활용하는데요. 예를 들어, 넷플릭스는 콘텐츠 추천 시스템에서 이진 트리 구조를 사용한다고 합니다.
트리 순회란?
트리 순회는 트리가 길을 찾아가는 방식입니다. 즉 트리의 모든 노드를 방문하는 방법인데요. 세 가지 주요 방법이 있습니다.
1. 전위 순회(Preorder): 부모 → 왼쪽 자식 → 오른쪽 자식
2. 중위 순회(Inorder): 왼쪽 자식 → 부모 → 오른쪽 자식
3. 후위 순회(Postorder): 왼쪽 자식 → 오른쪽 자식 → 부모
이해하기 어렵다고요? 아래 링크에는 완전 이진 트리의 트리 순회의 동작하는 애니메이션을 볼 수 있습니다. 아마 이해하기 더 쉬울 거예요.
알고리즘 동작 방식
트리 순회 알고리즘은 마치 미로를 탐험하는 것과 비슷해요. 각각의 방법마다 고유한 규칙이 있고, 그 규칙을 따라가면 모든 노드를 빠짐없이 방문할 수 있어요.
예를 들어, 전위 순회는 이렇게 동작합니다.
def preorder(node):
if node:
print(node.value) # 현재 노드 방문
preorder(node.left) # 왼쪽 서브트리 방문
preorder(node.right) # 오른쪽 서브트리 방문
이 코드는 마치 우리가 집을 방문할 때 현관문 -> 왼쪽 방 -> 오른쪽 방 순서로 들어가는 것과 같이 순서대로 값을 찾아가는 방식입니다.
구현 및 시간 복잡성 분석
트리 순회 알고리즘의 시간 복잡도는 O(n)이에요. 여기서 n은 트리의 노드 수를 의미합니다. 왜냐하면 각 노드를 정확히 한 번씩만 방문하기 때문이죠.
- 공간 복잡도의 경우
- 최선의 경우: O(log n) – 균형 잡힌 트리
- 최악의 경우: O(n) – 한쪽으로 치우친 트리
실제 구현 예시를 보면 더 쉽게 이해할 수 있습니다. 코드는 아래와 같습니다.
class Node:
def __init__(self, value):
self.value = value
self.left = None
self.right = None
마치며
지금까지 완전 이진 트리 개념과 트리 순회에 대해 알아봤는데요. 하지만 이제 시작에 불과합니다. 이 개념들을 응용한 더 진보된 모델들을 공부해야 합니다.
