내용에 대한 출처는 ‘이것이 취업을 위한 컴퓨터 과학이다’에 책에서 CHAPTER 04 자료구조에서 - 5 트리에 대한 내용입니다.
정의
- 주로 계층적인 구조를 표현하기 위한 자료구조이다.
- 계층적인 구조란 부모와 자식 간의 관계를 깊이로 구분하여 표현
- 노드와 노드 간 연결(간선, edge) 으로 구성되며, 간선으로 연결된 노드들은 상하 관계를 형성한다.
- 계층 구조 표현뿐만 아니라 탐색 등 다양한 상황에서 범용적으로 사용된다.
기본 용어 정리
- 부모 노드 / 자식 노드 : 상하 관계에서 위쪽은 부모, 아래쪽은 자식. 상대적인 개념이다.
- 형제 노드(sibling node) : 같은 부모를 공유하는 노드.
- 조상 노드 : 부모 노드 및 그 윗단의 노드들.
- 자손 노드 : 자식 노드 및 그 아래 노드들.
- 루트 노드 : 부모가 없는 최상단 노드.
- 리프 노드 : 자식 노드가 없는 최하단 노드.
- 차수 (degree) : 해당 노드가 가지는 자식 노드의 수.
- 레벨 : 루트 노드로부터 특정 노드까지 거치는 간선의 수.
- 트리의 깊이(depth) : 특정 노드가 얼마나 깊은 위치에 있는지를 나타냄.
- 트리의 높이(height) : 트리 내 가장 높은 레벨이 높이가 됌.
트리는 연결리스트처럼 하나의 노드를 데이터 + 자식 노드의 위치 정보(주소)로 구현할 수 있음.
트리의 순회
트리의 모든 노드를 한 번씩 방문하는 것을 트리의 순회라고 함. 대표적인 순회 방법은 다음 3가지가 있다.
전위 순회 (Preorder)
- 루트 → 왼쪽 서브트리 → 오른쪽 서브트리
- 루트 노드를 먼저 방문한 다음 왼쪽, 그다음 오른쪽 서브트리를 전위 순회 방식으로 재귀적 방문.
중위 순회 (Inorder)
- 왼쪽 서브트리 → 루트 → 오른쪽 서브트리
- 루트 노드를 기준으로 왼쪽을 먼저 중위 순회한 뒤, 루트를 방문하고 오른쪽 서브트리를 순회.
후위 순회 (Postorder)
- 왼쪽 서브트리 → 오른쪽 서브트리 → 루트
- 모든 자식들을 먼저 순회한 뒤 마지막에 루트를 방문.
이건 많은 예시들을 보면서 이해해야 함.
트리의 종류
이진 트리 (Binary Tree)
- 자식 노드가 최대 2개인 트리.
- 가장 흔히 떠올리는 기본적인 트리 구조.
편향 이진 트리
- 자식 노드들이 한 쪽으로만 몰린 구조.
정 이진 트리
- 자식 노드의 수가 0개 또는 2개인 이진 트리 (1개인 경우는 없음).
포화 이진 트리
- 리프 노드를 제외한 모든 노드가 자식 2개를 가지고, 리프 노드들의 레벨이 동일함.
완전 이진 트리
- 마지막 레벨을 제외한 모든 노드가 자식 2개를 가지며, 마지막 레벨의 노드들이 왼쪽부터 차례로 채워져 있음.
탐색에 활용되는 트리
이진 탐색 트리 (BST, Binary Search Tree)
- 왼쪽 서브트리에는 작은 값들, 오른쪽 서브트리에는 큰 값들이 위치.
- 정렬된 데이터를 효율적으로 탐색하기 위한 구조.
힙 (Heap)
- 완전 이진 트리 기반의 우선순위 큐 구현 구조.
최대 힙 (Max Heap)
- 부모 노드 ≥ 자식 노드, 가장 큰 값이 루트 노드에 위치.
최소 힙 (Min Heap)
- 부모 노드 ≤ 자식 노드, 가장 작은 값이 루트 노드에 위치.
우선순위 큐는 일반적으로 최대 힙 구조로 구현함.
균형 이진 탐색 트리
자가 균형 이진 탐색 트리
- 왼쪽/오른쪽 서브트리의 높이 차이를 일정하게 유지함.
- 탐색 성능을 일정하게 유지하기 위해 자동으로 회전 연산 등을 통해 균형을 맞춤.
AVL 트리
삽입/삭제 후에 균형 인수(balance factor) 를 기준으로 회전함.
RB 트리 (Red-Black Tree)
특정 규칙에 따라 균형을 유지하는 트리.
- 루트 노드는 블랙 노드
- 리프 노드는 블랙 노드
- 레드 노드의 자식은 모두 블랙 노드
- 루트에서 모든 리프 노드까지의 경로에 있는 블랙 노드의 수는 동일
트리의 회전 (Rotation)
- 균형 조정을 위한 연산.
- 부모와 자식 간의 관계를 재조정하여 왼쪽/오른쪽 서브트리의 높이 차이를 줄임.
- 회전 이후에도 이진 탐색 트리의 조건은 유지되어야 함.
B트리 & B+트리
B트리
- 균형 잡힌 다진 탐색 트리 (이진 X).
- 모든 리프 노드의 깊이가 같음.
- 디스크 기반의 대규모 데이터 저장 구조에서 주로 사용.
B+트리
- B트리의 변형.
- 모든 실질적 데이터는 리프 노드에 저장.
- 리프 노드들은 연결 리스트 형태로 연결되어 있음.
- 파일 시스템이나 데이터베이스에서 주로 사용됨.
Software Engineer