이진 트리에 대해서 설명해 주세요.
분야: 백엔드
트리(Tree) 는 방향이 존재하는 그래프의 일종으로 부모 정점 밑에 여러 자식 정점이 연결되고, 자식 정점 각각에 다시 자식 정점이 연결되는 재귀적 형태의 자료구조입니다. 그 중에서 각 정점이 최대 2개의 자식 정점을 가지는 트리를 이진 트리(Binary Tree) 라고 합니다.
이진 트리의 종류는 무엇이 있나요?
정점이 채워져 있는 형태에 따라서 대표적으로 포화 이진 트리, 완전 이진 트리, 편향 이진 트리가 존재합니다.
마지막 레벨까지 모든 정점이 채워져 있는 경우, 포화 이진 트리라고 부릅니다.
1 --- level 1
/ \
2 3 --- level 2
/ \ / \
4 5 6 7 --- level 3
마지막 레벨을 제외하고 모든 정점이 채워져 있는 경우, 완전 이진 트리라고 부릅니다.
1 --- level 1
/ \
2 3 --- level 2
/ \ /
4 5 6 --- level 3
한 방향으로만 정점이 이어지는 경우, 편향 이진 트리라고 부릅니다.
1 --- level 1
\
2 --- level 2
\
3 --- level 3
\
4 --- level 4
\
5 --- level 5
이진 트리의 특징과 활용 사례를 설명해 주세요.
이진 트리의 대표적인 특징은 다음과 같습니다.
- 이진 트리의 정점이 N개인 경우, 최악의 경우 높이가 (N - 1)이 될 수 있습니다.
- 포화 이진 트리와 완전 이진 트리의 높이는 log N입니다.
- 높이가 h인 포화 이진 트리는 2^(h + 1) - 1개의 정점을 가집니다.
이진 트리는 다른 자료 구조를 만드는 경우에 주로 활용되는데요. 대표적으로 힙(Heap), 이진 탐색 트리(Binary Search Tree)가 존재합니다.
이진 트리의 탐색 방법은 무엇이 있나요?
이진 트리를 탐색하기 위한 방법으로 중위 순회(in-order), 전위 순회(pre-order), 후위 순회(post-order), 층별 순회(level-order)가 존재합니다.
- 중위 순회는 왼쪽 정점, 부모 정점, 오른쪽 정점 순서로 방문합니다.
- 전위 순회는 부모 정점, 왼쪽 정점, 오른쪽 정점 순서로 방문합니다.
- 후위 순회는 왼쪽 정점, 오른쪽 정점, 부모 정점 순서로 방문합니다.
- 층별 순회는 시작 정점의 레벨을 순서대로 모두 방문하고, 이후에 다음 레벨의 정점을 순서대로 방문합니다. (층별로 방문)