트리 (자료 구조)

트리(tree, 문화어: 나무)란 그래프의 일종으로, 한 노드에서 시작해서 다른 정점들을 순회하여 자기 자신에게 돌아오는 순환이 없는 연결 그래프이다.

모델에 대해서는 트리 구조 (모델) 문서를 참고하십시오.

이진 트리

트리에서 최상위 노드를 루트 노드(root node 뿌리 노드^[*])라고 한다. 또한 노드 A가 노드 B를 가리킬 때 A를 B의 부모 노드(parent node), B를 A의 자식 노드(child node)라고 한다. 자식 노드가 없는 노드를 잎 노드(leaf node 리프 노드^[*]) 또는 말단 노드 (terminal node)라고 한다. 잎 노드가 아닌 노드를 내부 노드(internal node)라고 한다.

유향 트리(영어: directed tree)는 방향을 제거했을 때 트리가 되는 유향 그래프이다. 컴퓨터 과학에서는, 자료 구조의 일종인 트리는 일반적으로 유향 나무를 의미한다.

뿌리 트리

뿌리 트리의 예. 꼭짓점 R은 뿌리이다. 꼭짓점 V 바로 위에 있는 꼭짓점이 V의 부모이며, 아래 있는 두 꼭짓점이 V의 자식이다. V의 높이는 1이고, 깊이는 2이다. 그래프의 높이는 3이다.

뿌리 트리(영어: rooted tree)는 특정 꼭짓점 하나를 뿌리(root)로 가지는 트리이다. 뿌리 트리는 뿌리에서 출발해 잎으로 가는 방향으로 각 변에 자연스럽게 방향을 부여할 수 있다.

뿌리 트리에서 꼭짓점 ${\displaystyle v}$의 부모(영어: parent)는, 뿌리와 ${\displaystyle v}$를 잇는 경로 위의 꼭짓점 중에서 ${\displaystyle v}$와 연결되어 있는 꼭짓점이다. 따라서 뿌리를 제외한 모든 꼭짓점은 유일한 부모를 갖는다. 꼭짓점 ${\displaystyle v}$의 자식(영어: child)은 ${\displaystyle v}$를 부모로 갖는 꼭짓점이다. 따라서 꼭짓점의 자식은 여러 개일 수 있으며, 잎 꼭짓점은 자식을 갖지 않는다. 꼭짓점 ${\displaystyle v}$의 조상(영어: ascendant)은 ${\displaystyle v}$의 부모 또는 조상 관계에 있는 꼭짓점이다. 꼭짓점 ${\displaystyle v}$의 자손(영어: descendant)은 ${\displaystyle v}$의 자식 또는 자손 관계에 있는 꼭짓점이다. 꼭짓점 ${\displaystyle v}$의 형제(영어: sibling)은 ${\displaystyle v}$와 동일한 부모를 가지는 꼭짓점이다.

뿌리 트리에서 어떤 꼭짓점의 높이(영어: height)는 그 꼭짓점에서 잎 꼭짓점까지의 가장 긴 경로의 길이이다. 뿌리 트리의 높이는 뿌리의 높이로 정의한다. 뿌리 트리에서 어떤 꼭짓점의 깊이(영어: depth)는 그 꼭짓점에서 뿌리까지의 경로의 길이이다.

음이 아닌 정수 k에 대해, k진 트리(영어: k-ary tree)는 각 꼭짓점이 k개 이하의 자식을 갖는 뿌리 나무이다. 이진 트리는 2진 나무와 유사하지만 다른 개념이다.

유명한 트리 자료 구조

• 자가 균형 이진 탐색 트리
• AVL 트리
• 레드-블랙 트리
• 스플레이 트리

기타

• 신장 트리, 최소 비용 신장 트리
• B-트리, 2-3 트리, B+ 트리, B*-트리
• DSW 알고리즘
• R-트리
• 기수 트리
• 스킵 리스트

같이 보기

• 힙
• 연결 리스트
• 그래프 이론
• 분류:트리 구조