알고리즘 기초 03) 트리 (tree) 자료 구조

개념

node와 node를 연결하는 edge로 구성된 자료구조이다.

비선형 자료구조의 일종으로 계층 구조를 이룬다.

 

tree 표현에 사용되는 용어



degree : 차수, 특정 노드의 자식 노드 수

height : 높이, root node에서 최하위 노드까지의 길이

level : 레벨, 각 층의 번호 - root node : level 1

 

tree vs graph : tree는 graph의 한 종류로써, cycle이 없는 일종의 connected graph이다.

대표적인 사용처 : 각종 탐색

 

Binary Tree (이진 트리)

최대 2개의 자식 노드를 갖는 트리

 

종류 

1) Complete binary tree (완전 이진 트리)

2) Full binary tree (포화 이진 트리)

3) Skewed binary tree (사향 이진 트리)

 

Complete Binary Tree의 특성

 

tree의 모든 높이에서 노드가 꽉 차 있는 binary tree이다.

즉, 마지막 level을 제외하고는 모든 level이 완전히 채워져 있다.

 

마지막 levle은 꽉 차 있지는 않아도 되는데, 노드가 왼쪽에서 오른쪽으로 채워져야 한다.

마지막 레벨h에서는 최소 1개에서 최대 2h-1개의 노드를 가질 수 있다.

 

complete binary tree는 list, array 등의 선형 자료구조를 사용해 효율적으로 표현할 수 있다.