트리

트리(Tree)의 개념

트리는 그래프 중 하나로 그래프의 특징처럼 정점과 간선으로 이루어져 있고, 트리 구조로 배열된 일종의 계층적 데이터의 집합입니다.

계층 구조

트리는 부모와 자식의 관계를 가지고, 부모 노드에서 자식 노드로 방향성이 있는 간선으로 연결됩니다. 각 노드는 오직 하나의 부모를 가지고 있습니다. (루트 노드 제외)

루트 노드

트리는 하나의 루트(root) 노드를 가집니다. 이 루트 노드는 모든 다른 노드로부터 독립적으로 연결되어 있으며, 트리의 시작점을 나타냅니다.

내부 노드

루트 노드와 내부 노드 사이에 있는 노드를 말합니다.

리프 노드

트리의 노드 중에서 자식 노드가 없는 노드를 리프 노드(leaf node) 또는 단말 노드(terminal node)라고 합니다.

트리의 높이와 레벨

• 깊이
  • 트리에서의 깊이는 각 노드마다 다르며, 루트 노드부터 특정 노드까지 최단거리로 갔을 때의 거리를 말합니다. 예를 들어 위 그림에서 D 노드의 깊이는 2입니다.
• 높이
  • 트리의 높이는 루트 노드부터 리프 노드까지의 거리 중 가장 긴 거리를 의미하며 위 그림의 트리 높이는 3입니다.
• 레벨
  • 트리의 레벨은 주어지는 문제마다 조금씩 다르지만 보통 깊이와 같은 의미를 지닙니다.
• 서브트리
  • 트리 내의 하위 집합을 서브트리라고 합니다.

이 내용을 정리하면 다음과 같은 특성을 가집니다.

1. 트리는 하나의 루트 노드를 갖는다.
2. 루트 노드는 0개 이상의 자식 노드를 갖고 있다.
3. 그 자식 노드 또한 0개 이상의 자식 노드를 갖고 있고, 이는 반복적으로 정의된다.

이러한 노드들은 간선으로 노드들과 연결되어 있습니다. 이러한 점은 그래프(graph)와 같지만 서로 다른 특성이 있습니다.

사이클

• 그래프: 그래프는 순환이 가능한 자료 구조입니다. 즉, 그래프에서 한 노드에서 시작하여 순환 경로를 따라 이동할 수 있습니다.
• 트리: 트리는 순환을 포함하지 않는 특별한 종류의 그래프입니다. 즉, 트리는 사이클이 없는 그래프입니다.

루트 및 계층 구조

• 그래프: 그래프에는 특별한 루트 노드가 없으며, 간선을 통해 서로 연결된 임의의 노드들로 구성됩니다. 그래프는 일반적으로 비선형(non-linear) 관계를 표현하는 데 사용됩니다.
• 트리: 트리는 정확히 하나의 루트 노드로 시작하는 계층적(hierarchical) 구조를 갖습니다. 각 노드는 부모-자식 관계를 가지며, 재귀적으로 정의됩니다.

노드의 다수성

• 그래프: 그래프에서는 노드 간에 다양한 관계가 있을 수 있으며, 두 노드 사이에 여러 개의 간선이 존재할 수 있습니다.
• 트리: 트리에서는 각 노드가 정확히 하나의 부모를 가지며, 부모 노드로부터 최대 두 개의 자식 노드를 가질 수 있습니다. 트리에서 노드 간에는 순서가 존재합니다.

용도와 응용

• 그래프: 그래프는 네트워크, 소셜 그래프, 지도 등 다양한 영역에서 사용됩니다. 그래프는 복잡한 상호 작용을 모델링하거나 데이터 간의 관계를 나타내는 데 유용합니다.
• 트리: 트리는 계층 구조를 표현하고 검색, 정렬, 데이터 구조화 등에 사용됩니다. 파일 시스템, 조직도, HTML 문서 구조 등에 대한 표현에 사용됩니다.

