21. 트리의 기본개념과 방향 트리(11-1)

1차시

트리의 기본개념

1. 트리의 기본 개념

1) 트리(Tree) 

. 그래프에서 가장 중요한 클래스(class) 

. 가계도나 회사의 조직도 등을 나타낼 때 유용하게 사용되고 있는 비선형 자료구조(non-linear data  structure) 

. 계층적 자료구조(hierarchical data  structure) 

*화학에서의 트리

. 트리(Tree)의 정의 

.  A를 유한 집합이라 하고  T를  A에서의 관계라 하자.  A에 속하는 정점  v0 에 대해  v0 에서  A의 모든 다른 정점으로는 유일한 경로가 존재하고,  v0에서  v0 로 가는 경로는 존재하지 않을 때 관계  T를 트리(Tree)라 한다. 

.  트리T는  다음을  만족시키는  단순그래프이다.  v와  w가  T의  정점들이면,  v에서  w로의  유일한 단순 경로가 존재한다. 

. 근트리(rooted  tree)는 특별한 정점이 뿌리(루트노드)로 지정된 트리이다. 

2. 트리의 주요 용어 

1) 숲(forest) 

. 연결되어 있지 않아서 트리는 아니지만 그래프의 각 성분은 트리로 되어 있는 그래프. 즉, 서로 연결되어 있지 않은 트리들의 집합 

. 트리에서 루트 노드를 제거하면 발생하는  n개의 분리된 트리들을 숲(forest)이라고도 한다. 

. <그림6>에서 루트노드  a를 제거하면  T1,  T2로 이루어진 숲을 얻는다. 

2) 노드(node) 

. 트리의 구성 요소. <그림  6>에서  a, b,  c,  d,  e,  f,  g, h,  i,  j,  k이다. 

3) 루트(root) 

. 주어진 그래프의 시작 노드로서 통상 트리의 가장 높은 곳에 위치하며 <그림  6>에서 노드  a가 루트노드이다. 

3) 서브트리(subtree) 

. 하나의 노드와 그 노드들의 자손들로 이루어진 트리, <그림  6>에서 트리  T1과  T2이다. 

4) 차수(degree) 

. 어떤 노드의 차수는 그 노드의 서브트리의 개수를 나타낸다.  <그림  6>에서 노드  a의 차수는 2,  d의 차수는  3,  h의 차수는  1,  k의 차수는  0이다. 

.트리에 있는 각 노드의 차수 중에서 가장 큰 차수를 트리의 차수(degree of  tree)라고 한다. 

5) 잎노드  (leaf  node) 또는 단말노드(terminal  node) 

. 차수가  0인 노드로서 <그림  6>에서  c,  e,  f, g,  j,  k이다. 

6) 자식 노드(children  node) 

. 어떤 노드의 서브 트리의 루트노드들을 말하는데 <그림 6>에서 노드 a의 자식 노드는 b, h 이다. 

7) 부모노드(parent  node) 

. 자식 노드의 반대 개념으로서  <그림  6>에서  b의 부모노드는  a이고,  e,  f,  g의 부모노드는  d이다. 

8) 형제노드(sibling  node) 

. 동일한 부모를 가지는 노드인데  <그림  6>에서  b,  h는 모두 형제 노드이고,  e,  f,  g도 형제노드이다. 

9) 중간노드  (internal  node) 

. 루트도 아니고 잎노드도 아닌 노드를 말한다.<그림  6>에서  b,  d, h,  i이다.