[자료구조/알고리즘] 트리(Tree)

트리(Tree)

• 정의
  - 노드와 링크로 구성된 자료구조
  -> 그래프의 일종으로 cycle이 없음
• 사용처
  - 계층적 구조를 나타낼 때 사용
  • 폴더구조, 조직도 ...
• 특징
  - 하나의 노드에서 다른 노드로 이동하는 경로는 유일
  - 노드가 N개인 트리의 Edge수는 N-1개
  - Acyclic(Cycle이 존재하지 않음)
  - 모든 노드는 서로 연결되어있음
  - 하나의 Edge를 끊으면 2개의 Sub-tree로 분리됨
• 구조
  - 노드(Node): 트리 구조의 자료 값을 담고 있는 단위
  - 엣지(Edge): 노드 간의 연결선(=link, branch)
  - 루트 노드(Root): 부모가 없는 노드, 최상위 노드
  - 리프 노드(Reaf): 자식이 없는 노드
  - 내부 노드(Internal): 리프노드를 제외한 모든 노드
  - 부모 노드(Parent): 연결된 두 노드의 상위노드
  - 자식 노드(Child): 연결된 두 노드의 하위노드
  - 형제 노드(Sibling): 같은 부모를 가진 노드
  - 깊이(Depth): 루트에서 특정 노드까지의 간선의 수
  - 레벨(Level): 특정 깊이를 가지는 노드의 집합
  - 높이(Height): 트리에서 가장 큰 레벨 값
  - 크기(Size): 자신을 포함한 자식 노드의 개수
  - 차수(Degree): 각 노드가 지닌 가지의 수
  - 트리의 차수: 트리의 최대 차수
  

이진트리(Binary Tree)

• 특징
  - 각 노드는 최대 2개의 자식을 가질 수 있음
  - 자식 노드는 좌우를 구분함

• 포화 이진 트리(Perfect binary tree)
  - 모든 레벨에서 노드들이 꽉 채워져 있는 트리
  - 포화 이진 트리의 높이가 h일 때, 노드의 수는 $2^{h+1}-1$개
  - 노드가 N개일 때 높이는 $\log N$
  

• 완전 이진 트리(Complete binary tree)
  - 마지막 레벨을 제외하고 노드들이 모두 채워져 있는 트리
  

• 정 이진 트리(Full binary tree)
  - 모든 노드가 0개 또는 2개의 자식 노드를 갖는 트리
  

• 편향 트리(Skewed binary tree) <=> 사향트리
  - 한쪽으로 기울어진 트리
  

• 균형 이진 트리(Balanced binary tree)
  - 모든 노드의 좌우 서브 트리 높이가 1이상 차이나지 않는 트리

이진 트리의 순회(Traversal)

• 모든 노드를 빠뜨리거나 중복하지 않고 방문하는 연산
• 전위, 중위, 후위(DFS: Depth frist search, 깊이 우선 탐색)
• 레벨 순회(BFS: Breath first search, 너비 우선 탐색)

전위 순회(Preorder Traversal)

• 방문순서: 현재 -> 왼쪽 -> 오른쪽
  

중위 순회(Inorder Traversal)

• 방문순서: 왼쪽 -> 현재 -> 오른쪽
  

후위 순회(Postorder Traversal)

• 방문순서: 왼쪽 -> 오른쪽 -> 현재
  

레벨 순회(Level Traversal)

• 방문순서: 각 레벨