🌳 트리(Tree)와 집합(Set)

1️⃣ 트리(Tree)란?

✅ 트리의 개념

트리는 계층적인 구조를 가진 비선형 자료구조입니다. 일반적으로 부모-자식 관계를 가지며, 루트 노드(Root Node)에서 시작해 여러 개의 자식 노드(Child Node)로 분기된다.

✅ 트리의 주요 특징

• 계층적 구조: 부모-자식 관계를 가짐.
• 사이클 없음: 트리는 비순환 그래프(Directed Acyclic Graph, DAG).
• 노드(Node)와 간선(Edge)으로 구성: 한 노드는 여러 개의 자식을 가질 수 있음.
• 트리는 하나의 루트(Root) 노드에서 시작: 모든 노드는 하나의 부모를 가짐 (예외: 루트 노드)
• 트리의 깊이(Depth)와 높이(Height) 개념 중요
  • 깊이(Depth): 루트 노드에서 특정 노드까지의 거리
  • 높이(Height): 특정 노드에서 가장 깊은 리프 노드까지의 거리

✅ 트리 용어 정리

용어	설명
루트(Root) 노드	트리의 최상위 노드 (부모가 없음)
부모(Parent) 노드	다른 노드를 가리키는 노드
자식(Child) 노드	부모 노드에서 연결된 노드
형제(Sibling) 노드	같은 부모를 가진 노드들
리프(Leaf) 노드	자식이 없는 노드
서브트리(Subtree)	하나의 노드를 기준으로 형성된 작은 트리
깊이(Depth)	루트에서 특정 노드까지의 거리
높이(Height)	특정 노드에서 가장 깊은 노드까지의 거리
차수(Degree)	특정 노드가 가진 자식 노드의 개수

✅ 트리의 종류

1. 일반 트리 (General Tree)

   • 자식 노드의 개수에 제한이 없는 트리.

2. 이진 트리(Binary Tree)

   • 각 노드가 최대 두 개의 자식을 가질 수 있는 트리.
   • 예제 코드 (JavaScript):

   class Node {
       constructor(value) {
           this.value = value;
           this.left = null;
           this.right = null;
       }
   }
   
   const root = new Node(1);
   root.left = new Node(2);
   root.right = new Node(3);

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

   • 왼쪽 자식 노드는 부모보다 작고, 오른쪽 자식 노드는 부모보다 큼.
   • 예제 코드 (JavaScript):

   class BST {
       constructor(value) {
           this.value = value;
           this.left = null;
           this.right = null;
       }
   
       insert(value) {
           if (value < this.value) {
               if (this.left === null) {
                   this.left = new BST(value);
               } else {
                   this.left.insert(value);
               }
           } else {
               if (this.right === null) {
                   this.right = new BST(value);
               } else {
                   this.right.insert(value);
               }
           }
       }
   }
   
   const root = new BST(10);
   root.insert(5);
   root.insert(15);

4. 균형 트리 (Balanced Tree)

   • AVL 트리: 노드의 균형을 유지하기 위해 회전 연산(Rotation)을 수행하는 트리.
   • 레드-블랙 트리 (Red-Black Tree): 삽입 및 삭제 연산 시 균형을 유지하는 이진 탐색 트리.

5. 힙(Heap) 트리

   • 최대 힙(Max Heap) → 부모 노드가 항상 자식보다 큼.
   • 최소 힙(Min Heap) → 부모 노드가 항상 자식보다 작음.

✅ 트리 순회 방법 (Tree Traversal)

트리의 노드를 탐색하는 방법에는 DFS(깊이 우선 탐색)과 BFS(너비 우선 탐색)이 있다.

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

   • 전위 순회 (Preorder Traversal): 루트 → 왼쪽 → 오른쪽
   • 중위 순회 (Inorder Traversal): 왼쪽 → 루트 → 오른쪽
   • 후위 순회 (Postorder Traversal): 왼쪽 → 오른쪽 → 루트

   function inorderTraversal(node) {
       if (node !== null) {
           inorderTraversal(node.left);
           console.log(node.value);
           inorderTraversal(node.right);
       }
   }
   inorderTraversal(root);

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

   • 큐(Queue)를 이용하여 레벨 단위로 탐색함.

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

✅ 트리의 활용 예시

• 파일 시스템 (디렉토리 구조)
• 데이터베이스 인덱싱 (B-Tree, B+Tree)
• HTML DOM 구조
• AI, 게임에서의 의사결정 트리
• 네트워크 라우팅 (최단 경로 탐색)

---

3️⃣ 집합(Set)의 내부 동작

✅ JavaScript의 Set 객체 내부 원리

• JavaScript의 Set은 해시 테이블(Hash Table)을 기반으로 동작한다.
• 해시 테이블은 키-값(Key-Value) 구조를 사용하여 O(1) 시간 복잡도로 데이터를 찾을 수 있다.
• 즉, Set.has(value) 연산은 매우 빠르게 수행된다.

const mySet = new Set();
mySet.add(1);
mySet.add(2);
mySet.add(3);
console.log(mySet.has(2)); // true
console.log(mySet.size); // 3

✅ Set을 이용한 중복 제거

const arr = [1, 2, 2, 3, 4, 4, 5];
const uniqueArr = [...new Set(arr)];
console.log(uniqueArr); // [1, 2, 3, 4, 5]

---

트리와 집합의 기본적인 개념은 직관적이라 쉬웠지만.. 조금만 파고들어가니 아니나 다를까 이건 또 뭔소리인가 싶었다.

트리는 예를 들자면 족보나 폴더 구조를 떠올려보면 쉽게 이해 할 수 있고 집합은 쇼핑할 때 장바구니나 누군가의 버킷리스트를 떠올려보면 쉽게 이해 할 수 있다.