비선형 자료구조 - 1. 트리

트리(Tree)

 

노드와 간선(Edge)으로 이루어진 자료구조로 순환(Cycle)이 없는 그래프의 일종입니다.

 

보통 계층 구조를 나타낼 때 사용합니다.

 

 

트리의 구조

 

출처 : 파이썬 알고리즘 인터뷰

 

• 노드(Node) : 트리 구조의 단위
  • 루트 노드(Root Node) : 부모가 없는 최상위 노드
  • 리프 노드(Leaf Node) : 자식이 없는 최하위 노드 (= 단말 노드)
  • 부모 노드(Parent Node)
  • 자식 노드(Child Node)
  • 형제 노드(Sibling Node) : 같은 부모를 가지는 노드들
  • 내부 노드(Internal Node) : Leaf를 제외한 모든 노드
• 간선(Edge) : 노드 간의 연결선 (= link, branch)
• 깊이(Depth) : Root 에서 어떤 노드까지의 간선 수
• 레벨(Level) : 트리의 특정 깊이를 가지는 노드 집합
• 높이(Height) : 트리에서 가장 큰 레벨 값
• 크기(Size) : 자신을 포함한 자식 노드의 개수
• 차수(Degree) : 각 노드가 지닌 가지의 수
• 트리의 차수 : 트리의 최대 차수

 

트리의 특징

 

• 하나의 노드에서 다른 노드로 이동하는 경로는 유일합니다.
• 노드가 N개인 트리의 간선 수는 N-1 개
• 순환이 존재하지 않습니다.
• 모든 노드들은 서로 연결되어 있습니다.
• 하나의 간선을 끊으면 2개의 서브 트리로 분리됩니다.

 

 

트리의 종류

이진 트리(Binary Tree)

 

이진 트리는 부모 노드가 최대 2개의 자식 노드를 가지는 트리를 뜻합니다.

자식 노드들은 좌·우가 구분되며 서로 위치가 바뀌면, 서로 다른 트리로 여겨집니다.

 

이진 트리는 다음과 같은 종류가 있습니다.

 

포화 이진 트리 (Perfect Binary Tree).

 

모든 리프 노드의 높이가 같고 리프 노드가 아닌 노드들이 모두 2개의 자식을 갖는 트리입니다.

쉽게 말해, 모든 레벨에 모든 노드들이 채워져있는 형태입니다.

 

포화 이진 트리의 노드 수는 2^(높이+1) - 1 개입니다.

 

ex. 위의 이미지에서 최대 높이는 4이므로 2^4 - 1 = 15개

 

노드가 N개 일 때, 높이는 logN입니다.

 

 

완전 이진 트리 (Complete Binary Tree)

 

모든 리프 노드의 높이가 최대 1차이 나고, 모든 노드의 오른쪽 자식이 있으면 왼쪽 자식이 있는 트리입니다.

쉽게 말해서 마지막 레벨을 제외하고 모든 노드들이 채워져있는 형태입니다.

 

Binary Heap을 만들 때 사용합니다.

 

노드가 N개 일 때, 높이는 logN입니다.

 

 

정 이진 트리 (Full Binary Tree)

 

모든 노드가 자식 노드를 모두 가지고 있던가(2개) 모두 없는(0개) 형태의트리입니다.

 

리프 노드의 개수는 내부 노드의 개수 + 1개 입니다.

 

 

편향 트리 (Skewed Binary Tree, 사향 트리)

 

한쪽으로 기울어진 트리로 연결 리스트와 성능이 동일합니다.

 

 

균형 이진 트리 (Balanced Binary Tree)

 

출처 : https://yoongrammer.tistory.com/69

 

모든 노드의 좌우 서브 트리 높이가 1이상 차이 나지 않는 트리입니다.

 

알고리즘을 풀 때 이진 트리를 사용할 일이 있다면, 최대한 균형 이진트리를 유지하는게 탐색 속도가 빠릅니다.

 

 

이진 트리의 순회

순회란 모든 노드를 빠뜨리지거나 중복하지 않고 모두 방문하는 것을 의미합니다.

 

순회는 다음과 같은 방법들이 있습니다.

 

DFS (Depth-First Search)

Pre-Order(전위 순회)

 

출처 : https://www.jiwon.me/binary-tree-traversal/

부모 노드 -> 왼쪽 노드 -> 오른쪽 노드 순서로 순회하는 방법입니다.

 

 

In-Order (중위 순회)

 

출처 : https://www.jiwon.me/binary-tree-traversal/

왼쪽 노드 -> 부모 노드 -> 오른쪽 노드 순으로 순회가 이루어지는 방법입니다.

Post-Order(후위 순회)

 

출처 : https://www.jiwon.me/binary-tree-traversal/

왼쪽 노드 -> 오른쪽 노드 -> 부모 노드 순서로 순회가 이루어지는 방법입니다.

 

 

BFS (Breadth-First Search)

 

출처 : https://www.jiwon.me/binary-tree-traversal/

BFS의 경우, 레벨 순회라고도 불립니다.

위쪽 레벨부터 왼쪽 노드 -> 오른쪽 노드 순으로 순회가 이루어집니다.

 

BFS는 보통 Queue 자료구조를 이용합니다.

 

 

프로그래밍 언어에서 구현

Java

public class ArrayBinaryTree {
   char[] arr;

   public ArrayBinaryTree(char[] data) {
      this.arr = data.clone();
   }

   // 전위 순회
   public void preOrder(int idx) {
      int left = idx * 2 + 1;
      int right = idx * 2 + 2;

      System.out.printf("[%s] ", arr[idx]);

      if (left < arr.length) {
         preOrder(left);
      }

      if (right < arr.length) {
         preOrder(right);
      }
   }
   // 중위 순회
   public void inOrder(int idx) {
      int left = idx * 2 + 1;
      int right = idx * 2 + 2;

      if (left < arr.length) {
         inOrder(left);
      }

      System.out.printf("[%s] ", arr[idx]);

      if (right < arr.length) {
         inOrder(right);
      }
   }
   // 후위 순회
   public void postOrder(int idx) {
      int left = idx * 2 + 1;
      int right = idx * 2 + 2;

      if (left < arr.length) {
         postOrder(left);
      }

      if (right < arr.length) {
         postOrder(right);
      }

      System.out.printf("[%s] ", arr[idx]);
   }

   public static void main(String[] args) {
      char[] arr = new char[]{'A','B','C','D','E','F','G','H','I','J'};

      ArrayBinaryTree tree = new ArrayBinaryTree(arr);

      System.out.println("======전위 순회======");
      tree.preOrder(0);

      System.out.println("\n======중위 순회======");
      tree.inOrder(0);

      System.out.println("\n======후위 순회======");
      tree.postOrder(0);

   }


}