Tree Structure 노트1

 

 

Tree 그래프 이론적 정의 : Tree는 연결된 그래프이며 Cycle이 없음, Root가 있으며 그와 연결된 subtree로 구성된 개체

Tree의 종류 : Rooted Tree/Unrooted Tree, Ordered Tree/Unordered Tree, Directed Tree/Undirected Tree, Binary Tree, k-ary Tree

Ordered Tree/Unordered Tree는 Rooted, Directed Tree/Undirected Tree는 Unrooted

Binary Tree도 Rooted Tree, 한 개의 노드에서 child 노드의 개수가 최대 2개

K-ary Tree는 각 노드에 k이하의 child 노드가 있는 트리

 

Tree에서 사용되는 전문 용어 (taxonomy)

- root, subtree, parents, child, sibling, depth/height, leaf node, internal node, degree, Least Common Ancestor (최단 공통 조상)

internal node != leaf node

degree(차수) : Rooted Tree에서는 child 개수/ Unrooted 에서는 연결된 node들 개수

leaf node는 degree가 0

LCA(Least Common Ancestor) : 특정 노드끼리의 가장 가까운 parent 노드 (최단 공통 조상)

 

트리에 대한 기본 연산

ㆍboolean parents(a, b) : a의 부모가 b인가?

ㆍnodes find_child(a) : a의 자식을 모두 찾기

ㆍnodes sibling(a) : a의 형제 노드 모두 찾기

ㆍnodes root(a) : a가 속한 트리의 root 노드 찾기

ㆍnodes path(a, b) : a에서 b로 가는 길에 있는 모든 노드

ㆍnodes leaf_nodes(T) : 트리 T의 모든 leaf node 출력

ㆍnodes scanning(T) : 트리 T에 있는 노드를 모두 traverse

 

Forest = A set of Trees

 

사분 트리(Quad Tree) : 공간을 순환적으로 분해하는 특성을 갖는 계층적 자료구조. 표현하려는 자료의 유형/공간 분해 과정의 원칙/해상도에 따라 구분

- 표현하려는 자료의 유형 : 사분 트리가 곡선이나 표면과 같이 개체의 경계를 표현하는 경우, 영역이나 볼륨과 같이 개체의 내부를 표현하는 경우

- 공간 분해 원칙 : 각 레벨마다 공간을 일정한 크기의 동일한 부분들로 분해, 입력 자료값에 따라 서로 다른 크기의 공간으로 분해

- 분해의 해상도 : 분해 과정을 몇번이나 적용하는가? 고정/동적

사분할씩 쪼개면서 만드는 트리