Tree

작성일 | In

[자료구조] Tree

트리란?

  • 최대 하나의 부모를 갖고, 여러 개의 자식 노드를 갖는 자료구조
  • 노드와 간선(edge)으로 이루어져 있다.
  • root 노드를 제외한 모든 노드는 최대 하나의 부모만을 갖는다는 조건에 의해, 트리는 아래와 같은 특징들을 갖는다.
    • 임의의 노드에서 다른 노드로 가는 경로(path)가 반드시 존재한다.
    • 트리 내의 사이클(cycle)이 존재하지 않는다.
    • 트리 내의 임의의 간선 하나를 제거하면, 트리는 2개로 나뉜다.
    • 노드 개수를 V라 하고, 간선의 개수를 E라 할 때, E = V-1 이 성립한다.


트리의 구성 요소

트리 구성 출처 : https://ratsgo.github.io/data structure&algorithm/2017/10/21/tree/

노드

트리 내의 노드의 종류에는 총 세 가지가 있다.

  • root
    트리의 시작점이 되는 노드. 트리 내에서 유일하게 부모 노드가 없는 노드이다.
  • internal
    root, leaf 사이에 있는 노드들을 통칭한다.
  • leaf
    자식 노드가 없는 노드를 의미한다.

그 외 용어

  • path
    하나의 노드에서 다른 노드로 가는 경로를 의미한다.
  • depth(level)
    어느 노드가 root 노드에서부터 떨어진 거리를 의미한다. root 노드의 depth는 0이다.
  • height
    트리의 높이. root 노드에서부터 가장 멀리 떨어진(거쳐야 하는 간선의 개수가 많은) 노드 사이의 간선의 개수를 의미한다.


이진 트리

트리의 종류 중, 자식 노드를 최대 2개만 갖는 트리를 이진 트리(binary tree)라고 한다.
이진 트리는 힙, 이진 탐색 등 여러 자료구조 및 알고리즘에서 유용하게 사용된다.

이진 트리의 종류

정이진트리 (Full Binary Tree)

leaf노드를 제외한 모든 노드들이 자식 노드를 2개 혹은 0개만 갖는 이진트리이다.
정이진트리

정이진트리의 각 depth의 노드 개수는 $2^{depth}$ 개다.
따라서 정이진트리의 height가 h일 때, 정이진트리 전체 노드의 개수는
$2^0 + 2^1 + … + 2^h = 2^{h+1} - 1$개다.

완전이진트리 (Complete Binary Tree)

자식 노드가 왼쪽부터 쌓이고, 마지막 depth를 제외한 나머지 depth의 노드들이 전부 존재하는 이진트리이다.
완전이진트리

위 그림에서 A는 완전이진트리이고, B는 오른쪽 노드가 먼저 채워진 부모노드가 존재하기 때문에 완전이진트리가 아니다.
보통 힙(heap)을 완전이진트리를 이용하여 구현한다.
완전이진트리는 왼쪽 자식부터 채워지기 때문에, 1차원 배열을 이용하여 구현할 수 있다. 인덱스 k의 왼쪽 자식은 2k, 오른쪽 자식은 2k+1로 찾아낼 수 있다. 이러한 규칙을 이용하기 위해서 보통 0번째 인덱스는 사용하지 않고, 1번째 인덱스를 root 노드로 취급한다.

균형이진트리 (Balanced Binary Tree)

모든 노드의 depth 차이가 최대 1인 이진트리이다. 따라서 균형이진트리의 노드의 개수가 주어지면 이를 통해 해당 트리의 height를 추측할 수 있다. (노드 개수가 n개일 때, 균형이진트리의 height는 $log^n$)
depth말고 root 노드를 기준으로 왼쪽 subtree와 오른쪽 subtree의 노드 개수 차이로 균형이진트리 여부를 정의하는 관점도 있다고 한다.


트리의 순회

트리를 순회하는 방법에는 세 가지가 있다. 예시 트리를 각 순회방법으로 순회하면 어떤 순으로 값이 출력되는지 함께 알아보자. 트리 예제

preorder

방문한 노드를 기점으로 노드 -> 왼쪽 서브트리 -> 오른쪽 서브트리 순으로 순회한다.
| 8,3,1,6,4,7,10,14,13

inorder

방문한 노드를 기점으로 왼쪽 서브트리 -> 노드 -> 오른쪽 서브트리 순으로 순회한다.
| 1,3,4,6,7,8,10,13,14

postorder

방문한 노드를 기점으로 왼쪽 서브트리 -> 오른쪽 서브트리 -> 노드 순으로 순회한다.
| 1,4,6,7,3,13,14,10,8

각 순회 방법에 따라 루트 노드(8)가 언제쯤 방문되는지를 보면 각 순회 방법의 성격을 알 수 있다.
preorder는 첫 번째로 방문되고, inorder는 중간쯤, postorder는 마지막에 루트 노드가 방문된다.

0%