밍의 기록들😉

[트리] 트리의 기본 본문

자료구조, 알고리즘/기본다지기

[트리] 트리의 기본

민쓰 2018. 9. 9. 21:54

트리(Tree)

  • 자료구조의 일종
  • 사이클이 없는 그래프
  • 정점(Node, Vertex)
  • 간선(Edge) : 정점간의 관계를 나타냄
  • 정점의 개수 : V / 간선의 개수 : V-1


루트가 있는 트리


  • 1번이 루트(root)임
  • 루트부터 아래로 방향을 정할 수 있음

루트 노드, 리프 노드, 단말 노드, 가지 노드




  • 1번은 루트 노드(root node) 즉, 부모가 없는 최상위 노드
  • 4, 5, 6, 7번은 리프 노드(leaf node) 즉, 맨 마지막 끝 노드
  • 4, 5, 6, 7번은 단말 노드(terminal node)도 됨. 가지를 가지지 않는 노드. 즉 degree가 0인 노드
  • 1, 2, 3번은 가지 노드(branch node) 가지를 가지는 노드. 즉, degree가 0이 아닌 노드


부모와 자식


  • 부모노드(Parent)와 자식노드(Child)
  • 1의 자식은 2와 3
  • 2의 자식은 4와 5
  • 3의 자식은 6과 7


형제


  • 형제 노드(Sibling)
  • 4와 5는 형제
  • 6과 7은 형제
  • 2와 3도 형제
  • 같은 부모를 가지면 형제


깊이, 높이, 레벨


  • 깊이(Depth) : 루트에서 어떤 노드까지의 경로 길이
  • 4의 깊이는 2
  • 높이(Height) : 가장 긴 깊이. 즉 가장 긴 경로 길이
  • 트리의 높이는 2
  • 레벨(Level) : 트리의 특정 깊이를 가지는 노드의 집합
  • 루트의 레벨은 0으로 하는 경우와 1로 하는 경우가 있음
  • 1 노드의 레벨은 1
  • 2와 3 노드의 레벨은 2
  • 4, 5, 6, 7 노드의 레벨은 3



조상과 자손


  • p->q로 갈 수 있을 때
  • p가 q보다 루트에 가까우면
  • p는 q의 조상
  • q는 p의 자손


0 Comments
댓글쓰기 폼