[자료구조] 트리(Tree)

1. 트리의 개념

트리란 노드가 나뭇가지처럼 연결된 비선형 계층적 자료구조다.

그래프의 일종으로, 순환 구조를 갖지 않는 그래프라는 점이 가장 큰 특징이다.

 

 

2. 트리의 구성요소

트리의 구성요소

1) 간선(edge, branch) : 노드를 잇는 선

2) 루트 노드(root node) : 시작 노드. 부모 노드가 없고 트리에서 유일하다.

3) 리프 노드(leaf node) : 자식이 없는 노드. 단말 노드, 말단 노드라고도 한다. 트리는 나무를 뒤집어 놓은 듯한 모양이기 때문에 뒤집은 나무에서 잎의 위치를 생각하면 이해하기 쉽다.

4) 내부 노드(internal node) : 리프 노드가 아닌 노드

5) 부모 노드(parent node) : 자식(child) 노드를 가진 노드

6) 형제(siblings) : 같은 부모 노드를 공유하는 노드

 

7) 노드의 크기(size) : 자신을 포함한 모든 자손 노드의 개수

8) 노드의 깊이(depth) : 루트에서 어떤 노드에 도달하기 위해 거쳐야 하는 간선의 개수

9) 노드의 레벨(level) : 특정 깊이를 가지는 노드의 집합. 0부터 시작한다.

10) 노드의 차수(degree) : 하위 트리 개수(간선의 개수)

11) 트리의 차수(degree of tree) : 트리의 최대 차수

12) 높이(height) : 루트 노드에서 가장 깊은 곳에 있는 노드의 깊이 

 

 

3. 트리의 특징

• 하나의 루트 노드와 0개 이상의 하위 트리로 구성된다.
• 데이터를 순차적으로 저장하지 않으므로 비선형 자료구조이다.
• 트리내에 또 다른 트리가 있는 재귀적 자료구조이다.
• 그래프의 일종으로, 순환(Loop)구조를 갖지 않고 연결된 무방향 그래프 구조이다.
• 노드 간에 부모 자식 관계를 갖고 있는 계층형 자료구조이며 모든 자식 노드는 하나의 부모 노드만 갖는다.
• 노드가 n개인 트리는 항상 n-1개의 간선(edge)을 가진다.
• 루트에서 어떤 노드로 가는 경로는 유일하다.

 

 

4. 트리의 종류

트리에는 트리, 이진 트리, 이진 탐색 트리, 균형 트리, 비균형 트리, 정 이진 트리, 완전 이진 트리, 포화 이진 트리 등이 있다.

4.1 트리와 이진 트리 (Binary Tree)

트리의 각 노드가 m개 이하의 자식을 가지고 있으면 그 트리는 m-ary트리(다진 트리)라고 부른다.

m이 2일 경우, 즉 모든 노드의 차수가 2이하일 때를 특별히 이진 트리라고 한다.

트리의 한 종류이고 모든 트리가 이진 트리는 아니다.

 

4.2 이진 트리(Binary Tree)와 이진 탐색 트리(Binary Search Tree, BST)

이진 탐색 트리는 정렬된 이진 트리다.

'모든 왼쪽 자식 노드 <= n < 모든 오른쪽 자식 노드' 를 만족한다.

탐색 시간 복잡도가 O(logn)이다.

 

4.3 균형 트리와 비균형 트리

O(logn)에 탐색 및 삽입이 가능할 정도로 잘 균형이 잡혀있는 경우(균형이 깨지면 최악의 경우 O(n))

* 자가 균형 이진 탐색 트리: 삽입 삭제 시 자동으로 높이를 작게 유지하는 이진 탐색 트리로, AVL 트리, 레드-블랙 트리 등이 있다.

 

4.4 정이진트리(Full Binary Tree), 완전이진트리(Complete Binary Tree), 포화이진트리(Perfect Binary Tree)

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

 

힙(Heap), 트라이(Trie) 등이 대표적인 트리 자료구조이다.