[C] 이진 트리란? 이진 트리 관련 용어 정리

1. 트리란

 

트리는 나무를 뒤집어 놓은 형태의 자료구조다. 일반적으로 트리의 최상단 노드를 루트 노드라고 하고, 루트 노드에서 가지를 이용해서 각각의 노드로 연결되며, 가장 마지막에 해당하는 원소들을 리프 노드라고 부른다.

 

트리 기본 구조

 

또한 트리는 기본적으로 부모와 자식 간의 관계로 이루어져 있다. 가지로 연결된 관계에서 루트 노드에 가까운 노드를 부모 노드, 리프 노드에 가까운 노드를 자식 노드라고 한다. 

 

부모-자식 노드, 형제 노드 관계

 

트리 구조에서 길이란 출발 노드에서 목적지 노드까지 거쳐야 하는 가짓수를 의미한다. 가지를 2번 거쳐서 1번 노드에서 35번 노드까지 간다면, 길이가 2가 되는 것이다. 깊이란 루트 노드에서 특정 노드까지의 길이를 의미한다. 높이는 가장 높은 노드부터 가장 깊은 노드까지의 길이를 의미한다.

 

트리의 길이, 깊이, 높이

 

2. 이진 트리란

 

이진 트리(binary tree)는 최대 2개의 자식을 가질 수 있는 트리다. 

 

 

포화 이진 트리(full binary tree)는 리프 노드를 제외한 모든 노드가 두 자식을 갖고 있는 트리다. 

 

포화 이진 트리와 아닌 트리

 

완전 이진 트리(complete binary tree)는 모든 노드들이 왼쪽 자식부터 차근차근 채워진 트리다.

 

모두 완전 이진 트리

높이 균형 트리(height balanced tree)는 왼쪽 자식 트리와 오른쪽 자식 트리의 높이가 1 이상 차이 나지 않는 트리다. 높이 균형이 맞지 않는 트리를 편향 트리라고 한다. 

 

높이 균형 트리와 아닌 트리

 

이진 트리는 많은 양의 노드를 낮은 높이에서 관리할 수 있다는 점에서 데이터 활용의 효율성이 높다. 데이터 저장, 탐색 등의 다양한 목적에서 활용 가능하다. 편향 트리 같은 경우에는 한 쪽으로 몰려서 바르지 않은 자료구조이기 때문에 높이 균형을 맞춰줘야 한다.