[자료구조] 이진 트리(binary tree) 개념

트리(tree)

트리는 계층적인 구조를 나타내는 비선형 자료구조입니다. 트리는 부모-자식 관계의 노드들로 이루어지며 트리를 응용한 분야로는 계층적 조직을 표현하거나 컴퓨터 파일들의 디렉토리 구조 조직, 인공지능에서의 결정 트리 등이 있습니다.

 

 

트리의 용어

노드(node) : 트리의 구성 요소입니다.

루트(root) : 부모가 없는 최상위 노드입니다.

서브 트리(subtree) : 하나의 노드와 그 노드들의 자손들의 이루어진 트리입니다.

단말노드(terminal node) : 자식이 없는 노드입니다.

비단말노드 : 적어도 하나의 자식을 가지는 노드입니다.

자식, 부모, 형제, 조상, 자손 노드: 용어 그대로의 의미입니다.

레벨(level) : 트리의 각층의 번호입니다.

높이(height) : 트리의 최대 레벨입니다.

차수(degree) : 노드가 가지고 있는 자식 노드의 개수입니다.

 

 

트리의 종류

이진 트리(binary tree)

모든 노드가 2개의 서브트리를 가지고 있는 트리입니다. 서브트리는 공집합일 수 있으며 공집합도 서브트리입니다.

이진 트리의 노드에는 최대 2개까지의 자식 노드가 존재합니다. 그러므로 모든 노드의 차수가 2 이하가 되며 구현이 편리합니다.

이진 트리에는 서브트리간의 왼쪽, 오른쪽 순서가 존재합니다.

이진 트리는 공집합이거나 루트와 왼쪽 서브트리, 오른쪽 서브트리로 구성된 노드들의 유한집합으로 정의됩니다.

이진 트리의 서브트리들은 모두 이진 트리여야만 합니다.

 

이진 트리의 특징

 

 

(1) 노드의 개수가 n개이면 간선의 개수는 n-1 개.

 

 

(2) 높이가 h인 이진 트리의 경우, 최소 h개의 노드를 가지며 최대 2^h - 1개.

예를 들어 높이가 3인 경우 최소 3개의 노드를 가지며 최대 2^3 - 1 = 7개의 노드를 가집니다.

 

(3) n개의 노드를 가지는 이진 트리의 높이

최대 h = n. 

최소 h = log2(n+1) 개. (2는 밑)

 

이진 트리의 분류

포화 이진 트리(full binary tree)

각 레벨에 노드가 꽉 차있는 이진 트리입니다. 높이가 h일 때, 전체 노드 개수는 2^h - 1개입니다.

 

완전 이진 트리(complete binary tree)

레벨1부터 k-2까지는 노드가 모두 채워져 있고 마지막 레벨 k에서는 왼쪽부터 오른쪽으로 노드가 순서대로 채워져 있는 이진 트리입니다.