트리 자료구조 요약

Cheatsheet Content

### 1. 트리의 소개 및 기본 개념 트리는 선형 자료구조(배열, 연결 리스트)의 한계를 극복하기 위해 등장한 **비선형 계층적(Hierarchical)** 자료구조입니다. 데이터 간의 부모-자식 관계를 명시적으로 표현하여 복잡한 관계를 효율적으로 모델링할 수 있습니다. **선형 vs. 비선형 자료구조:** - **선형(Linear):** 데이터 요소들이 순차적으로 연결되어 하나의 긴 줄을 형성합니다. (예: `A -> B -> C`) - 장점: 구현이 간단하고 메모리 접근이 직관적입니다. - 단점: 계층적 관계나 복잡한 네트워크 구조를 표현하기 어렵습니다. - **비선형(Non-linear):** 데이터 요소들이 1:N 또는 N:M 관계를 가집니다. (예: `A -- B, A -- C`) - 장점: 실제 세계의 복잡한 관계(조직도, 파일 시스템, 소셜 네트워크)를 효과적으로 모델링할 수 있습니다. - 단점: 구현이 더 복잡하고, 순회(traversal) 알고리즘이 다양합니다. **트리(Tree)의 정의:** 트리는 다음 속성들을 만족하는 유한한 노드들의 집합입니다. 1. **루트 노드(Root Node):** 트리의 가장 상위에 있는 유일한 노드이며, 부모가 없습니다. 2. **부모-자식 관계:** 루트를 제외한 모든 노드는 정확히 하나의 부모 노드를 가집니다. 부모 노드로부터 하나 이상의 자식 노드가 파생될 수 있습니다. 3. **사이클(Cycle) 없음:** 어떤 노드에서도 자기 자신으로 돌아오는 경로가 존재하지 않습니다. 4. **연결성:** 모든 노드는 루트로부터 도달 가능합니다. **트리의 주요 응용 분야:** - **파일 시스템:** 디렉토리와 파일의 계층 구조. - **데이터베이스 인덱싱:** B-트리, B+트리 등을 사용하여 빠른 데이터 검색. - **컴퓨터 네트워크 라우팅:** 네트워크 경로 결정. - **컴파일러:** 프로그램 코드의 구문 분석 트리(Parse Tree, Syntax Tree). - **인공지능:** 의사 결정 트리(Decision Tree), 게임 트리(Game Tree). - **XML/HTML 문서 구조:** DOM(Document Object Model) 트리. ### 2. 트리의 핵심 용어 및 속성 트리를 이해하고 설명하기 위한 핵심적인 용어들입니다. - **노드(Node):** 트리를 구성하는 기본 요소로, 데이터를 저장합니다. - **간선(Edge):** 노드와 노드를 연결하는 선으로, 부모-자식 관계를 나타냅니다. - **루트 노드(Root Node):** 트리의 가장 상위에 있는 노드 (부모가 없음). 트리는 오직 하나의 루트 노드만 가집니다. - **부모 노드(Parent Node):** 특정 노드의 바로 위에 연결된 노드. - **자식 노드(Child Node):** 특정 노드의 바로 아래에 연결된 노드. - **형제 노드(Sibling Node):** 같은 부모를 가지는 노드들. - **조상(Ancestors):** 특정 노드에서 루트까지의 경로에 있는 모든 노드 (부모, 조부모 등). - **자손(Descendants):** 특정 노드에서부터 아래로 연결된 모든 노드 (자식, 손자 등). - **리프 노드(Leaf Node) / 외부 노드(External Node):** 자식이 없는 노드. - **내부 노드(Internal Node):** 하나 이상의 자식을 가지는 노드 (루트 노드 포함, 리프 노드 제외). - **경로(Path):** 한 노드에서 다른 노드까지 간선을 따라 이동하는 순서. - **경로 길이(Path Length):** 경로를 구성하는 간선의 수. - **깊이(Depth):** 루트 노드로부터 특정 노드까지의 경로 길이. 루트 노드의 깊이는 0입니다. (예: `depth(노드 k) = depth(노드 k의 부모) + 1`) - **높이(Height):** 트리에 있는 모든 노드의 깊이 중 최댓값. 또는, 루트 노드에서 가장 깊은 리프 노드까지의 경로 길이. 리프 노드의 높이는 0입니다. (예: `height(노드 k) = max(height(노드 k의 자식)) + 1`) - **레벨(Level):** 깊이와 유사한 개념으로, 루트를 레벨 1(또는 0)로 시작하여 아래로 내려갈수록 1씩 증가합니다. - **서브트리(Subtree):** 특정 노드를 루트로 하고, 그 노드의 모든 자손으로 구성된 부분 트리. **예시:** ``` A (깊이 0, 높이 3) /|\ B C D (깊이 1) /| | \ E F G H (깊이 2) / \ I J (깊이 3) ``` - 루트: A - 리프 노드: D, E, G, H, I, J - 내부 노드: A, B, C, F - 노드 I의 깊이: 3, 트리의 높이: 3 ### 3. 트리 ADT와 메모리 표현 (구현) 트리는 추상 데이터 타입(ADT)으로서 논리적인 계층 구조와 연산을 정의하며, 실제 메모리에는 다양한 방식으로 구현될 수 있습니다. #### 3.1. 트리 ADT (Abstract Data Type) 트리 ADT는 트리의 논리적 모델을 정의하고, 트리에 대해 수행할 수 있는 연산의 집합을 명세합니다. - **노드(Position) 기반 접근:** 트리의 각 요소를 `Position` 객체로 추상화하여, 실제 저장 방식과 독립적으로 트리를 조작할 수 있게 합니다. - **주요 연산:** - **접근자(Accessor):** `root()`, `parent(p)`, `children(p)`, `numChildren(p)`. - **질의(Query):** `isRoot(p)`, `isLeaf(p)`, `isEmpty()`. - **업데이터(Update):** `addRoot(e)`, `addChild(p, e)`, `remove(p)`, `set(p, e)` (트리 종류에 따라 다름). #### 3.2. 트리의 메모리 표현 (구현 방식) 트리는 비선형 구조이지만, 컴퓨터 메모리는 선형적입니다. 따라서 포인터나 배열을 사용하여 계층 구조를 인코딩합니다. 1. **노드 객체와 연결 리스트/포인터 기반 구현:** - 가장 일반적입니다. 각 노드를 객체로 표현하고, 데이터와 함께 부모 및 자식 노드에 대한 참조(포인터)를 가집니다. - **일반적인 노드 구조:** ```java class Node { Object data; Node parent; List children; // 또는 Node[] children; } ``` - **장점:** 유연하게 노드 추가/삭제 가능, 자식 수에 제한 없음. - **단점:** 각 노드마다 포인터 저장 공간 필요, 메모리 할당/해제 오버헤드. 2. **첫째 자식 / 다음 형제 (First-Child / Next-Sibling) 구현:** - 일반 트리를 이진 트리와 유사하게 표현하는 기법입니다. - 각 노드는 두 개의 포인터를 가집니다: `firstChild` (가장 왼쪽 자식)와 `nextSibling` (다음 형제 노드). - **노드 구조:** ```java class Node { Object data; Node firstChild; Node nextSibling; } ``` - **장점:** 모든 트리를 이진 트리 형태로 표현할 수 있어 구현이 간결하고 메모리 효율적입니다. - **단점:** 특정 노드의 모든 자식을 찾으려면 `nextSibling`을 따라 순회해야 하므로 시간이 더 걸릴 수 있습니다. 3. **배열 기반 구현 (주로 완전 이진 트리에 사용):** - 트리의 노드들을 배열의 인덱스에 매핑하여 저장합니다. (예: 힙) - **완전 이진 트리의 경우:** - 루트 노드는 인덱스 1 (또는 0)에 저장. - 인덱스 `i`의 노드에 대해: 왼쪽 자식 `2 * i`, 오른쪽 자식 `2 * i + 1`, 부모 `floor(i / 2)`. - **장점:** 포인터 없이 인덱스 연산으로 노드 관계를 알 수 있어 메모리 효율성과 접근 속도가 매우 빠릅니다. - **단점:** 트리가 완전 이진 트리가 아닐 경우, 배열에 많은 빈 공간이 발생하여 메모리 낭비가 심합니다. ### 4. 트리 순회(Traversal) 알고리즘 트리 순회는 트리의 모든 노드를 체계적으로 방문하여 특정 작업을 수행하는 과정입니다. #### 4.1. 깊이 우선 탐색 (DFS: Depth-First Search) 기반 순회 DFS는 가능한 한 깊이 내려가면서 노드를 방문하는 방식입니다. 재귀적으로 구현하는 것이 일반적입니다. 1. **전위 순회 (Pre-order Traversal):** - **방문 순서:** **현재 노드 방문** → 왼쪽 서브트리 순회 → 오른쪽 서브트리 순회 - **응용:** 트리 구조 복사, 전위 표기법 수식 변환 (예: `+ * A B C` → `A * B + C`). - **코드 스니펫:** `visit(node); pre_order(node.left); pre_order(node.right)` 2. **중위 순회 (In-order Traversal):** (주로 이진 트리에 적용) - **방문 순서:** 왼쪽 서브트리 순회 → **현재 노드 방문** → 오른쪽 서브트리 순회 - **응용:** **이진 탐색 트리(BST)에서 노드를 오름차순으로 정렬된 순서대로 얻기.** 중위 표기법 수식 변환 (예: `A * B + C`). - **코드 스니펫:** `in_order(node.left); visit(node); in_order(node.right)` 3. **후위 순회 (Post-order Traversal):** - **방문 순서:** 왼쪽 서브트리 순회 → 오른쪽 서브트리 순회 → **현재 노드 방문** - **응용:** 트리 노드 삭제 (자식 노드부터 삭제), 후위 표기법 수식 변환 (예: `A B * C +`). 파일 시스템에서 디렉토리의 총 크기 계산. - **코드 스니펫:** `post_order(node.left); post_order(node.right); visit(node)` #### 4.2. 너비 우선 탐색 (BFS: Breadth-First Search) 기반 순회 BFS는 현재 레벨의 모든 노드를 방문한 후 다음 레벨로 넘어가는 방식입니다. 큐(Queue)를 사용하여 구현합니다. - **레벨 순서 순회 (Level-order Traversal):** - **방문 순서:** 루트 노드부터 시작하여, 같은 레벨의 노드들을 왼쪽에서 오른쪽으로 방문한 후 다음 레벨로 이동합니다. - **응용:** 최단 경로 찾기 (그래프 탐색에서 중요), 트리에서 특정 레벨의 모든 노드에 접근. - **코드 스니펫:** `queue = deque([root]); while queue: node = queue.popleft(); visit(node); enqueue_children(node)` ### 5. 이진 트리 (Binary Trees) 이진 트리는 각 노드가 **최대 두 개의 자식 노드** (왼쪽 자식, 오른쪽 자식)를 가질 수 있는 특별한 형태의 트리입니다. 복잡한 알고리즘에서 매우 중요한 역할을 하며, 분석하기 용이합니다. #### 5.1. 이진 트리의 정의 및 종류 - **정의:** 각 노드는 0개, 1개 또는 2개의 자식 노드를 가질 수 있으며, 자식 노드는 왼쪽 자식과 오른쪽 자식으로 명확히 구분됩니다. - **종류:** 1. **정 이진 트리 (Full Binary Tree / Strict Binary Tree):** 모든 내부 노드(리프가 아닌 노드)가 정확히 두 개의 자식을 가집니다 (0개 또는 2개의 자식만 가짐). 2. **완전 이진 트리 (Complete Binary Tree):** 마지막 레벨을 제외한 모든 레벨이 완전히 채워져 있으며, 마지막 레벨의 노드들은 가능한 한 왼쪽부터 채워져 있습니다 (힙(Heap) 자료구조 구현에 사용). 3. **포화 이진 트리 (Perfect Binary Tree):** 모든 내부 노드가 두 개의 자식을 가지며, 모든 리프 노드가 같은 깊이(레벨)에 있습니다. 깊이가 `d`인 포화 이진 트리는 `2^(d+1) - 1`개의 노드를 가집니다. #### 5.2. 이진 트리의 속성 - **깊이가 `d`인 이진 트리가 가질 수 있는 최대 노드 수:** $2^{d+1} - 1$ - **`n`개의 노드를 가진 이진 트리의 최소 높이:** $\lfloor \log_2 n \rfloor$ (완전 이진 트리의 경우) - **`n`개의 노드를 가진 이진 트리의 최대 높이:** `n-1` (사향 트리/Skewed Tree의 경우) - **리프 노드의 개수와 내부 노드의 개수 관계 (정 이진 트리):** 리프 노드 수 `L`, 내부 노드 수 `I`일 때, `L = I + 1`. #### 5.3. 수식 트리 (Expression Tree) 구성 예시 수식 트리는 산술 또는 논리 수식을 표현하는 이진 트리입니다. 내부 노드는 연산자를, 리프 노드는 피연산자를 나타냅니다. 후위 표기법(Postfix Notation)을 스택을 사용하여 수식 트리로 변환하는 알고리즘은 다음과 같습니다. 1. 빈 스택을 생성합니다. 2. 후위 표기법 수식의 각 토큰을 왼쪽에서 오른쪽으로 스캔합니다. 3. **토큰이 피연산자(숫자, 변수)인 경우:** 해당 피연산자를 값으로 하는 새 노드(리프)를 생성하고 스택에 푸시합니다. 4. **토큰이 연산자(+, -, *, / 등)인 경우:** 스택에서 상위 두 개의 노드를 팝합니다 (먼저 팝된 것이 오른쪽 자식, 다음 팝된 것이 왼쪽 자식). 해당 연산자를 값으로 하는 새 노드를 생성하고, 팝된 두 노드를 각각 왼쪽/오른쪽 자식으로 연결합니다. 새로 생성된 연산자 노드를 스택에 푸시합니다. 5. 모든 토큰을 처리한 후, 스택에 남아있는 유일한 노드가 수식 트리의 루트가 됩니다. **예시: `5 7 2 3 * / +`** 1. `5, 7, 2, 3` (피연산자) 차례로 스택에 푸시: `[Node(5), Node(7), Node(2), Node(3)]` 2. `*` (연산자): `Node(3), Node(2)` 팝. `Node('*', left=Node(2), right=Node(3))` 생성 후 푸시: `[Node(5), Node(7), Node(*)]` 3. `/` (연산자): `Node(*), Node(7)` 팝. `Node('/', left=Node(7), right=Node(*))` 생성 후 푸시: `[Node(5), Node(/)]` 4. `+` (연산자): `Node(/), Node(5)` 팝. `Node('+', left=Node(5), right=Node(/))` 생성 후 푸시: `[Node(+)]` 최종 스택: `[Node(+)]` (이것이 수식 트리의 루트입니다.)