[자료구조] Tree

1. Tree 란?

그래프의 일종

• 노드들과 이 노드들을 연결하는 엣지들로 구성된 일종의 그래프

 

순환이 없는 연결 그래프

• 모든 노드가 연결되어 있는 구조
• 어떤 두 노드를 선택해도 경로는 항상 단 하나만 존재

 

계층형 구조

• 루트노드부터 시작해서 여러 개의 하위 노드로 분기됩니다.
• 각 노드는 0개 이상의 자식 노드를 가질 수 있습니다.

 

예시

• 파일 시스템 (디렉토리)

 

용어

         A (Root, Depth: 0, Height: 2, Level: 1)
       /   \
      /     \
     B       C (Node, Depth: 1, Height: 1, Level: 2)
    / \     / \
   D   E   F   G (Leaf, Depth: 2, Height: 0, Level: 3)

Node	트리를 구성하는 기본단위 입니다.
Root	트리의 최상위 노드입니다.
Leaf	자식노드가 없는 노드입니다.
SubTree	특정 노드와 그 노드의 모든 자손 노드로 구성된 트리입니다. (재귀적인 구조)
Level	트리에서 같은 깊이의 노드들의 집합을 의미합니다.
Depth	루트 노드에서 특정 노드까지 도달하기 위한 엣지의 수입니다.
Height	특정 노드에서 가장 멀리 떨어진 리프 노드까지의 엣지의 수입니다.

 

2. 탐색

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

• 주어진 노드에서 시작해 인접한 모든 노드를 먼저 방문하고, 다시 해당 노드의 자식 노드들을 방문하는 방식입니다.
• 큐(Queue)를 사용하여 구현할 수 있습니다.

 

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

• 시작노드로부터 깊이를 따라 끝까지 탐색합니다.
• 더이상 갈 곳이 없으면 가장 마지막에 만났던 갈림길에 있는 노드로 돌아와 다음 경로를 탐색하는 방식입니다.
• 재귀 호출이나 스택(Stack)을 사용하여 구현할 수 있습니다.

 

3. 순회

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

전위 순회 (Preorder Traversal)

• 트리의 노드를 방문하는 순서는 "루트(자신) -> 왼쪽 서브트리 -> 오른쪽 서브트리" 입니다.
• A -> B -> D -> E -> C -> F -> G

 

중위 순회 (Inorder Traversal)

• 트리의 노드를 방문하는 순서는 "왼쪽 서브트리 -> 루트(자신) -> 오른쪽 서브트리" 입니다.
• D -> B -> E -> A -> F -> C -> G
  • 정렬된 순서의 출력을 얻을 수 있습니다.

 

후위 순회 (Postorder Traversal)

• 트리의 노드를 방문하는 순서는 "왼쪽 서브트리 -> 오른쪽 서브트리 ->  루트(자신)" 입니다.
• D -> E -> B -> F -> G -> C -> A

 

3. 종류

이진 트리

• 각 노드가 최대 두 개의 자식노드를 가지는 트리입니다.

 

포화 이진 트리 (perfect binary tree)

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

• 모든 레벨이 완전히 채워져 있는 이진트리입니다.

 

완전 이진 트리 (complete binary tree)

    A
   / \
  B   C
 / \ / 
D  E F

• 마지막 레벨을 제외한 모든 레벨이 모두 차있는 이진트리입니다.
• 마지막 레벨의 노드들은 왼쪽부터 채워져 있습니다.

 

균형 이진 트리 (balanced binary tree)

    A
   / \
  B   C
 /     \
D       E

• 이진 트리에서 모든 리프노드까지의 거리가 거의 동일한 트리입니다.

 

다진트리

• 각 노드가 세 개의 이상의 자식노드를 가지는 트리입니다.

 

4. 사례

DOM	웹 페이지의 구조를 표현하는데 사용되는 트리구조입니다. HTML, XML 등에서 사용됩니다.
AST	프로그램의 구조를 표현하기 위한 트리입니다. 컴파일러나 인터프리터에서 소스코드를 분석할 때 사용됩니다.
Search Tree	효율적인 검색, 삽입, 삭제 연산을 지원하기 위한 트리구조 입니다.

 

 

 

출처

• Wiki - Tree