이진 트리

이진 트리는 자식의 노드 수가 두개 이하인 트리를 의미합니다.

이진 트리 종류

• 정 이진 트리
  • 자식 노드가 0 또는 2개인 이진 트리를 의미합니다.
• 완전 이진 트리
  • 왼쪽에서부터 채워져 있는 이진 트리를 의미합니다. 마지막 레벨을 제외하고는 모든 레벨이 완전히 채워져 있으며, 마지막 레벨의 경우 왼쪽부터 채워져 있습니다.
• 포화 이진 트리
  • 정 이진 트리이면서 완전 이진 트리인 경우입니다. 모든 리프 노드의 레벨이 동일하고, 모든 레벨이 가득 채워져 있는 트리입니다.

이진 트리 순회 방법

• 중위 순회(in-order traversal): 왼쪽 자손, 자신, 오른쪽 자손 순서로 방문하는 순회 방법. 이진 탐색 트리를 중위 순회하면 정렬된 결과를 얻을 수 있다.
• 전위 순회(pre-order traversal): 자신, 왼쪽 자손, 오른쪽 자손 순서로 방문하는 순회 방법.
• 후위 순회(post-order traversal): 왼쪽 자손, 오른쪽 자손, 자신 순서로 방문하는 순회 방법.
• 레벨 순서 순회(level-order traversal): 너비 우선 순회(Breadth-First traversal)라고도 한다. 노드를 레벨 순서로 방문하는 순회 방법. 위의 세 가지 방법은 스택을 활용하여 구현할 수 있는 반면 레벨 순서 순회는 큐를 활용해 구현할 수 있다.

• In-order: 1 3 4 6 7 8 10 13 14
• Pre-order: 8 3 1 6 4 7 10 14 13
• Post-order: 1 4 7 6 3 13 14 10 8
• Level-order: 8 3 10 1 6 14 4 7 13

이진 탐색 트리

이진 탐색 트리는 이진 트리의 일종으로, 노드의 왼쪽 가지에는 노드의 값보다 작은 값들만 있고, 오른쪽 가지에는 큰 값들만 있도록 구성되었습니다.

트리가 이상적으로 구성되었을 때 탐색/삽입/삭제 모두 시간복잡도가

*O(logN*)이 됩니다.

AVL 트리

AVL 트리는 이진 탐색 트리(Binary Search Tree, BST)의 일종으로, 균형 잡힌 이진 탐색 트리입니다.

이진 탐색은 선형적인 트리 구조를 가질 경우 최악의 경우로 O(n)의 시간복잡도를 가질 수 있습니다. 이러한 경우를 배제하고 항상 균형잡힌 트리로 만들자 라는 개념을 가진 트리가 바로 AVL 트리입니다.

회전 연산: AVL 트리에서 노드를 삽입하거나 삭제할 때, 높이 차이가 발생할 경우에는 회전 연산을 통해 균형을 유지합니다. 이는 단일 회전, 두 번 연속 회전 등 다양한 형태로 이루어질 수 있습니다.

레드-블랙 트리

이진 탐색 트리(Binary Search Tree, BST)의 일종으로, 균형 잡힌 트리의 한 종류입니다.

1. 색상 속성(Color Property): 레드-블랙 트리의 각 노드는 레드(red) 또는 블랙(black) 중 하나의 색상을 갖습니다. 트리의 모든 노드에는 다음과 같은 추가 제약 조건이 있습니다:
   • 루트 노드는 블랙이어야 합니다.
   • 각 리프 노드는 블랙이어야 합니다. (null 노드를 포함합니다)
   • 레드 노드의 자식 노드는 모두 블랙이어야 합니다.
   • 어떤 노드로부터 시작하는 단순 경로에 있는 블랙 노드의 수는 모두 같아야 합니다.

---

참조

[자료구조] 트리(Tree)란 - Heee’s Development Blog

이진 트리