[자료구조] 이진 트리(간단한 정의 및 특징)

기본적으로 트리는 계층적 구조를 가진 자료구조입니다.

나무의 뿌리는 최하단에 위치해있으나, 자료구조에서 트리의 뿌리는 최상단에 위치하여

위에서부터 아래로 뻗어나가는 형태를 가집니다.

 

*이진트리(Binary Tree) : 최상위 노드(root)를 제외한 각 원소가 최대 2개의 자식(Child) 노드를 가지는 트리

   → 최대 2개의 자식노드를 가질 수 있으나, 0개의 자식노드를 가져도 무방합니다.

이진 트리의 예시

위의 그림은 A(root)를 기준으로 최대 2개의 자식을 가지는 노드들을 가지는 트리의 예시입니다.

B와 E는 각각 C,D와 F,G를 자식으로 가지는 노드입니다.

 

A(root)는 B와 E의 부모노드이고, B와 E는 A의 자식노드이나 B와 E는 또 각각 C,D와 F,G의 부모노드입니다.

이렇게 누군가의 자식노드가 누군가의 부모노드의 역할을 할 수 있습니다. 이를 계층적으로 정의한 자료구조이죠.

 

 

* 트리에 대한 용어정리

1. 루트노드 : 더이상 부모노드가 없는 노드 → 예시에서 A입니다.

2. 부모노드 : 자식노드를 가진 노드

3. 자식노드 : 부모노드를 가진 노드

4. 형제노드 : 동일한 부모를 공유하는 노드

5. 잎(leaf) 노드 : 자식이 단 하나도 없는 노드

6. 깊이(Depth) : 루트노드를 기준으로 특정 노드에 도달하기 위해 거쳐야 하는 간선의 수 ( A → C : 2개의 간선), 깊이 2

7. 높이(Height) : Maximum Depth, 즉 최하단 노드까지 도달할 때 거쳐야 하는 간선의 수

8. 서브트리(Subtree) : 어떤 노드와 그 자손들로 구성된 트리, 즉 특정 노드 n을 Root로 하는 트리

9. 노드의 차수(level) : 각 노드에 연결되어 있는 자식의 수 : 이진트리에서는 최대 차수가 2입니다.

 

*이진 트리의 종류

1. 완전 이진트리 : 루트노드에서 시작하여 모든 노드가 왼쪽→오른쪽 순서대로 구성된 트리

완전이진트리 (왼쪽->오른쪽 순서)

 

2. 편향 이진트리 : 루트노드를 기준으로 자식노드가 한 쪽으로 편향되게 이루어진 트리

루트를 기준으로 왼쪽으로 치우친 트리

 

3. 포화 이진트리 : 높이(Height)가 h인 노드가 가질 수 있는 최대 노드 개수를 가진 트리 = 2^(h+1) -1

                           맨 위의 예시가 포화 이진트리의 예가 되겠습니다.

높이가 3인 이진트리에서 가질 수 있는 최대 노드 개수는 15개이고, 15개가 다 차있는 이진 트리는 포화 이진트리임