-
Tree 구조
트리는 위와 같은 구조를 갖고 있습니다.
용어
- node: 트리에서 데이터를 의미
- branch(link): 노드와 노드를 연결
- root node: 최상위 노드
- interior node: 자기자신 아래에 연결된 노드가 있는 형태
- leaf node: 자기자신 아래에 노드가 더이상 연결되어있지 않은 형태
- parent: child 노드들이 연결되어 있는 상위 노드
- child: 부모노드 아래에 연결되어 있는 노드
- sibling: 부모노드 아래에 존재하며 동일한 레벨에 있는 노드
- degree (노드의 degree): 자기자신 아래에 연결된 노드가 몇개가 있는지
- depth: 루트에서 어떤 노드에 도달하기까지 거쳐야 하는 branch(link)의 수
- level: 트리의 특정 depth를 가지는 노드의 집합
- height: 루트노드에서부터 가장 멀리 있는 노드의 depth
- 트리의 degree: 트리의 최대 degree
- 위 그림에서 노드의 최대 degree는 2
Skewed Tree (Degenerate Tree)
Full (Perfect) Tree
Binary Tree
degree가 최대 2 (0 <= degree <= 2)
Quad Tree
degree가 최대 4 (0 <= degree <= 4)
정의
- root 노드를 제외한 모든 노드는 parent 노드를 1개만 가짐
- leaf 노드를 제외한 모든 노드는 child 노드를 1개 이상을 가짐
Tree 자료구조의 다양한 타입
Binary Tree
- Binary Search Tree, Heap, Digital Search Tree
- Red-Black Tree, AA Tree, Splay Tree
Height-Balanced Binary Tree
- AVL Tree, T-Tree
n-Way Tree
- m-Way Tree
- 2-3 Tree, 2-3-4 Tree
Height-Balanced m-Way Tree
- B-Tree, B+-Tree, K-d B-Tree
Spatial Tree
- Quad Tree, Oct Tree, R-Tree
