트리(Tree Data Structure)

트리

정의

• 자식 노드와 부모 노드로 이루어진 계층적 구조를 가짐
• 무방향 그래프의 일종이자 사이클이 없는 자료구조
  

  특징

1. 부모, 자식 계층 구조를 가지며 같은 경로상에서 위에 있으면 부모, 밑에 있으면 자식이라 함
2. V(노드 수) - 1 = E(간선 수)라는 특징을 가짐
3. 임의의 두 노드 사이의 경로는 반드시 하나만 있음

   노드 종류

   루트 노드

• 가장 위에있는 노드
• 보통 트리 문제가 나오고 트리를 탐색할 때 루느 노드를 중심으로 탐색하면 쉽게 풀림

  내부 노드

• 루트 노드와 리프 노드 사이에 있는 노드를 뜻함

  리프 노드

• 자식 노드가 없는 노드
  

  높이와 레벨

  깊이

• 트리에서 깊이는 각 노드마다 다르며 루트 노드에서 측정해 최단거리로 갔을 때 거리를 의미

  높이

• 루트 노드부터 리프 노드까지의 거리 중 가장 긴 거리를 의미
• 위의 사진에서 높이는 3임

  레벨

• 문제마다 조금씩 다르지만 보통 깊이와 같은 의미를 가짐
• 1번 노드를 0레벨, 2,3번 노드를 1레벨이라 할 수 있으며 1번 노드를 1레벨부터 새는 경우도 있음

  서브트리

• 트리내 하위 집합을 서브트리라 함
• 트리내의 부분 집합이라 보면 됨

  숲(Forest)

• 트리로 이루어진 집합을 숲이라고 함