[자료구조 Java] 비선형 자료구조 ② 트리

비선형 자료구조란?

: 일렬로 나열하지 않고 자료 순서나 관계가 복잡한 구조를 말하며 일반적으로 트리나 그래프를 의미

2. 트리

: 계층적 관계를 표현하는 자료구조

2-1. 관련 용어

- Node(노드): 트리를 구성하고 있는 각각의 요소

- Edge(간선): 노드와 노드를 연결하는 선

- Root Node(루트 노드): 트리 구조에서 최상위에 있는 노드

- Terminal Node(=Leaf Node, 단말 노드): 하위에 다른 노드가 연결되어 있지 않은 노드

- Internal Node(내부 노드, 비단말 노드): 단말 노드를 제외한 모든 노드 (루트노드도 포함)

- Sibling: 같은 부모를 가지는 노드

- 노드의 크기: 자신을 포함한 모든 자손 노드의 개수

- 노드의 깊이: 루트에서 어떤 노드에 도달하기 위해 거쳐야 하는 간선의 수

- 노드의 레벨: 트리의 특정 깊이를 가지는 노드의 집합

- 노드의 차수: 하위 트리 개수 / 간선의 수 = 각 노드가 지닌 가지의 수

- 트리의 차수: 트리의 최대 차수

- 트리의 높이: 루트 노드에서 가장 깊숙히 있는 노드의 깊이

2-2. 트리의 특징

- 최소 연결 트리라고도 불리며, 방향성이 없는 비순환 그래프(DAG)의 한 종류
- 노드가 N개인 트리는 항상 N-1개의 간선을 갖는다 (V = E - 1)
- 루트에서 어떤 노드로 가는 경로는 유일
- 한 개의 루트 노드만이 존재하며, 모든 자식 노드는 한 개의 부모 노드를 가짐

2-3. 트리의 순회 방식

2-3-1. 전위 순회 (pre-order)

: 각 루트를 순차적으로 먼저 방문

1 → 2 → 4 → 8 → 9 → 5 → 10 → 11 → 3 → 6 → 12 → 7 → 13

2-3-2. 중위 순회 (in-order)
: 왼쪽 하위 트리를 방문 후 루트를 방문 (왼쪽 자식 -> root -> 오른쪽 자식)

8 → 4 → 9 → 2→ 10 → 5 → 11 → 1 → 6 → 12 → 3 → 13 → 7

2-3-3. 후위 순회 (post-order)

: 왼쪽 하위 트리부터 하위를 모두 방문 후 루트를 방문 (왼쪽 자식 -> 오른쪽 자식 -> root)

8 → 9 → 4 → 10 → 11 → 5 → 2 → 12 → 6 → 13 → 7 → 3 → 1

2-3-4. 레벨 순회 (level-order)

: 루트부터 계층 별로 방문하는 방식

1 → 2 → 3 → 4 → 5 → 6 → 7 → 8 → 9 → 10 → 11 → 12 → 13

2-4. 트리의 종류

2-3-1. 이진트리

- 자식의 노드 수가 두 개 이하인 트리를 의미

구분	설명
정이진 트리(full binary tree)	자식 노드가 0 또는 두 개인 이진 트리
완전 이진 트리(complete binary tree)	왼쪽에서부터 채워져 있는 이진 트리 - 마지막 레벨을 제외하고 모든 레벨은 2개씩 채워져 있음 - 마지막 레벨의 경우 왼쪽부터 채워져 있음
변질 이진 트리(degenerate binary tree)	자식 노드가 하나밖에 없는 이진 트리
포화 이진 트리(perfect binary tree)	모든 노드가 꽉 차 있는 이진 트리
균형 이진 트리(balanced binary tree)	왼쪽과 오른쪽 노드의 높이 차이가 1 이하인 이진 트리

2-3-2. 이진 탐색 트리 (BST, Binary Search Tree)

- 이진 탐색 트리는 이진 트리의 일종으로, 특정 규칙에 따라 데이터가 저장되는 트리

규칙 1. 이진 탐색 트리의 노드에 저장되는 키(key)는 유일
규칙 2. 부모의 키가 왼쪽 자식 노드의 키보다 큼
규칙 3. 부모의 키가 오른쪽 자식 노드의 키보다 큼
규칙 4. 왼쪽과 오른쪽 서브트리도 모두 이진 탐색 트리

- 이진 탐색 트리의 탐색 연산은 O(log n)의 시간복잡도를 가지나, 삽입 순서에 따라 선형적 트리일 경우 O(n)이 될 수 있음
- 배열보다 많은 메모리를 사용하며 데이터를 저장했으나, 탐색에 필요한 시간 복잡도가 같게 되는 비효율적인 상황 발생
  ▶︎ 이후 다룰 Red-black tree를 통해 해결할 수 있음

2-3-3. 레드 블랙 트리 (Red Black Tree)

- 균형 이진 탐색 트리로, 탐색, 삽입, 삭제 모두 시간 복잡도가 O(long n)이 소요
- 동일한 노드의 개수일 때 depth를 최소화하여 시간복잡도를 줄이는 것이 핵심 아이디어