트리
최종 수정 : 25.1.2
트리
선형구조는 자료들이 1 : 1로 연결되어 있는 구조이다. 트리와 그래프는 대표적인 비선형 구조로 노드의 자료들이 1 : 다 또는 다 : 다의 구조를 가진다.
1. 정의
트리는 그래프 중에서 사이클 관계를 포함하지 않는 연결 그래프로서 임의의 노드에서 상위로 연결된 경로가 1개이고, 하위로 연결된 경로가 여러 개를 가지는 계층적 구조를 가진다. 트리는 계층적인 자료구조로 노드와 각 노드들을 연결하는 간선들로 구성된다. 노드 중 최상위 노드를 한 개 가지고 이를 루트라 한다. 루트에 다른 하위 노드들이 간선들로 연결된 비선형 구조의 계층 구조이다. 트리의 응용 분야는 계층적인 조직이나 디렉토리 구조 및 인공지능에서 인간의 의사결정 구조를 표현하는 결정 트리(decision tree)를 표현하는 데 이용된다.
트리의 정의는 다음 조건을 만족하는 하나 이상의 노드들로 구성된 유한 집합 T를 말한다.
- 조건1. T의 원소 중 루트(root) 노드가 반드시 한 개 존재한다.
- 조건2. 루트를 제외한 나머지 노드들은 서로 분리된 부분집합 T1, T2, ... T3로 분리가능하며, 각 T(i = 1, 2, ..., n)도 트리가 된다.
2. 용어
| 노드 (node) |
트리를 구성하는 요소(element, atom)으로 하나의 데이터가 저장된다. 여기서 데이터는 한 개의 값이 아니라 연결 리스트에서의 노드와 같이 여러 개의 값으로 구성된 하나의 레코드가 될 수 있다. |
| 근노드 (root node) |
트리에서 레벨이 가장 높은 1개의 노드를 근노드라 하고 트리의 시작이 된다. |
| 차수 (degree) |
한 노드가 가지고 있는 서브 트리의 수 또는 자노드의 수를 말한다. |
| 단노드 (terminal node) |
차수가 0인 노드를 말하며, 리프(leaf) 노드 = 잎노드 = 터미널(terminal) 노드 = 단노드 와 같은 의미로 사용된다. |
| 비단노드 (non-termnal node) |
차수가 1이상인 노드를 말하며, 간노드라고 하여 사이에 끼인 노드라고 한다. |
| 부노드 (parent) |
어떤 하나의 노드에 대하여 상위에 연결된 노드를 말한다. |
| 자노드 (children & son node) |
특정 노드와 연결된 계층상 바로 아래의 노드를 말한다. |
| 제노드 (brother node & sibling) |
같은 부노드를가지는 노드의 집합 |
| 조상 (ancestors) |
루트부터 특정 노드까지 경로를 형성하는 노드의 집합 |
| 트리의 차수 (degree of tree) |
트리의 모든 노드의 차수 중 최댓값 |
| 노드의 레벨 (level) |
루트가 레벨 1이고, 자노드로 내려갈수록 레벨은 1씩 증가한다. 즉, 노드가 레벨 l 에 속하면 그 자노드는 l + 1 |
| 트리의 높이 & 깊이 (height & depth) |
트리의 레벨 중 최댓값 |
| 경로 (path) |
임의의 노드에서 다른 노드까지의 노드들의 순서 집합 |
| 포리스트 (forest) |
트리에서 루트를 제거했을 때, 생성되는 트리의 집합 |
3. 트리의 표현
1) 부자 관계를 표현하는 방법
순차 리스트로 표현이 가능하고, 연결 리스트로 표현할 수 있다. 또는 구조체를 이용하여 노드와 링크로 구현하는 방법이 있다. 이 구조체를 이용하는 방법은 연결 리스트를 구현하는 것과 같다.
2) 왼쪽 자식 - 오른쪽 형제(left child-right child) 표현 방법
4. 트리의 종류
1) 자노드 수에 따른 분류
일반 트리(General Tree)
☞ 각 노드의 차수에 제한이 없는 트리로 가장 일반적인 트리이나 구현이 복잡하다.
이진 트리(Binary Tree)
☞ 트리의 차수가 2 이하인 트리로, 단순하여 구현하기 쉽다.
2) 순서 트리와 비순서 트리
순서 트리(Ordered Tree)
☞ 노드의 위치가 중요한 의미를 가지는 트리로 위치가 바뀌면 서로 다른 트리이다.
비순서 트리(Oriendted Tree)
☞ 노드 간에 레벨 차이는 중요하지만, 좌우의 위치에 의미가 부여되지 않은 트리이다. 좌우의 위치만 다른 트리는 같은 트리이다.
3) 닮은 트리와 대등한 트리
닮은 트리(Similar Tree)
☞ 구조는 가티만 내용이 다른 트리.
대등한 트리(Equivalent Tree)
☞ 구조뿐만 아니라 노드의 내용까지 완전히 같은 트리.
4) 균형 트리와 완전균형 트리
균형 트리(Height Balanced Tree)
☞ 루트를 기준으로 왼쪽 부 트리와 오른쪽 부 트리의 깊이 차이가 1이하인 트리이다.
완전균형 트리(Completely Height Balanced Tree)
☞ 높이(깊이)가 같은 트리이다.
참고
독학사 교재