Tree (트리) - 1

트리의 개념

• 비선형 구조
• 원소들 간에 1:n 관계를 가지는 자료구조
• 원소들 간에 계층관계를 가지는 계층형 자료구조
• 상위 원소에서 하위 원소로 내려가면서 확장되는 트리(나무)모양의 구조

노트(node) - 트리의 원소

ex) 트리 T의 노드 - 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 14

간선(edge) - 노드를 연결하는 선으로 부모 노드와 자식 노드를 연결

루트 노드(root node) - 트리의 시작 노드

ex) 트리 T의 루트 노드 - 1

형제 노드 (sibling node) - 같은 부모 노드의 자식 노드들

ex) 2, 3은 형제 노드

조상 노드 - 간선을 따라 루트 노드까지 이르는 경로에 있는 모든 노드들

ex) 8의 조상 노드: 4, 2, 1

서브 트리(subtree) - 부모 노드와 연결된 간선을 끊었을 때 생성되는 트리

자손 노드 - 서브 트리에 있는 하위 레벨의 노드들

ex) 4의 자손 노드: 8, 9

 

차수(degree) 

• 노드의 차수: 노드에 연결된 자식 노드의 수 (ex. 2의 차수 2)
• 트리의 차수: 트리에 있는 노드의 차수 중에서 가장 큰 값
• 단말 노드(리프 노트): 차수가 0인 노드, 즉 자식 노드가 없는 노드 (ex. 8, 9, 10, 11, 13, 14)

 

높이

• 노드의 높이: 루트에서 노드에 이르는 간선의 수. 노드의 레벨(ex. 2의 높이 1, 8의 높이 3)
• 트리의 높이: 트리에 있는 노드의 높이 중에서 가장 큰 값, 최대 레벨(ex. 3)

 

트리는 하나 이상의 노드로 이루어진 유한 집합이며 다음 조건을 만족한다.

1.  노드 중 최상위 노드를 루트(root)라 한다.
2. 나머지 노드들은 n(n>=0)개의 분리 집합 T1,T2,...,Tn으로 분리될 수 있다.
3. 이들 T1, T2,...,Tn은 각각 하나의 트리가 되며(재귀적 정의) 루트의 부 트리(subtree)라 한다.

B, D, E는 단말노드이며 이들의 집합은 부 트리(subtree)가 된다.

 

---

이진 트리

모든 노드들이 2개의 서브트리를 갖는 특별한 형태의 트리

각 노드가 자식 노드를 최대한 2개까지만 가질 수 있는 트리

• 왼쪽 자식 노드(left child node)
• 오른쪽 자식 노드(right child node)

이진 트리의 예

 

이진트리의 레벨 i에서의 최대 노드의 개수는 2^i개이다.

높이가 h인 이진 트리가 가질 수 있는 노드의 최소 개수는 (h+1)개가 되며, 최대 개수는 (2^(h+1)-1)개가 된다.

 

이진 트리의 종류

• 포화 이진 트리(Full Binary Tree)
• 완전 이진 트리(Complete Binary Tree)
• 편향 이진 트리(Skewed Binary Tree)

 

포화 이진 트리(Full Binary Tree)

• 모든 레벨에 노드가 포화상태로 차 있는 이진 트리
• 높이가 h일 때, 최대의 노드 개수인  (2^(h+1)-1)개의 노드를 가진 이진 트리 (ex. 높이 3일 때,  (2^(h+1)-1) = 15, 15개의 노드를 가짐)
• 루트를 1번으로 하여  (2^(h+1)-1)까지 정해진 위치에 대한 노드 번호를 가진다. 

 

완전 이진 트리(Complete Binary Tree)

• 높이가 h이고 노드 수가 n개일 때 (단,  h+1 <= n < 2^(h+1)-1), 포화 이진 트리의 노드 번호 1번부터 n번까지 빈 자리가 없는 이진 트리 

 

편향 이진 트리(Skewed Binary Tree)

• 높이 h에 대한 최소 개수의 노드를 가지면서 한쪽 방향의 자식 노드만을 가진 이진 트리