트리 용어

(2020-06-17)

트리 관련 주요 용어, Root Node, 루트 노드, Leaf Node, 리프 노드, Tree Order, 트리 차수, Tree Depth, 트리 깊이, Tree Degree, 트리 디그리

1. 트리 관련 주요 용어

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

  ㅇ 가지/관계/분기/링크 (Branch/Edge/Link)
     - 노드노드 간의 연결선
     - (드물게, 뿌리(root)와 잎(leaf) 사이의 모든 노드를 일컫기도 함)

  ㅇ 부(하위) 트리의 갯수/간선수/차수 (Degree)
     - 각 노드가 지닌 가지의 수 (한 노드에 연결된 자식 노드의 수) 
        . 例) A의 디그리 = 2, B의 디그리 = 3, C의 디그리 = 2
           .. 즉, 부 트리(subtree)의 갯수를 그 노드의 degree 라고 함
     * [참고] 모든 노드차수가 2 이하인 트리이진 트리 참조

  ㅇ 계수 (Order) (드물게,차수라고도 함)
     - 자식 노드들 중 최대 개수
        . 例) B가 가장 많은 자식 3을 갖으므로 계수 = 3

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

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

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

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

  ㅇ 자식(child), 부모(parent) 노드, 형제(brother) 노드
     - 부모 노드(parent node)  例)         : D,E,F의 부모노드는 B
     - 자식 노드(child node)   例)         : B의 자식노드는 D,E,F
     - 형제 노드(brother node,sibling) 例) : D,E,F는 동일한 부모를 갖는 형제노드


[트리] 1. 트리 2. 트리 용어 3. 트리 종류 4. 이진 트리 5. 이진 탐색 트리 6. 스패닝 트리 7. 트리 순회 8. B 트리 9. 10. 멀티캐스트 트리 11. 결정 트리

 
        최근수정     요약목록     참고문헌