트리 (tree in computer science)

주제(Subject)
--------------------------------------------------------
한글(약어) : 트리()
영어(약어) : tree()


관련개념(Related Concepts)
--------------------------------------------------------
자료구조
그래프(graph)


개요(Summary)
--------------------------------------------------------
연결된 무사이클, 무방향 그래프


본문(Body)
--------------------------------------------------------
1. 나무의 성질
   연결된 무사이클, 무방향 그래프.
   n개의 노드를 가진 어떤 이진 나무도 n개의 노드를 갖는 완전 이진 나무의 높이보다 낮을 수는 없다.
   높이 h인 완전 이진 나무의 노드 수 : 2^h ≤ n ≤ 2^(h+1) -1
   n개 노드의 완전 이진나무의 높이 : └ log n ┘

2. 용어 정리
   (1) 뿌리(root)
      나무의 정점 중 하나를 지정한 것.

   (2) 뿌리나무(rooted tree)
      뿌리가 지정된 나무. 뿌리나무가 아닌 것을 자유나무라고 한다.

   (3) 조상(ancessor)
      뿌리 r 로부터 특정 노드 x 까지의 경로상에 존재하는 모든 노드들을 노드 x의 조상이라 한다.

   (4) 자손(descendent)
      조상과 반대개념

   (5) 부모(parent)
      노드 x의 바로 위에 연결된 노드

   (6) 자식(child)
      노드 x의 바로 아래에 연결된 노드

   (7) 동기(sibling)
      부모가 같은 노드

   (8) 잎(leaf)
      자식이 없는 노드

   (9) 차수(degree)
      뿌리나무에서 노드 x의 자식의 개수

   (10) 깊이(depth)
      뿌리나무에서 노드 x까지의 경로의 길이

   (11) 높이(height)
      뿌리나무에서 노드 x까지의 최대의 깊이

   (12) 수준(level)
      깊이와 동일한 의미

   (13) 순서 나무(ordered tree)
      노드의 자식들에 순서가 있는 나무.

   (14) 이진 나무(binary tree)
      각 노드의 자식이 2개 이하인 나무.

   (15) 전이진 나무(full binary tree)
      모든 노드의 자식이 0 또는 2인 이진 나무

   (16) 포화 이진 나무(perfect binary tree)
      모든 잎의 깊이가 같은 이진 나무.
      * 높이 h인 포화이진나무
         - 노드의 개수               = 2^(h+1) - 1
         - 잎의 개수                  = 2^h
         - 잎이 아닌 노드의 개수 = 2^h - 1

   (17) 완전 이진 나무(complete binary tree)
      포화 이진 나무의 잎 노드들을 오른쪽부터 제거하여 얻어진 나무


모임,단체(Commutities)
--------------------------------------------------------
1. NIST(National Institute of Standards and Technology)
   http://www.nist.gov/


블로그,개인 홈페이지 등(Humanities)
--------------------------------------------------------


참고문서(References)
--------------------------------------------------------
* 한국어(Korean)
저자. 역자. "제목". 출판사. 출판년도. (ISBN:)
1. 조유근, 홍영식, 이지수, 김명. "알고리즘 - 알고리즘의 설계와 분석". 이한출판사. 2005. (ISBN:89-8241-210-7)

* 영어(English)
저자. 제목, 판, 출판사. 출판년도. (ISBN:)
1. Wikipedia : Tree(data structure)
   http://en.wikipedia.org/wiki/Tree_%28data_structure%29

2. Wikipedia : Tree(graph theory)
   http://en.wikipedia.org/wiki/Tree_%28graph_theory%29

3. Dictionary of Algorithms and Data Structures
   http://www.nist.gov/dads/