트리 용어

(2020-08-10)

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

Top 정보기술(IT) 프로그래밍 자료구조 비선형 자료구조 (그래프,트리) 트리

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는 동일한 부모를 갖는 형제노드
     - 선조 (ancestor) : 부모 노드와 그의 부모들을 총칭
     - 자손 (descendant) : 자식 노드와 그 자식들을 총칭



Copyrightⓒ written by 차재복 (Cha Jae Bok)