14. 트리의 정의(Definition of Tree)

 

14. 1. 트리의 정의(Definition of Tree)

 

- 트리(Tree): Root라는 특별한 Node를 가지는 비순환의 연결 그래프.

 

- 노드(Node): Tree를 구성하는 꼭짓점.

 

- 루트(Root): Tree에서 가장 높은 곳에 위치하는 시작 노드.

 

- 부모 노드(Parent Node): Tree에서 임의의 노드의 한 단계 상위 노드.

 

- 자식 노드(Child Node): Tree에서 임의의 노드의 한 단계 하위 노드.

 

- 형제 노드(Sibling Node): Tree에서 임의의 노드와 부모가 같은 노드.

 

- 리프 노드(Leaf Node): 자식 노드가 없는 노드.

 

- 조상 노드(Ancestor Node): Root에서 임의의 한 노드에 이르는 경로에 있는 모든 노드들.

 

- 자손 노드(Descendant Node): 임의의 한 노드에서 리프 노드에 이르는 경로에 있는 모든 노드들.

 

- 서브 트리(Sub Tree): Tree에서 임의의 한 노드를 Root로 하는 노드.

 

- 차수(Degree): 한 노드에 포함된 자식 노드의 개수.

 

- 레벨(Level): Root를 Level 0으로 시작하여 자식 노드로 한 단계씩 내려갈 때마다 하나씩 증가하는 단계.

 

- 높이(Height), 깊이(Depth): Tree의 최대 레벨.

 

- 포레스트(Forest): Tree에서 Root와 Edge를 제거하여 얻은 Sub Tree.

 

 

- Tree에서 Edge Number = Node Number – 1.

 

- Tree에서 2개의 임의의 Node를 정할 때 이 Node 사이에 가는 경로는 단 하나이다.

 

---

 

14. 2. 이진트리(Binary Tree)

 

- 이진트리(Binary Tree): Maximum Degree가 2인 Tree.

 

- 완전이진트리(Complete Binary Tree): 높이가 h일 때 Level 1 ~ h-1 까지 모든 노드의 차수가 2이고, Level h에

서는 왼쪽부터 노드가 채워지는 트리.

 

- 포화이진트리(Full Binary Tree): 높이가 h일 때 Level 1 ~ h 까지 모든 노드의 차수가 2인 트리.

 

- 편향이진트리(Skewed Binary Tree): 왼쪽이나 오른쪽 한 방향으로만 뻗어나가는 트리.

 

- Level k에서 이진트리가 가질 수 있는 최대 노드의 수: 2^k 개.

 

- 높이가 m인 이진트리가 가질 수 있는 최대 노드의 수: 2^{m + 1} – 1개.

 

- 높이가 m인 이진트리가 가질 수 있는 최소 노드의 수: m + 1개.

 

---