CWN(CHANGE WITH NEWS) - 자료구조 어디까지 알고 있니? #5. 트리의 종류

1. 이진 트리
이진 트리는 모든 노드의 자식 노드가 두 개 이하인 트리를 의미한다. 이진 트리는 서브 트리가 두 개 이하기 때문에 서브 트리는 왼쪽 서브 트리와 오른쪽 서브 트리로 구분한다.

(1) 완전 이진 트리(complete binary tree)
단말 노드를 제외한 나머지 노드가 두 개의 자식 노드를 가지고 있는 트리를 ‘완전 이진 트리’라 한다. 아래 그림의 A, B, C, D 노드는 모두 두 개의 자식 노드를 가지고 있다.

마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있으며, 마지막 레벨의 모든 노드는 가능한 한 가장 왼쪽에 있다. 마지막 레벨 h에서 1부터 2h-1개의 노드를 가질 수 있다. 또 다른 정의는 가장 오른쪽의 잎 노드가 제거된 포화 이진 트리다.

완전 이진 트리는 배열을 사용해 효율적으로 표현할 수 있다.

(2) 포화 이진 트리(perfect binary tree)
모든 노드가 채워진 이진 트리를 ‘포화 이진 트리’라고 한다.

모든 내부 노드가 두 개의 자식 노드를 가지며 모든 잎 노드가 동일한 깊이 또는 레벨을 갖는다. 각각의 사람이 한 명의 어머니와 한 명의 아버지를 갖는 것처럼, 주어진 깊이에 대한 한 사람의 가계도가 포화 이진 트리의 예가 될 수 있다.

(3) 정 이진 트리(full binary tree)
모든 노드가 0개 또는 2개의 자식 노드를 갖는 트리다.

(4) 편향 이진 트리(skewed binary tree)
노드가 한 방향으로 편향된 트리

이진 탐색 트리
이진 탐색 트리는 데이터의 삽입, 삭제, 탐색 등이 자주 발생하는 경우에 효율적인 구조로, 이진 트리이면서 같은 값을 갖는 노드가 없어야 한다.

왼쪽 서브 트리에 있는 모든 데이터는 현재 노드의 값보다 작고, 오른쪽 서브 트리에 있는 모든 노드의 데이터는 현재 노드의 값보다 크다.

이번 기사에서는 트리의 종류를 알아보았다. 다음 기사에서는 그래프에 대해 알아보자.

[저작권자ⓒ CWN(CHANGE WITH NEWS). 무단전재-재배포 금지]