3. tree(트리) [자료구조 & 알고리즘]

1. 용어 

 

• tree : 계층적인 자료를 표현하는데 적합한  자료구조

트리의 예

 

• node(노드) : 위의 첫 번째 그림에서 트리의 구성 요소에 해당하는 1,2,3,4,6,7,10,15를 노드라고 한다.
• root node(루트노드) : 트리는 한 개 이상의 노드로 이루어진 유한 집합이다. 이들 중 하나의 노드는 루트(root) 노드라 불리고 나머지 노드들은 서브 트리(subtree)라고 불린다.
  
  위의 첫번째 그림에서 전체 노드 집합 {1,2,3,4,6,7,10,15}중에서 루트 노드는 1이고 나머지 노드들은 {2,4,6,10,7}, {3,15} 두 개의 집합으로 나누어진다. 이들을 1의 서브트리라고 한다.
  다시 서브 트리인 {2,4,6,10,7}의 루트는 2가 되고 나머지 노드들은 다시 2개의 서브트리 {4}, {6,10,7} 로 나누어진다.
  이런 식으로 6, 3도 마찬가지 논리로 진행된다.
• edge(간선) : 트리에서 루트와 서브트리는 선으로 연결된다. 이 연결선을 간선(edge)라고 한다.
• parent node, children node, terminal node, nonterminal node(부모노드, 자식 노드, 단말노드, 비단말 노드) : 
  노드들 간에는 부모 관계, 형제 관계, 조상과 자손 관계가 존재한다. 그림 1에서 1은 2의 부모 노드가 된다. 반대로 2는 1의 자식노드가 된다. 단말 노드는 자식 노드가 없는 노드를 말한다. 그림에서 4,10,7,15 같은 경우가 단말 노드 혹은 리프노드(leaf node)라고 한다. 이의 반대말은 비단말노드이다.
• degree(차수) : 노드의 차수(degree)  는 어떤 노드가 가지고 있는 자식 노드의 개수를 의미한다. 그림 1에서는 자식노드가 2개이기 때문에 차수가 2가 된다. 단말노드는 차수가 0인 노드이다. 
• level(레벨) : 트리에서의 레벨은 트리의 각층에번호를 매기는 것으로 1의 레벨은 1이고, {2,3}의 경우 레벨은 2이다. 한 층씩 내려갈수록 1씩 증가한다.
• height(높이) : 트리가 가지고 있는 최대 레벨을 말한다. 위의 트리에서 높이는 4이다. 

 

 

2. 이진트리(binary tree)

트리 중에서 가장 많이 쓰이는 트리가 이진트리이다. 모든 노드가 두 자식을 최대로 갖는 구조이다.

이진 트리의 예

2.1 이진트리의 성질

• n개의 노드를 가진 이진트리는 정확하게 n-1개의 간선을 가짐
• 높이가 h인 이진트리의 경우, 최소 h개의 노드를 가지며 최대 2^h - 1 개의 노드를 가짐.
  (왜냐하면, 한 레벨에는 적어도 하나의 노드는 존재해야 하므로 높이가 h인 이진트리는 적어도 h개의 노드를 가짐. 또한 하나의 노드는 최대 2개의 자식을 가질 수 있으므로 레벨 i에서의 노드의 최대개수는 2^i - 1이 된다.
  따라서 전체 노드 개수는 2^h - 1 이 된다.
• n개의 노드를 가지는 이진트리의 높이는 최대 n이거나 최소 [log2(n+1)] 이 된다. 

 

2.2 이진트리의 분류

• 2.2.1 포화 이진 트리
• 2.2.2 완전 이진트리
• 2.2.3 기타 이진트리

이진트리의 분류

 

2.2.1 포화 이진트리(full binary tree)

포화 이진트리는 용어 그래도 트리의 각 레벨에 노드가 꽉 차있는 이진트리를 의미함.

 

2.2.2 완전 이진 트리

완전 이진 트리는 높이가 k일 때 레벨 1부터 k-1 까지는 노드가 모두 채워져 있고 마지막 레벨 k에서는 왼쪽부터 오른쪽으로 노드가 순서대로 채워져 있는 이진트리. 마지막 레벨에서는 노드가 꽉 차있지 않아도 되지만 중간에 빈 곳이 있어서는 안 된다. 따라서 포화 이진트리는 항상 완전 이진트리이지만 그 역은 성립하지 않음