트리

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

• 리프 노드 : 가장 끝에 있는 노드(자식 노드가 없음)

• 루트 노드 : 가장 첫 번째 노드

• 내부 노드 : 루트 노드와 리프 노드 사이에 있는 노드

• 위 : 부모

• 아래 : 자식

• 계층적 구조

• 사이클 : 루프를 도는 행위?

그래프

• 정점과 간선의 집합
• 정점(vertex)의 수에서 간선(edge)의 수를 빼면 1이다.
  • V - 1 = E

트리의 깊이와 레벨

• 깊이 : 트리에서의 깊이는 각각의 노드마다 다르며 루트 노드에서 특정 노드까지 최단거리로 갔을 때 거리

  • 4번 : 2칸
  • 9번 : 3칸

• 높이 : 루트노드부터 리프노드까지의 거리 중 가장 긴 거리

• 레벨 : 깊이와 비슷한 의미 , 문제에서 루트노드를 lv0이냐 lv1이냐에 따라 다름

• 숲 : 트리로 이루어진 집합