트리 용어

(2023-08-03)

트리 관련 주요 용어, Root Node, 루트 노드, Leaf Node, 리프 노드, Tree Degree, 트리 차수, 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

  ㅇ 레벨 (level), 높이 (height), 깊이 (depth)
     - 레벨(수준) : 루트로부터 단순 경로의 길이
        . 例) A(루트)의 레벨 : 0 ;  B,C의 레벨 : 1 ;  D,E,F,G,H의 레벨 : 2
     - 높이 (깊이) : (최대 레벨 값 + 1)
        . 例) 가장 긴 깊이 (높이) : 4
     * 한편, 이진 트리에서, 
        . 레벨 i에서의 최대 노드의 수 : 2i개
        . 높이 j를 갖는 이진 트리의 최대 노드 수 : 2j-1개 

  ㅇ 경로 (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) : 자식 노드와 그 자식들을 총칭

  ㅇ 크기 (size)
     - 특정 노드가 자신을 포함한 자손의 수
        . 例) 노드 C의 크기 : 6

  ㅇ 서브 트리 (subtree)
     - B를 루트로 하는 하위 트리를 A의 왼쪽 서브 트리, 
       C를 루트로 하는 하위 트리를 A의 오른쪽 서브 트리 라고 함

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


Copyrightⓒ written by 차재복 (Cha Jae Bok)       기술용어해설 소액 후원
"본 웹사이트 내 모든 저작물은 원출처를 밝히는 한 자유롭게 사용(상업화포함) 가능합니다"