자료구조 트리

Tree

노드로 이어진 자료 구조

  1. 하나의 루트 노드를 갖는다.
  2. 루트 노드는 0개 이상의 자식 노드를 갖는다.
  3. 비선형 자료구조로 계층적 관계를 표현한다. (ex: 디렉토리)

용어

  • 루트노드 : 부모가 없는 노드
  • 단말노드(leaf node) : 자식이 없는 노드
  • 내부노드(internal node) : 단말 노드가 아닌 노드
  • 간선(edge) : 노드를 연결하는 선
  • 형제(sibling) : 같은 부모를 가지는 노드
  • 노드의 크기(size) : 모든 노드의 갯수
  • 노드의 깊이(depth) : 루트에서 특정 노드까지 진입하는데 거쳐야 하는 간선의 수
  • 노드의 레벨 : 트리의 특정 깊이를 가지는 노드의 집합

    ?

  • 노드의 차수(degree) : 하위 트리 개수 / 간선 수 = 각 노드가 가진 가지의 수
  • 트리의 차수(degree of tree): 트리의 최대 차수
  • 트리의 높이(height) : 루트 노드에서 가장 깊이 있는 노드의 깊이

특징

  • 그래프의 한 종류이며, '최소 연결 트리'라고 불린다
  • 트리는 계층 모델이다
  • 노드가 N개인 트리는 항상 N-1개의 간선을 가진다
  • 루트에서 특정 노드로 가는 경로는 유일하다
  • 임의의 두 노드간의 경로도 유일하다
  • 한개의 루트 노드를 가지며, 자식 노드는 하나의 부모 노드를 가진다

더 공부할 내용

  • 순회는 Pre-order, In-order, Post-order로 이루어진다.
  • 이진 트리, 이진 탐색 트리, 균형 트리, 비균형 트리, 이진 힙 등
  • 완전 이진 트리, 전 이진 트리, 포화 이진 트리