🌳 트리(Tree)

트리(Tree)란?

트리는 계층적인 관계를 표현하는 자료구조다. 여러 개의 데이터를 부모-자식 관계로 연결하여 저장하는 방식.

예시

• 가족 족보 → 조상이 있고, 그 아래로 자식, 손자가 계층적으로 이어짐.
• 회사 조직도 → CEO가 있고, 그 아래로 부서장이 있고, 부서장 아래에 직원들이 있음.
• 폴더 구조 → 컴퓨터에서 하나의 폴더 안에 여러 파일과 하위 폴더가 포함될 수 있음.

트리는 한 개의 최상위 노드(루트)에서 시작해서 가지처럼 뻗어나가는 구조이다.

---

트리의 기본 개념

트리의 구성 요소

용어	설명	예시
노드(Node)	데이터를 저장하는 기본 단위	사람, 폴더, 회사 부서
루트(Root) 노드	트리의 최상위 노드	가족 족보에서 가장 윗사람
부모(Parent) 노드	자식 노드를 가지는 노드	아버지, 회사 팀장
자식(Child) 노드	부모 노드 아래에 있는 노드	아들, 팀원
리프(Leaf) 노드	자식이 없는 노드	최하위 직원, 파일
간선(Edge)	노드를 연결하는 선	가족 관계, 조직도
깊이(Depth)	루트에서 특정 노드까지의 거리	조직에서 사장 → 부장 → 팀장 → 직원까지 몇 단계인지
높이(Height)	특정 노드에서 가장 깊은 리프 노드까지의 거리	트리의 최대 깊이

트리의 특징

1️⃣ 루트에서 시작해 여러 개의 자식 노드로 가지를 뻗어나간다. 2️⃣ 하나의 노드는 한 개의 부모 노드만 가질 수 있다 (단, 루트 노드는 부모가 없음). 3️⃣ 트리는 사이클이 없다 (순환 구조가 불가능함). 4️⃣ 깊이(depth)와 높이(height) 개념이 존재한다.

---

트리의 종류

1️⃣ 일반 트리 (General Tree)

• 하나의 부모가 여러 개의 자식을 가질 수 있는 트리.
• 예시: 회사 조직도, 족보, 폴더 구조.

2️⃣ 이진 트리 (Binary Tree)

• 모든 노드가 최대 2개의 자식 노드만 가질 수 있는 트리.
• 예시: 이진 검색 트리(Binary Search Tree, BST), 힙(Heap)

3️⃣ 이진 탐색 트리 (BST, Binary Search Tree)

• 왼쪽 자식은 부모보다 작은 값, 오른쪽 자식은 부모보다 큰 값을 가지는 이진 트리.
• 데이터 검색, 정렬에 효율적 (O(log n) 시간복잡도).
• 예시: 검색 엔진 자동완성 기능, 데이터베이스 인덱스.

4️⃣ 균형 트리 (Balanced Tree)

• 높이가 일정하게 유지되도록 자동 정렬되는 트리.
• 예시: AVL 트리, 레드-블랙 트리 (빠른 검색을 위해 사용됨).

5️⃣ 힙(Heap) 트리

• 부모가 항상 자식보다 크거나(최대 힙), 작도록(최소 힙) 정렬되는 트리.
• 예시: 우선순위 큐 (Priority Queue), 작업 스케줄링 시스템.

6️⃣ B-Tree / B+Tree

• 데이터베이스 인덱스 구조로 사용되는 트리. 검색 속도를 빠르게 하기 위해 설계됨.
• 예시: MySQL, MongoDB 같은 데이터베이스에서 사용.

---

트리의 활용 예시

1️⃣ 파일 시스템

• 📁 폴더 안에 여러 개의 파일과 하위 폴더가 포함되는 구조.
• 트리 구조로 구성되어 있어 탐색이 편리함.

2️⃣ 검색 엔진 자동완성

• 🔎 구글 검색창에서 "hello"를 입력하면 "hello world" 같은 추천 단어가 뜨는 기능.
• Trie(트라이) 트리라는 자료구조를 활용하여 빠르게 단어 검색 가능.

3️⃣ 게임 AI & 의사결정 트리

• 🤖 체스 AI가 다음 수를 결정할 때 트리 탐색을 이용해 최적의 선택을 찾음.
• 🎮 RPG 게임에서 퀘스트 분기점을 결정할 때도 사용됨.

4️⃣ 데이터베이스 인덱스 (B-Tree, B+Tree)

• 📊 데이터베이스에서 데이터를 빠르게 찾기 위해 사용됨.
• 대용량 데이터 검색을 최적화하는 역할.

5️⃣ 네트워크 라우팅 (인터넷 패킷 전달)

• 🌐 인터넷에서 데이터가 목적지까지 갈 때 최적의 경로를 찾기 위해 라우팅 트리를 사용함.

---

트리 탐색 알고리즘

1️⃣ DFS (Depth First Search, 깊이 우선 탐색)

• 한 방향으로 깊이 탐색한 후, 더 이상 갈 곳이 없으면 돌아옴.
• 예시: 미로 찾기, 퍼즐 게임에서 경로 찾기.

function dfs(node) {
    if (!node) return;
    console.log(node.value); // 방문한 노드 출력
    dfs(node.left);
    dfs(node.right);
}

2️⃣ BFS (Breadth First Search, 너비 우선 탐색)

• 같은 레벨의 노드를 먼저 탐색한 후, 다음 레벨로 이동.
• 예시: 최단 거리 찾기 (네비게이션, AI 경로 탐색).

function bfs(root) {
    let queue = [root];
    while (queue.length) {
        let node = queue.shift();
        console.log(node.value);
        if (node.left) queue.push(node.left);
        if (node.right) queue.push(node.right);
    }
}

---

마무리

1️⃣ 트리는 부모-자식 관계를 가지는 계층적 자료구조이다.
2️⃣ 이진 탐색 트리(BST)는 검색이 빠른 트리 구조이다.
3️⃣ DFS / BFS 탐색 알고리즘이 있다 (미로 찾기, AI 등에서 활용).
4️⃣ 트리는 파일 시스템, 데이터베이스, AI, 검색 엔진 등 실생활에서 다양하게 활용된다.