트리 (Tree) 란 ?
노드들과 노드들을 연결하는 간선, 사이클이 없는 하나의 연결 그래프이다.
트리 용어
- 노드 Node : 트리를 구성하는 기본 요소
- 간선 Edge : 노드와 노드 간의 연결선
- 루트 노드 Root Node : 트리 구조에서 부모가 없는 최상위 노드
- 부모 노드 Parent Node : 자식 노드를 가진 노드
- 자식 노드 Child Node : 부모 노드의 하위 노드
- 형제 노드 Sibling Node : 같은 부모를 가지는 노드
- 외부 노드 External Node, 단말 노드 Terminal Node, 리프 노드 Leaf Node : 자식 노드가 없는 노드
- 내부 노드 Internal Node, 비 단말 노드 Non-Terminal Node, 가지 노드 Branch Node : 자식 노드 하나 이상 가진 노드
- 깊이 Depth : 루트에서 어떤 노드까지의 간선 수
- 높이 Height : 어떤 노드에서 리프 노드까지 가장 긴 경로의 간선 수
- 차수 Degree : 노드의 자식 수
- 크기 Size : 자신을 포함한 자손의 노드 수
- Level : 루트에서 어떤 노드까지의 간선 수
- Path : 한 노드에서 다른 한 노드에 이르는 길 사이에 놓여있는 노드들의 순서
- Path Length : 해당 경로에 있는 총노드의 수
- Width : 레벨에 있는 노드 수
- Breadth : 리프 노드의 수
- Distance : 두 노드 사이의 최단 경로에 있는 간선의 수
- Order : 부모 노드가 가질 수 있는 최대 자식의 주
특징
- Tree는 그래프의 종류로, 계층 모델입니다.
- DAG의 한 종류입니다. DAG란? Directed Acyclic Graphs의 약어로 방향성이 있는 비순환 그래프를 말합니다. DAG는 사이클이 없습니다. 즉, Tree는 사이클이 없다.
- 간선은 항상 정점의 개수 - 1 만큼 가집니다.
- 두 개의 정점 사이는 1개의 경로만 가집니다.
- 부모-자식의 관계를 가지므로 흐름은 top-bottom 또는 bottom-top으로 이루어집니다.
트리의 종류
- 이진트리 : 각 노드의 차수(자식 노드)가 2 이하인 트리
- 이진 탐색 트리 : 순서화된 이진트리
- 균형 트리 : 스스로 균형을 잡는 이진 탐색 트리 (ex. AVL 트리, 레드 블랙 트리)
- 이진 힙 : 노드의 값이 특정한 순서를 가지고 있는 완전 이진트리
- 편향 트리 ( Skew Tree ) : 모든 노드들이 자식을 하나만 가진 트리