트리(Tree)

정의

• 루트 노드(Root Node)라고 불리는 최상위 노드를 시작으로 여러 개의 자식 노드들이 나무 가지처럼 연결된 구조이다.
• 트리는 그래프의 한 종류로 최소 연결 트리라고도 불린다.
• 방향성이 있는 비순환 그래프의 한 종류이다.

특징

• 단순한 나열이 아닌 부모-자식 형태의 구조이며, 모든 자식 노드는 하나의 부모 만을 갖는다.

• 트리는 트리 내에 다른 하위 트리가 있고, 그 하위 트리 안에는 또 다른 하위 트리가 있는 재귀적 자료구조이기도 하다.

• 노드가 N개인 트리는 항상 N-1개의 간선(edge)을 가진다. 즉, 간선은 항상 (정점의 개수 - 1) 만큼을 가진다.

• 각 노드는 어떤 자료형으로도 표현이 가능하다.

• 데이터를 순차적으로 저장하지 않는다. → 비선형 자료구조이다.

• 사이클이 존재하지 않는다. (임의의 두 노드간 경로가 유일하며, 하나의 연결 그래프, 방향, 화살표가 없음.)

• 컴퓨터의 directory 구조가 트리 구조의 대표적 예이다.

  

용어

• 루트 노드(root node): 부모가 없는 노드, 트리는 하나의 루트 노드만을 가진다.
• 단말 노드(leaf node): 자식이 없는 노드, ‘말단 노드’ 또는 ‘잎 노드’라고도 부른다.