트리 - Tree

트리는 계층형 트리 구조를 시뮬레이션 하는 추상 자료형으로, 루트값과 부모-자식 관계의 서브트리로 구성되며, 서로 연결된 노드의 집합이다.

트리는 하나의 뿌리(Root)에서 위로 뻗어나가는 형상처럼 생겨서 ‘트리(나무)’라는 명칭이 붙었다.

실생활에서 볼 수 있는 트리구조에는 족보, 회사의 조직도 등이 있다.

좀더 중요한 트리의 속성은 재귀로(recursively) 정의된 자기 참조(self-Referential) 자료구조라는 점이다. 즉. 자식도 , 자식의 자식도, 모두 트리이며, 트리가 여러개 쌓여 큰 트리가 된다.

이러한 재귀적 특성 덕에 트리에서는 재귀 순회가 더 자연스러운 편이다.

트리의 각 명칭

• Root node: 트리가 시작되는 노드
• Edge: 간선
• Child node: 부모 노드에 간선으로 연결된 자식 노드
• Leaf node: 가장 하위 노드 (가장 자식 세대 노드)
• Height: 현재 위치에서 Leaf node까지의 거리
• Depth: Root 노드에서부터 현재 노드까지의 거리

• 좀 더 구체화된 용어 정의
  • 노드(node): 트리를 구성하는 기본 원소
    • 루트 노드(root node/root): 트리에서 부모가 없는 최상위 노드, 트리의 시작점
    • 부모 노드(parent node): 루트 노드 방향으로 직접 연결된 노드
    • 자식 노드(child node): 루트 노드 반대방향으로 직접 연결된 노드
    • 형제 노드(siblings node): 같은 부모 노드를 갖는 노드들
    • 리프 노드(leaf node/leaf): 루트 노드를 제외한 차수가 1인 정점을 뜻한다. 쉽게 말해 자식이 없는 노드. 단말 노드라 부르기도 한다.
  • 경로(path): 한 노드에서 다른 한 노드에 이르는 길 사이에 있는 노드들의 순서
  • 길이(length): 출발 노드에서 도착 노드까지 거치는 간선의 개수
  • 깊이(depth): 루트 경로의 길이
  • 레벨(level): 루트 노드(level=0)부터 노드까지 연결된 간선 수의 합
  • 높이(height): 가장 긴 루트 경로의 길이
  • 차수(degree): 각 노드의 자식의 개수
  • 트리의 차수(degree of tree): 트리의 최대 차수 = max[deg1, deg2, ..., degn]
  • 크기(size): 노드의 개수
  • 너비(width): 가장 많은 노드를 갖고 있는 레벨의 크기
  • 내부 정점(internal vertex): 차수가 2 이상인 정점을 뜻한다.
  • 포레스트(forest): 서로 독립인 트리들의 모임이다.
  • 방향 트리(directed tree): 방향을 무시하고 생각했을 때 트리인 유향 그래프는 방향 트리이다. 자료구조의 트리는 방향 트리의 일종이다.
   

트리 구조

그래프 VS 트리

“트리는 순환구조를 갖지 않는 그래프입니다.”

그래프와 트리의 차이점에서 핵심은 순환구조가 아니라는데 있다.

트리는 특수한 형태의 그래프의 일종이며, 크게 그래프의 범주에 포함된다.

하지만, 트리는 그래프와 달리 어떠한 경우에도 한번 연결된 노드가 다시 연결되는 법이 없다.

이외에도 단방향(Uni-Directional), 양방향(Bi-Directional)을 모두 가리킬 수 있는 그래프와 달리, 트리는 부모 노드에서 자식 노드를 가리키는 단방향뿐이다.

그뿐만 아니라 트리는 하나의 부모 노드를 갖는 다는 차이점이 있으며, 루트 또한 하나여야 한다.

• 각각 왜 트리가 아닌가?
•  정답
  • 2)는 부모가 둘
  • 3)서로 연결되어 있지 않으며, 루트가 둘
  • 1)은 순환구조

이진 트리

“이진 트리요?”

우리는 “트리”하면, “이진트리”가 떠오르는데, 그것이 뭔지 정확히는 알지 못한다.

왜냐면, “왜”와 “정의” 두가지를 놓치고 있기 때문이다.

트리중에서 가장 널리 사용되는 트리 자료구조는 이진 트리와 이진 탐색 트리(Binary Search Tree)다.

먼저, 각 노드가 m개 이하의 자식을 갖고 있으면, m-ary 트리(다항 트리, 혹은 다진트리)

여기서 m=2이면, 즉, 모든 노드의 차수(자식의 개수)가 2이하이면, 특별히 이진 트리(Binary Tree)라고 구분해서 부른다.

2진 트리는 매우 단순한 형태로, 다진 트리에 비해 훨씬 간결하며 여러가지 알고리즘을 구현하는 일도 좀더 간단하게 처리할 수 있어서, 대체로 트리라고 하면 특별한 경우가 아니고서는 대부분 이진 트리를 일컫는다.

이진 트리 유형

• 정 이진 트리(Full Binary Tree): 모든 노드가 0개 또는 2개의 자식 노드를 갖는다.
• 완전 이진 트리(Complete Binary Tree): 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있으며, 마지막 레벨의 모든 노드는 가장 왼쪽부터 채워져 있다.
• 포화 이진 트리(Perfect Binary Tree): 모든 노드가 2개의 자식 노드를 가지고 있으며, 모든 리프노드가 동일한 깊이 또는 레벨을 가진다. ‘perferct’라는 수식어 답게, 가장 완벽한 유형의 트리이다.