자료구조 part 3. tree

tree 구조?

• 비선형 자료구조 : 차례대로 연결 되는 것이 아닌 유기적으로 연결이 가능한 구조.
• 뿌리 노드인 부모를 바탕으로 자식을 가지는 부모 자식 관계를 가진다.
• 가족 관계도와 같은 구조이다.
• 계층 (높이, 레벨)을 가지고 있다.

트리구조는 용어를 잘 파악해야 될 듯 하다.

1. 노드의 차수 : 한 노드가 가진 서브트리의 수

2. 리프(나뭇잎)노드 (단말) : 차수가 없는 노드

3. 부모 노드 : 자식노드들의 상위 노드

4. 자식 노드 : 노드에 연결된 서브트리의 루트 노드

5. 형제 노드 : 부모가 같은 노드

6. 트리의 차수 : 트리노드들의 차수중 최대의 차수

7. 노드의 레벨 : 노드가 속해있는 트리의 깊이

8. 트리의 높이 : 트리의 최대 레벨

이진 트리

노드의 최대 차수가 2인 트리

1. 편향 이진 트리

   • 한 쪽으로 편향되어 생성된 이진트리

   문제점 :
   탐색속도의 저하 : 편향 트리로 형성이 되면 제일 끝의 요소를 탐색하기 위해 모든 노드들을 탐색해야 한다. 이로 인해 탐색하는 속도가 떨어지게 된다.

2. 포화 이진트리

• 높이가 h일 때 2^(h+1) - 1 개의 노드개수가 최대 노드의 수 이다. 이 때 최대 노드의 수를 만족하는 트리를 포화 이진트리라고 한다.
• 내부의 모든 노드들이 2개의 자식을 가지는 트리 (포화 상태)

3. 완전 이진트리

• 포화 이진 트리에서 leaf노드들을 오른쪽에서 제거하여 얻어진 트리이다.

  공간의 효율이 좋다.

  ---

  이진트리의 순회 방식