개념
트리는 원소들을 계층적으로 저장하는 추상 데이터 타입이다. 최상위 원소를 제외하고, 각각의 원소는 하나의 부모 원소와 0 또는 여러 개의 자식 원소를 갖고 있다.
특성
일반적으로 트리는 다음 조건을 만족하는 하나 이상의 노드(node)들로 구성된 유한 집합 T를 말한다.
- T의 원소 중 근 노드(root node)라 불리우는 특정한 1개의 노드가 존재한다.
- 근 노드를 제외한 나머지 노드들은 서로 분리된 부분 집합이다.
- 순환(cycle)을 허용하지 않는다. 처음과 끝의 경로가 같은 단순 경로를 사이클(cycle)이라 한다. 트리는 그래프의 부분 집합으로서, 그래프를 형성하는 정점 가운데서 어떠한 두 정점 사이에도 사이클이 형성되지 않은 연속된 그래프(connected graph)라고도 할 수 있다.
용어
- 노드(node)는 트리를 구성하는 기본 요소이며 레코드, 원소, 데이터 필드 등과 같이 단위 정보를 나타내는 항목을 말한다.
- 근 노드(root node)는 트리의 제일 상위 계층에 속하는 노드이며, 1 레벨에 있는 단 한 개의 노드이다.
- 서브 트리(subtree)는 트리에서 근 노드를 제거했을 때 생기는 하위 계층의 트리를 말한다. 각 서브 트리의 근 노드를 제거하면 다시 새로운 서브 트리가 생긴다.
- 차수(degree)는 어느 노드에서의 부 트리의 개수 혹은 가지의 개수이다.
- 트리의 차수는 트리를 형성하는 모든 노드의 차수 중에서 최대치를 말한다.
- 단 노드 또는 단말 노드(terminal node 또는 leaf)는 차수가 0인 노드 즉 서브 트리가 없는 노드를 말한다.
- 간 노드 또는 가지 노드(nonterminal node)는 차수가 0이 아닌 노드 즉 부 트리가 있는 노드이다. 단말 노드를 제외한 모든 노드가 해당된다.
- 부모 노드(parent node) 임의의 노드에서 바로 상위의 계층에 있는 노드이다.
- 형제 노드(brother node)는 부모 노드가 같은 노드들의 집합이다.
- 자식 노드(children node)는 임의의 노드에서 바로 하위의 계층에 있는 노드들의 집합이다.
- 조상(ancestors)은 특정 노드에서 근 노드에 이르기까지의 경로 상에 존재하는 모든 노드들의 집합이다.
- 자손(descendants)는 특정 노드의 하위 계층에 있는 모든 노드들의 집합이다.
- 레벨(level)은 근 노드를 레벨 1로 하여 하위계층으로 내려가면서 1씩 증가하는 번호이다. 레벨 m인 노드의 자식 노드는 레벨 m+1로 정의 하는데 계층 번호가 된다.
- 높이(height) 또는 깊이(depth)는 트리의 단말 노드의 레벨 중에서 최대인 레벨수이다.
- 트리군(forest)는 서로 독립된 즉 분리된 트리들의 집합이다.
추상 데이터 타입(ADT)
- p.parent(): p의 부모를 반납한다. p가 루트이면 에러가 발생한다.
- p.children(): 노드 p의 자식들을 포함하는 위치 리스트를 반환한다.
- p.is_root(): p가 루트이면 true 아니면 false를 반환한다.
- p.is_external(): p가 외부노드이면 true 아니면 false를 반환한다.
- size(): 트리 내의 노드의 개수를 반환한다.
- empty(): 트리가 비었으면 참을 아니면 거짓을 반환한다.
- root(): 트리의 루트에 대한 위치를 반환한다. 트리가 비었으면 에러가 발생한다.
- positions(): 트리의 모든 노드의 위치 리스트를 반환한다.
반응형
댓글