CS Study/자료구조

트리

danalee252 2022. 4. 4. 20:03

트리란?

  • 하나의 루트 노드를 가지며, 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를 할 수 있을 정도로 균형이 잡혀 있는 트리
  • 이진 힙
    트리의 마지막 단계에서 오른쪽 부분을 뺀 나머지 부분이 가득 채워져 있는 완전 이진 트리
    최소 힙: 각 노드의 원소가 자식들의 원소보다 작다.
    최대 힙: 각 노드의 원소가 자식들의 원소보다 크다.

'CS Study > 자료구조' 카테고리의 다른 글

힙이란?  (0) 2022.04.08
스택(Stack), 큐(Queue)  (0) 2022.03.11