[Data Structure] 트리(Tree), 이진 트리(Binary Tree)

트리 (Tree)

트리는 이름 그대로 하나의 뿌리로부터 가지가 사방으로 뻗어있는 나무를 거꾸로 뒤집어 놓은 형태의 자료구조이다. 그림에서 볼 수 있듯이 하나의 데이터 아래에 여러 데이터가 존재할 수 있는 비선형적인 계층 구조이고 사이클이 존재하지 않는다.

대표적인 사용 예시는 디렉토리 구조, 토너먼트 대진표, 가계도 등이 있다. 

트리의 구조와 용어 

트리는 루트(Root)에서 시작해서 데이터가 담긴 노드들을 간선(edge)으로 연결한다.  부모 노드와 자식 노드가 있는데 자식 노드는 하나의 부모만 가질 수 있고 같은 부모를 가진 자식 노드들을 형제 노드 관계라고 부르고 자식이 없는 노드는 리프(leaf) 노드라고 부른다.

 

깊이 (depth)

루트로부터 하위 계층의 특정 노드까지의 깊이.

루트 노드의 depth는 0이고 내려갈수록 1씩 증가한다. 위 그림에선 P의 depth는 0. ABCD의 depth는 2다.

 

레벨 (level)

같은 깊이를 가지고 있는 노드들을 묶어서 레벨로 표현할 수 있다. depth가 0인 P의 level은 1이고 ABCD의 level은 2다.

 

높이 (height)

리프 노드를 기준으로 0부터 시작해서 부모 노드로 갈수록 증가한다. 즉 한 노드의 높이는 자식 노드들 중 가장 높은 높이의 값에 1을 더한 값이다. HI의 높이는 0이고 R의 높이는 3이다.

 

차수 (degree)

자식 노드와 연결된 간선의 개수. A의 차수는 1, L의 차수는 3이다.

 

노드 (node)

트리 구조를 이루는 모든 개별 데이터

 

루트 (root)

트리 구조의 시작 노드. 그림에선 P 노드

 

부모 노드 (parent node) 

간선으로 연결된 노드 중 루트에 가까운 노드. 그림의 Q와 A관계에서 Q노드

 

자식 노드 (child node)

간선으로 연결된 노드 중 루트에서 먼 노드. 그림의 Q와 A관계에서 A노드

 

리프 노드 (leaf node)

자식이 없는 노드. EFGBHID 노드 

---

이진 트리 (Binary Tree)

이진 트리는 노드의 차수가 0~2개로 자식 노드를 최대 2개까지로 제한한 트리의 한 종류이다.

여기서 자료의 삽입, 삭제 방법에 따라 정 이진 트리(Full Binary Tree), 완전 이진 트리(Complete Binary Tree), 포화 이진 트리(Perfect Binary Tree)로 나뉜다.

 

 

 

정 이진 트리(Full Binary Tree)

자식 노드가 0개 또는 2개인 트리. 리프 노드를 제외한 노드들은 자식 노드가 2개씩 있어야 한다. 

 

완전 이진 트리(Complete Binary Tree)

마지막 레벨을 제외하고 노드들의 자식들은 전부 있어야 하고 마지막 레벨의 노드들은 왼쪽부터 채워진다. 

 

포화 이진 트리(Perfect Binary Tree)

리프 노드를 제외한 노드들은 2개의 자식이 있고 모든 리프 노드들이 동일한 레벨을 갖는다.