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

트리(Tree)

이미지 출처: https://monsieursongsong.tistory.com/6

• 스택/큐와는 다른 비선형 구조이다.
• 여러 데이터가 계층 구조 안에서 서로 연결된 형태를 나타낼 때 사용된다.
• 정점을 노드(Node) 라고 하고 노드와 노드를 연결하는 선을 가지(Edge) 라고 한다.

관련 용어

• Root node (뿌리 노드)
  : 트리 구조에서 최상위에 있는 노드

• Parent node (부모 노드)
  : 어떤 노드에서 자신과 인접한 노드들 중 뿌리 노드로 향하는 노드

• Child node (자식 노드)
  : 어떤 노드에서 자신과 인접한 노드들 중 뿌리 노드의 반대 방향으로 향하는 노드

• Leaf node (단말 노드)
  : 자식 노드가 없는 노드

• Sibling node (형제 노드)
  : 부모 노드 가 같은 다른 노드

• Sub tree (부트리)
  : 큰 트리(전체)에 속하는 작은 트리

• Degree (차수)
  : 자식 노드의 개수

• Length (길이)
  : 임의의 두 노드를 시작 노드, 도착 노드로 하는 경로에서 거치게 되는 노드의 수

• Depth (깊이)
  : 뿌리 노드에서 해당 노드까지의 길이

• Level (레벨)
  : 깊이가 같은 노드의 집합 (각 층별로 숫자를 매김)

• Height (높이)
  : 단말 노드까지의 길이 (최고 레벨)

트리의 종류

• 이진 트리
  : 모든 노드의 차수가 2 이하인 트리
• 전 이진 트리
  : 모든 노드의 차수가 0 또는 2인 트리
• 포화 이진 트리
  : 모든 단말 노드의 깊이가 같은 이진 트리
• 완전 이진 트리
  : 포화 이진 트리에서 오른쪽부터 제거된 트리
  = 빈 곳이 없어야 하고 마지막 레벨 노드가 왼쪽에 몰려있어야 한다.