[정글 WEEK03_알고리즘] 개발 일지 - 트리

정의

n개의 노드(Node)와 n-1개의 간선(Edge)을 갖는 비순환 방향 연결 그래프

 * 전통적인 수학에서는 무방향 그래프로, 컴퓨터공학 분야에서는 방향 그래프로 간주한다.

 

❗️아래 조건을 모두 만족해야 트리라고 할 수 있다.

1) 모든 노드가 하나로 연결되어있어야 하며,
2) 사이클이 없어야 하고,
3) 항상 '간선의 수'가 '노드 수 - 1'개여야 한다.

 

헷갈리는 용어

 - 레벨(level): 현재 노드가 루트에서 얼마나 멀리 떨어져 있는지 

 - 높이(height): 루트에서 가장 멀리 있는 리프까지의 거리 (= 리프 레벨의 최댓값)

 

분류

1. Binary Tree

 - Perfect Binary Tree

 - Strict Binary Tree

 - Complete Binary Tree

 - Binary Search Tree

 - AVL Tree

 - Red-Black Tree

2. Self-Balancing Search Tree

 [Binary]

    - AVL Tree

    - Red-Black Tree

  [M-ary]

    - B-Tree

    - B+ Tree

    - B* Tree

    - 2-3 Tree

3. MST(Minimum Spanning Tree)

4. Trie

---

1. Binary Tree

   부모 노드가 최대 2개의 자식 노드를 갖는 트리. 두 자식 중 하나 또는 두 자식 모두 없는 부모 노드가 있어도 됨

   🌲 Perfect  Binary Tree

      모든 내부 노드는 자식이 정확히 2개이고, 모든 리프 노드는 동일한 레벨에 존재하는 이진 트리

Perfect Binary Tree

   🌲 Strict Binary Tree

      모든 노드가 0 또는 2개의 자식 노드를 가지는데, 리프 노드가 다 채워질 필요는 없음

Strict Binay Tree1

   🌲 Complete Binary Tree

      루트부터 아래 방향으로 모든 노드가 가득 차있고, 같은 레벨에서는 왼쪽부터 오른쪽 순서로 노드가 채워지는 이진 트리

      단, 마지막 레벨은 왼쪽부터 오른쪽까지 채우되, 끝까지 채우지 않아도 됨

      힙(Heap) 자료구조가 Complete Binary Tree로 구현됨 

Complete Binary Tree

   🌲 Binary Search Tree

      왼쪽 자식 값 < 루트 값 < 오른쪽 자식 값의 관계를 모든 서브트리가 만족하는 이진 트리

      중위 순회 시 오름차순으로 정렬된 결과가 나옴

      탐색, 삽입, 삭제가 평균적으로 O(logN) 시간에 수행됨

      균형이 깨질 경우 성능이  O(n)까지 저하될 수 있음

BInary Seach Tree

 

2.  Self-Balancing Search Tree

   삽입/ 삭제 시 트리의 균형이 자동으로 조정되어 항상 O(log n)의 성능을 유지하는 고성능 BST

    [Binary]

       이진 탐색 트리의 특성을 가지면서 삽입/삭제 후 균형 유지 

        🌲 AVL Tree

           모든 노드의 왼쪽 서브트리와 오른쪽 서브트리의 레벨 차이가 항상 1 이하가 되도록 유지

           균형 조건이 엄격해서 탐색 성능이 매우 좋지만, 삽입/삭제 시 회전이 많아질 수 있음

AVL Tree

        🌲 Red-Black Tree

           약간의 불균형을 허용하지만 최악의 경우에도 O(log n) 보장

           삽입/삭제 시 빨강/검정 노드 색상 규칙을 통해 균형 유지

           Java TreeMap, C++ STL의 map/set 등에서 사용됨

Red-Black Tree

     [M-ary]

        한 노드가 다수개의 자식을 가지면서 삽입/삭제 후 균형 유지

        디스크 기반 시스템, 데이터베이스 인덱스에서 데이터를 효율적으로 저장하고 검색하기 위해 설계됨

         🌲 B-Tree

           노드에 여러 개의 키와 자식을 저장할 수 있어 높이를 낮추고 디스크 접근 최소화 가능

           데이터베이스, 파일 시스템 등 블록 단위 저장이 중요한 환경에서 주로 사용

 

           [Search Operation] - 120을 찾아라!

         🌲 B+ Tree

            B-Tree의 변형으로 리프 노드에만 실제 데이터를 저장하고 다른 노드들은 인덱스 역할만 수행

            리프 노드가 연결 리스트처럼 이어져있어서 범위 검색에 매우 효율적

            대부분의 데이터베이스 인덱스가 B+Tree 기반

         🌲 B* Tree

             B+ Tree에서 더 많은 키를 담기 위해 노드 분할 전 형제 노드로 분산하는 형태로, 노드 활용률 극대화

 

          🌲 2-3 Tree

             각 노드는 2-node(2-node는 1개의 키, 2개의 자식) 또는 3-node(3-node는 3개의 키, 3개의 자식) 타입 중 하나.

             모든 리프 노드의 깊이가 동일하며,

             2-3 Tree를 이진 트리로 변환한 형태가 레드블랙 트리라고도 할 수 있음

             (2-node → 1 블랙 노드, 3-node → 블랙 노드에 레드 노드가 자식으로 붙은 형태)

 

2 Node - 3 Node

 

 

3. MST(Minimum Spanning Tree, 최소 신장 트리)

    신장 트리는 무방향 연결 가중치 그래프가 있을 때 모든 노드를 포함하면서 사이클이 존재하지 않는 부분 트리

    최소 신장 트리는 신장 트리의 모든 정점을 최소 비용으로 연결한 결과

 

    최소 신장 트리를 구현하는 대표 알고리즘:

     - Kruskal(간선을 가중치 순으로 정렬 +  서로소 집합 사용)

     - Prim(우선순위 큐 기반으로 점진적 확장)

    

      [Kruskal 알고리즘]

       * 서로소 집합(Union-Find)를 통해 사이클을 방지해 MST를 구성

edges.sort()  # 비용 순으로 정렬

for cost, a, b in edges:
    if find(a) != find(b):      # 사이클이 발생하지 않으면
        union(a, b)             # 집합을 합쳐서 트리에 포함
        total_cost += cost

       1. 간선 데이터를 비용에 따라 오름차순으로 정렬

       2. 간선을 하나씩 확인하면서 현재의 간선이 사이클을 발생시키는지 확인

          2-1) 사이클이 발생하지 않는 경우 최소 신장 트리에 포함 

          2-2) 사이클이 발생하는 경우 최소 신장 트리에 미포함

       3. 모든 간선에 대해서 2번 과정을 반복

 

 

 

4. Trie

    문자열을 저장하고 검색하기 위한 트리 기반 자료구조

    각 노드가 하나의 문자를 나타내며, 루트부터 자식 노드까지 문자열의 공통 접두사 공유

    자식 방향으로 차례대로 따라가면서 문자열 구성

    문자열의 공통 접두사를 공유하기 때문에 효율적인 검색이 가능하며, 자동완성, 사전 구조에 사용됨 

Trie

 

 

 

출처:

https://www.geeksforgeeks.org/introduction-of-b-tree-2/?ref=header_outind

Introduction of B-Tree - GeeksforGeeks

 

이미지 출처:

https://www.geeksforgeeks.org/types-of-binary-tree/

Types of Binary Tree - GeeksforGeeks

https://iq.opengenus.org/strictly-binary-tree/

Strictly Binary Tree