트리

트리란?

• 하나의 루트 노드를 가지며, 0개 이상의 자식 노드를 갖고 있다.
• 각 노드들은 간선으로 연결되어 있다.
• 비선형 자료구조이며 계층적 관계를 표현한다.
• 사이클이 없는 하나의 연결그래프이다.
• 노드가 N개인 트리는 항상 N-1개의 간선을 가진다.
• 루트에서 어떤 노드, 또는 임의의 두 노드 간의 경로는 유일하다.
• 순회하는 방법에는 Pre-Order, In-Order, Post-Order가 있다.

관련 용어

• 노드의 크기(Size): 자신을 포함한 모든 자손 노드의 개수
• 노드의 깊이: 루트에서 어떤 노드에 도달하기까지 거쳐야 하는 간선의 수
• 노드의 레벨: 트리의 특정 깊이를 가지는 노드의 집합
• 노드의 차수(Degree): 노드의 자식 수
• 트리의 차수: 트리의 최대 차수
• 트리의 높이: 루트 노드에서 가장 깊숙히 있는 노드의 깊이

트리 순회

아래와 같은 트리가 있다고 할 때, 여러가지 방법으로 순회해보자.

• 전위 순회 (Pre-Order)
  루트노드 -> 왼쪽 서브트리 -> 오른쪽 서브트리의 순서로 순회하는 방식이다. 깊이 우선 순회라고도 한다.
  E -> F -> A -> G -> C -> B -> I -> D -> H
• 중위 순회 (In-Order)
  왼쪽 서브트리 -> 루트노드 -> 오른쪽 서브트리의 순서로 순회하는 방식이다. 대칭 순회라고도 한다.
  G -> A -> C -> F -> E -> I -> B -> H -> D
• 후위 순회 (Post-Order)
  왼쪽 서브트리 -> 오른쪽 서브트리 -> 루트노드의 순서로 순회하는 방식이다. 
  G -> C -> A -> F -> I -> H -> D -> B -> E

트리의 종류

• 이진 트리
  각 노드가 최대 두 개의 자식 노드를 갖는 트리
• 이진 탐색 트리
  모든 노드가 특정 순서를 따르는 속성이 있는 이진 트리 (ex. 모든 왼쪽 자식들 <= n < 모든 오른쪽 자식들)
• 균형 트리 (ex. Red-Black Tree, AVL Tree)
  O(logN) 의 시간복잡도로 insert와 find를 할 수 있을 정도로 균형이 잡혀 있는 트리
• 이진 힙
  트리의 마지막 단계에서 오른쪽 부분을 뺀 나머지 부분이 가득 채워져 있는 완전 이진 트리
  최소 힙: 각 노드의 원소가 자식들의 원소보다 작다.
  최대 힙: 각 노드의 원소가 자식들의 원소보다 크다.