트리(Tree) 개념 정리

트리(Tree) 개념 정리

트리 (Tree) 란 ?

노드들과 노드들을 연결하는 간선, 사이클이 없는 하나의 연결 그래프이며, DAG(방향성이 있는 비순환 그래프)의 한 종류이다.

트리 용어

노드 Node : 트리를 구성하는 기본 요소

Node : 트리를 구성하는 기본 요소 간선 Edge : 노드와 노드 간의 연결선

Edge : 노드와 노드 간의 연결선 루트 노드 Root Node : 트리 구조에서 부모가 없는 최상위 노드

Root Node : 트리 구조에서 부모가 없는 최상위 노드 부모 노드 Parent Node : 자식 노드를 가진 노드

Parent Node : 자식 노드를 가진 노드 자식 노드 Child Node : 부모 노드의 하위 노드

Child Node : 부모 노드의 하위 노드 형제 노드 Sibling Node : 같은 부모를 가지는 노드

Sibling Node : 같은 부모를 가지는 노드 외부 노드 External Node, 단말 노드 Terminal Node, 리프 노드 Leaf Node : 자식 노드가 없는 노드

External Node, Terminal Node, Leaf Node : 자식 노드가 없는 노드 내부 노드 Internal Node, 비 단말 노드 Non-Terminal Node, 가지 노드 Branch Node : 자식 노드 하나 이상 가진 노드

Internal Node, Non-Terminal Node, Branch Node : 자식 노드 하나 이상 가진 노드 깊이 Depth : 루트에서 어떤 노드까지의 간선 수

Depth : 루트에서 어떤 노드까지의 간선 수 높이 Height : 어떤 노드에서 리프 노드까지 가장 긴 경로의 간선 수

Height : 어떤 노드에서 리프 노드까지 가장 긴 경로의 간선 수 차수 Degree : 노드의 자식 수

Degree : 노드의 자식 수 크기 Size : 자신을 포함한 자손의 노드 수

Size : 자신을 포함한 자손의 노드 수 Level : 루트에서 어떤 노드까지의 간선 수

: 루트에서 어떤 노드까지의 간선 수 Path : 한 노드에서 다른 한 노드에 이르는 길 사이에 놓여있는 노드들의 순서

: 한 노드에서 다른 한 노드에 이르는 길 사이에 놓여있는 노드들의 순서 Path Length : 해당 경로에 있는 총노드의 수

: 해당 경로에 있는 총노드의 수 Width : 레벨에 있는 노드 수

: 레벨에 있는 노드 수 Breadth : 리프 노드의 수

: 리프 노드의 수 Distance : 두 노드 사이의 최단 경로에 있는 간선의 수

: 두 노드 사이의 최단 경로에 있는 간선의 수 Order : 부모 노드가 가질 수 있는 최대 자식의 주

from http://boss-cat.tistory.com/16 by ccl(A) rewrite - 2021-10-21 03:27:10