21.08.28 TIL

 

트리 관련 주요 용어

• 노드/마디/정점 (Node/Vertex)
  • 트리를 구성하는 기본 원소
    • ex) A,B,C,D,E,F,G,H,I,J,K,L,M,N

• 가지/관계/분기/링크 (Branch/Edge/Link)
  • 노드와 노드 간의 연결선 (드물게, 뿌리(root)와 잎(leaf) 사이의 모든 노드를 일컫기도 함)
• 부(하위) 트리의 갯수/간선수/차수 (Degree)
  • 각 노드가 지닌 가지의 수 (한 노드에 연결된 자식 노드의 수)
    • ex) A의 디그리 = 2, B의 디그리 = 3, C의 디그리 = 2 즉, 부 트리(subtree)의 갯수를 그 노드의 degree 라고 함
  • 이진 트리 : 모든 노드의 차수가 2 이하인 트리

• 계수 (Order) (드물게,차수라고도 하나 올바른 용어는 아님)
  • 자식 노드들 중 최대 개수
    • ex) B가 가장 많은 자식 3을 갖으므로 계수 = 3

• 깊이 (depth), 높이 (height), 레벨 (level)
  • 깊이 : 루트에서 어떤 노드까지의 경로 길이
    • ex) D의 경로 길이(깊이) : 2
  • 높이 : 가장 긴 깊이
    • ex) 가장 긴 깊이 : 4
  • 레벨(수준) : 같은 깊이
    • ex) A의 레벨 : 1 ; B,C의 레벨 : 2 ; D,E,F,G,H의 레벨 : 3

• 경로 (path), 길이 (length)
  • 경로 (path) : 한 노드에서 다른 한 노드에 이르는 길 사이에 놓여있는 노드들의 순서
  • 경로 길이 (length) : 출발 노드에서 목적 노드까지 거치는 노드의 갯수

• 루트 노드(root node, 뿌리), 리프 노드(leaf node, 잎)
  • 부모가 없는 최상위 루트 노드(트리 자료구조의 진입 노드) : root node
    • ex) 루트 노드 : A
  • 맨 마지막 끝 노드 : leaf node
    • ex) 잎 노드 : F,I,J,K,L,M,N

• 단/끝단/단말 노드 (terminal node), 가지 노드 (branch node), 리프 노드(잎,leaf node)
  • 가지를 가지지 않는 즉 degree가 0 인 노드를 단말 노드(terminal node)라 하며,
    • ex) 단말 노드 : F,I,J,K,L,M,N
  • degree가 0 이 아닌 노드들을 간노드(non-terminal node)/가지노드(branch node)라 함
    • ex) 가지 노드 : A,B,C,D,E,G,H

• 자식(child), 부모(parent) 노드, 형제(brother) 노드
  • 부모 노드(parent node) : ex) D,E,F의 부모노드는 B
  • 자식 노드(child node) : ex) B의 자식노드는 D,E,F
  • 형제 노드(brother node,sibling) : ex) D,E,F는 동일한 부모를 갖는 형제노드
  • 선조 (ancestor) : 부모 노드와 그의 부모들을 총칭
  • 자손 (descendant) : 자식 노드와 그 자식들을 총칭

• 크기(size)
  • 특정 노드가 자신을 포함한 자손의 수
    • ex) 노드 C의 크기 : 6

참고 자료 : http://www.ktword.co.kr/test/view/view.php?no=4726

 

이펙티브 자바, 아이템 14. Comparable을 구현할지 고려하라

https://rockintuna.tistory.com/173

이펙티브 자바, 아이템 14. Comparable을 구현할지 고려하라