[크래프톤 정글 ] 트리 란 ?

트리(Tree)의 기본 개념과 예시

트리(Tree)는 계층적인 관계를 표현하는 데이터 구조이다. 트리는 노드(Node)와 간선(Edge)으로 이루어지며, 데이터 구조나 알고리즘에서 중요한 역할을 한다.

1. 노드(Node):
   • 트리의 기본 구성 요소이다. 각 노드는 데이터를 포함하고, 다른 노드들과 연결될 수 있다. 노드의 개수는 트리의 크기를 나타낸다.
2. 루트 노드(Root Node):
   • 트리의 최상단에 위치한 노드이다. 부모 노드가 없는 유일한 노드로, 모든 노드는 루트 노드로부터 시작되는 경로를 가진다.
3. 부모 노드(Parent Node):
   • 자식 노드를 직접 연결하는 상위 노드이다. 부모 노드는 자식 노드의 상위에 위치하며, 두 노드를 연결하는 간선으로 표시된다.
4. 자식 노드(Child Node):
   • 특정 노드에 의해 연결된 하위 노드이다. 부모 노드와 자식 노드는 간선으로 연결된다.
5. 형제 노드(Sibling Node):
   • 동일한 부모를 공유하는 노드이다. 형제 노드들은 같은 부모 노드로부터 연결된 여러 자식 노드들이다.
6. 잎 노드(Leaf Node):
   • 자식 노드가 없는 말단 노드이다. 트리의 끝을 의미하며, 더 이상 하위 노드로 확장되지 않는 노드이다.
7. 간선(Edge):
   • 두 노드를 연결하는 선이다. 간선은 부모와 자식 노드를 이어주며, 트리의 구조를 형성한다.

트리의 종류와 예시

1. 이진 트리(Binary Tree):
   • 각 노드가 최대 두 개의 자식을 가지는 트리이다. 왼쪽 자식과 오른쪽 자식으로 구분된다.
   • 예시:

            A
           / \
          B   C
         / \   \
        D   E   F

     • A는 루트 노드이고, B와 C는 A의 자식 노드이다.
     • D, E, F는 각각 B와 C의 자식 노드로, 각 노드가 최대 두 개의 자식을 가진다.
2. 완전 이진 트리(Complete Binary Tree):
   • 마지막 레벨을 제외한 모든 레벨이 꽉 차 있으며, 마지막 레벨의 노드들은 가능한 한 왼쪽부터 차례대로 배치된 트리이다.
   • 예시:

            A
           / \
          B   C
         / \  /
        D   E F

     • 마지막 레벨의 노드들이 가능한 왼쪽에 배치되어 있으며, 이진 트리의 모든 레벨이 가득 차 있다.
3. 포화 이진 트리(Full Binary Tree):
   • 모든 노드가 0개 또는 2개의 자식 노드를 가지는 트리이다.
   • 예시:

            A
           / \
          B   C
         / \  / \
        D   E F  G

     • 모든 노드가 자식 노드를 2개씩 가지거나(내부 노드), 자식 노드가 없는(잎 노드) 트리이다.
4. 균형 이진 트리(Balanced Binary Tree):
   • 트리의 모든 잎 노드가 루트에서 동일한 거리 내에 있는 트리이다.
   • 예시:

            A
           / \
          B   C
         / \  / \
        D   E F  G

     • 모든 잎 노드(D, E, F, G)가 루트 노드(A)로부터 동일한 거리에 있다.
5. 이진 탐색 트리(Binary Search Tree):
   • 왼쪽 자식 노드에는 부모 노드보다 작은 값이, 오른쪽 자식 노드에는 부모 노드보다 큰 값이 위치하는 트리이다.
   • 예시:

            10
           /  \
          5    15
         / \   / \
        3   7 12  18

     • 모든 노드의 왼쪽 서브트리에는 부모 노드보다 작은 값이, 오른쪽 서브트리에는 큰 값이 위치한다.
6. N-진 트리(N-ary Tree):
   • 각 노드가 최대 N개의 자식을 가질 수 있는 트리이다.
   • 예시:

            A
          / | \
         B  C  D
        /|  |\
       E F  G H

     • A는 3개의 자식을 가지고 있으며, B, C, D는 각각 2개의 자식을 가진다. 이 트리는 3진 트리(N=3)이다.
7. 트라이(Trie):
   • 문자열을 저장하는 데 최적화된 트리 구조이다. 각 노드는 하나의 문자를 나타내며, 여러 문자열을 같은 트리 내에서 관리할 수 있다.
   • 예시:

             ""
            /   \
           t     b
          /     / \
         o     a   e
        / \     \
       p   y     t
      /
     s

     • 이 트리는 "top", "toy", "bat", "be"와 같은 단어들을 저장한다. 각 경로는 하나의 단어를 나타낸다.

트리의 주요 연산

1. 탐색(Search):
   • 트리에서 특정 값을 찾는 작업이다.
   • 이진 탐색 트리에서는 일반적으로 O(log n)의 시간 복잡도를 가진다.
2. 삽입(Insertion):
   • 트리에 새로운 노드를 추가하는 작업이다.
   • 특정 위치(대개 리프 노드)에서 새로운 노드를 추가한다.
3. 삭제(Deletion):
   • 트리에서 특정 노드를 제거하는 작업 이다.
   • 노드를 삭제한 후, 트리의 구조를 유지하기 위해 재조정이 필요할 수 있다.
4. 순회(Traversal):
   • 트리의 모든 노드를 방문하는 과정.
   • 주로 세 가지 방법이 존재 :
     • 전위 순회(Pre-order Traversal): 루트 -> 왼쪽 -> 오른쪽
     • 중위 순회(In-order Traversal): 왼쪽 -> 루트 -> 오른쪽
     • 후위 순회(Post-order Traversal): 왼쪽 -> 오른쪽 -> 루트

트리의 활용 예

• 파일 시스템: 디렉토리 구조는 트리 구조로 표현된다.
• 컴퓨터 그래픽스: 장면 그래프(Scene Graph)나 뷰 계층(View Hierarchy) 등에서 트리를 사용한다.
• 네트워크 라우팅: 라우팅 테이블은 트리 구조로 되어 있으며, 빠른 탐색을 가능하게 한다.
• 데이터베이스 인덱스: B-트리와 같은 트리 구조는 데이터베이스에서 인덱스를 유지하는 데 사용 된다.
• 인공지능: 의사결정 트리(Decision Tree)와 같은 기법은 트리 구조를 이용해 결정을 내린다.

트리는 이러한 다양한 특성과 구조 덕분에 컴퓨터 과학의 많은 분야에서 중요한 역할을 한다.