트리 구조
"오늘의AI위키"의 AI를 통해 더욱 풍부하고 폭넓은 지식 경험을 누리세요.
1. 개요
트리 구조는 그래프의 일종으로, 노드와 간선으로 구성되며 주로 유향 루트 트리가 사용된다. 트리 구조는 가계도와 유사하게 노드 간의 관계를 표현하며, 루트 노드, 리프 노드, 내부 노드 등의 용어를 사용한다. 자식 노드에 순서가 있는 순서 트리와 순서가 없는 트리가 있으며, 컴퓨터에서는 동적 메모리 할당, 포인터, 배열 등을 사용하여 구현한다. 트리 구조의 탐색 방법으로는 깊이 우선 탐색(DFS)과 너비 우선 탐색(BFS)이 있으며, 주요 연산으로는 항목 수 계산, 탐색, 추가, 삭제 등이 있다. 트리 구조는 자식 노드의 수, 균형 여부, 종류에 따라 이진 트리, 다항 트리, 균형 트리, 힙, 디지털 트리 등으로 분류되며, 디렉토리 구조, 데이터베이스 인덱스, 데이터 정렬 등 컴퓨터 분야에서 다양한 용도로 활용된다.
더 읽어볼만한 페이지
- 추상 자료형 - 리스트 (컴퓨팅)
리스트는 컴퓨터 과학에서 항목들을 순서대로 저장하고 관리하는 기본적인 자료 구조이며, 다양한 연산을 지원하고 연결 리스트나 동적 배열 등으로 구현되며 큐, 스택 등 다른 자료형의 기반이 된다. - 추상 자료형 - 스택
스택은 후입선출(LIFO) 원칙에 따라 데이터를 관리하는 추상 자료형으로, push 연산으로 데이터를 쌓고 pop 연산으로 가장 최근 데이터를 제거하며, 서브루틴 호출 관리, 수식 평가, 백트래킹 등에 활용된다. - 재귀 - 무한 루프
무한 루프는 컴퓨터 프로그램에서 루프가 종료되지 않고 무한히 반복되는 현상으로, 프로그램 오류나 의도적인 경우에 발생하며 시스템 응답 불능을 초래하거나 특정 상황에서 사용되기도 한다. - 재귀 - 점화식
점화식은 수열의 각 항을 이전 항들의 함수로 표현하는 방정식으로, 피보나치 수열, 로지스틱 맵, 이항 계수 등의 예시가 있으며, 선형대수학이나 Z변환 등을 이용하여 풀고 다양한 분야에 응용된다. - 트리 구조 - 덴드로그램
덴드로그램은 데이터 분석에서 데이터 포인트 간 계층적 관계를 시각적으로 표현하는 나무 형태의 다이어그램으로, 군집 분석에서 클러스터 간 유사성을 나타내기 위해 활용되며 다양한 분야에 응용된다. - 트리 구조 - 프림 알고리즘
프림 알고리즘은 그래프의 최소 비용 신장 트리를 찾는 탐욕 알고리즘으로, 최소 가중치를 가진 간선을 선택하여 트리를 확장하며, 시간 복잡도는 사용되는 자료 구조에 따라 달라진다.
| 트리 구조 | |
|---|---|
| 개요 | |
| 유형 | 자료 구조 |
| 분류 | 추상 자료형 |
| 발명가 | 아서 케일리 |
| 관련 자료 구조 | 그래프 힙 |
| 정의 | |
| 정의 | 계층적인 구조를 표현하는 자료 구조. 나무를 거꾸로 한 모양으로, 노드와 간선으로 이루어져 있다. |
| 루트 노드 | 가장 위에 있는 노드. 부모 노드가 없는 노드. |
| 부모 노드 | 자식 노드를 가지고 있는 노드. |
| 자식 노드 | 부모 노드를 가지는 노드. |
| 리프 노드 | 자식 노드가 없는 노드. |
| 내부 노드 | 리프 노드가 아닌 노드. |
| 일반적인 용도 | |
| 사용 예시 | 데이터베이스 인덱스 운영 체제의 파일 시스템 컴퓨터 네트워크의 라우팅 테이블 프로그램의 구문 트리 의사결정 트리 |
| 표현 방식 | 목록 중첩된 튜플 그래픽 |
| 종류 | |
| 종류 | 이진 트리 B-트리 AVL 트리 레드-블랙 트리 트라이 힙 |
| 탐색 알고리즘 | |
| 탐색 알고리즘 | 너비 우선 탐색 깊이 우선 탐색 |
2. 용어
트리 구조는 일반적인 그래프와 마찬가지로 노드(정점)와 노드를 연결하는 에지(변) 또는 링크로 표현되지만, 트리 구조에서는 특히 유향 루트 트리가 자주 사용된다.[1]
노드 간의 관계는 가계도에 비유한 용어로 표현된다.
- '''루트 노드(root node)'''는 부모 노드가 없는 최상위 노드이다. 하나의 트리 구조에는 최대 하나의 루트 노드만 존재한다.
- '''리프 노드(leaf node)'''는 자식 노드가 없는 최하위 노드이다. 하나의 트리에는 여러 개의 리프 노드가 존재할 수 있다.
- '''내부 노드'''(internal node, inner node)는 자식 노드를 가지는 노드, 즉 리프 노드가 아닌 노드이다.
- '''높이'''(height)는 어떤 노드에서 그 노드의 자손인 리프 노드까지의 에지 수의 최댓값이다. 루트 노드의 높이는 그 트리 구조의 높이이다.
- '''깊이'''(depth)는 어떤 노드에서 루트 노드까지의 에지 수이다. 루트 노드의 깊이는 0이다.
- '''부분 트리(subtree)'''는 트리 구조의 일부이며, 그 자체로도 완전한 트리 구조를 이루는 부분이다. 트리 구조 ''T''의 임의의 노드는 그 하위의 모든 노드와 함께 ''T''의 부분 트리를 구성한다. 루트 노드를 정점으로 하는 부분 트리는 그 트리 구조 전체와 같다. 루트 노드 이외를 정점으로 하는 부분 트리를 '''진부분 트리'''(proper subtree)라고 한다.
- '''숲'''(forest)은 트리의 집합이다. 그래프 이론에서 숲은 폐로를 갖지 않는 비연결 그래프이다.
3. 자식 노드의 순서성
노드의 자식 노드들 사이에 순서가 없는 트리와 순서가 있는 트리가 있다. 순서가 있는 트리를 구현하려면 자식 노드를 리스트에 넣거나 각 에지(가지)에 서로 다른 자연수를 부여하는 등의 방법으로 자식 노드들 사이에 순서를 부여한다. 이것이 '''순서 트리'''(ordered tree|오더드 트리영어)이다. 순서 트리의 응용으로는 이진 탐색 트리 등이 있다. 컴퓨터 내의 자료 구조로서는 순서가 없는 자료 구조는 (집합형처럼 존재는 하지만) 그다지 일반적이지 않기 때문에, 일반적인 구현에서는 자연스럽게 순서 트리가 된다.
4. 구현 방법
컴퓨터에서 트리 구조를 구현하는 방법은 다양하다. 전형적인 구현 방법으로는 동적 메모리 할당으로 노드를 나타내는 구조체의 영역을 확보하고, 포인터로 부모 노드나 자식 노드를 참조하는 방식이 있다.
- 각 노드가 자식 노드에 대한 포인터 목록을 가진다.
- 각 노드가 부모 노드에 대한 포인터를 가진다.
- 각 노드가 부모 노드와 자식 노드에 대한 포인터 목록을 가진다.
- 각 노드가 첫째 자식 노드에 대한 포인터와 다음 형제 노드에 대한 포인터를 가진다.
그 외에도, 배열을 사용하여 구현할 수 있다. 이 경우 포인터가 아니라 인덱스에 의해 부모-자식 관계가 결정된다. (예: 이진 힙)
5. 탐색 방법
트리 구조의 '''탐색'''(traverse)이란 트리 구조에 있는 모든 노드를 한 번씩 체계적으로 조사하는 처리이다. 연결 리스트나 1차원 배열과 같은 선형적인 데이터 구조에서는 탐색이 보통 앞에서부터 순서대로 이루어진다(뒤에서부터 탐색하는 방법도 있다). 트리 구조의 탐색에는 아래와 같은 방법들이 있다. 아래 알고리즘은 이진 트리에 관한 것이지만, 다항 트리에도 응용 가능하다.
깊이 우선 탐색은 현재 노드를 조사하고, 그 자식 노드에 대해 같은 작업을 반복한다. 따라서 재귀 호출로 쉽게 표현할 수 있다(루프로도 구현 가능하다). 탐색 방법은 노드를 조사하는 순서에 따라 다음 세 가지로 분류된다(어떤 방법이든 루트에서 탐색을 시작한다).
- 전위 순회 (pre-order|전위 순회영어)
# 루트 노드를 조사한다.
# 있다면, 왼쪽 부분 트리를 전위 순회한다.
# 있다면, 오른쪽 부분 트리를 전위 순회한다.
: 이진 탐색 트리의 복사본을 만들 때 자주 사용된다. 또한, 수식의 구문 트리에서 폴란드 표기법 표현을 얻는 데에도 사용된다.
- 중위 순회 (in-order|중위 순회영어)
# 있다면, 왼쪽 부분 트리를 중위 순회한다.
# 루트 노드를 조사한다.
# 있다면, 오른쪽 부분 트리를 중위 순회한다.
: 다중 트리에서는 정의되지 않는다. 이진 탐색 트리에서는 중위 순회에 의해 탐색 순서가 정렬된 순서가 되므로 자주 사용된다.
- 후위 순회 (post-order|후위 순회영어)
# 있다면, 왼쪽 부분 트리를 후위 순회한다.
# 있다면, 오른쪽 부분 트리를 후위 순회한다.
# 루트 노드를 조사한다.
- 레벨 순(level-order)
: 너비 우선 탐색은 깊이가 같은 노드를 얕은 쪽부터 순서대로 탐색한다.
| 탐색 방법 | 예시 (왼쪽 이진 탐색 트리 기준) |
|---|---|
| -- |
'''전위 순회'''('''n''')
: n 처리
: 각각의 (n의 자식 노드 i)에 대해
:: 전위 순회(i)
'''중위 순회'''('''n''')
: 만약 (n에 왼쪽 자식 노드가 있다면)
:: 중위 순회(n의 왼쪽 자식 노드)
: n 처리
: 만약 (n에 오른쪽 자식 노드가 있다면)
:: 중위 순회(n의 오른쪽 자식 노드)
'''후위 순회'''('''n''')
: 각각의 (n의 자식 노드 i)에 대해
:: 후위 순회(i)
: n 처리
이러한 구현에서는, 트리 구조의 높이만큼 콜 스택 영역이 필요하다. 균형이 유지되지 않은 트리에서는, 이것이 심각한 문제가 될 수도 있다. 각 노드의 부모 노드의 위치를 기억함으로써 스택을 사용하지 않도록 할 수도 있다.
아래는 레벨 순회의 의사 코드이다.
'''레벨 순회'''('''n''')
: n을 큐에 추가
: while (큐에 요소가 있다면)
:: n ← 큐에서 꺼냄
:: n 처리
:: 각각의 (n의 자식 노드 i)에 대해
::: i를 큐에 추가
또는, 스레드 이진 트리를 사용하는 방법도 있다. Joseph M. Morris가 1979년에 발표했다.[2] 스레드 이진 트리는 자식 노드가 없는 경우, 중위 순회의 앞과 뒤를 각각 왼쪽 자식 포인터와 오른쪽 자식 포인터에 설정해 놓은 트리 구조이다. 이 경우, 자식 노드의 유무는 포인터 이외의 필드로 나타낼 필요가 있다. 이것을 사용하면 중위 순회의 효율이 매우 좋아지지만, 전위 순회나 후위 순회는 일반적인 스택을 사용한 구현이 더 좋다.
6. 주요 연산
- 항목(노드)의 수를 계산한다.
- 특정 항목을 탐색한다.
- 새로운 항목을 트리 구조의 특정 위치에 추가한다.
- 항목을 삭제한다.
- 부분 트리를 삭제한다(가지치기).
- 부분 트리를 추가한다(접붙이기).
- 임의의 노드에서 루트 노드를 찾는다.
7. 트리 구조의 종류
- 자식 노드 수에 따른 분류
- * 이진 트리 - 각 노드가 최대 2개의 자식 노드만 가지는 트리
- ** 이진 탐색 트리
- * 다항 트리 - 3개 이상의 자식 노드를 가지는 노드를 포함하는 트리. 이진 트리가 아닌 트리
- ** 사분 트리
- ** 팔분 트리
- 균형 트리(밸런스 트리) - 모든 리프 노드에 대해 깊이가 거의 같은 트리
- * 균형 이진 탐색 트리 - 균형 트리이면서 동시에 이진 탐색 트리이기도 한 트리
- ** AA 트리
- ** AVL 트리(일반적으로 균형 이진 트리라고 불리지만, 균형 이진 탐색 트리와 혼동하기 쉬우므로 주의)
- ** 희생양 트리
- ** 적흑 트리(2색 트리)
- ** T 트리(T-tree)
- ** 슬플레이 트리
- ** 트리앱
- * 다항 트리
- ** B 트리
B+ 트리, B* 트리
8. 컴퓨터에서의 트리 구조 활용
- 계층 구조를 가진 데이터를 조작한다. 디렉토리 트리, 도메인 이름, 구문 트리, 제어 구조, 결정 트리, XML DOM 트리 등이 있다.
- 정보를 탐색하기 쉽게 한다. 데이터베이스의 인덱스 등에 사용되며, 이 용도의 트리 구조를 '''탐색 트리'''라고도 부른다.
- 데이터의 정렬을 위해 사용한다. 힙 정렬 등에 사용된다.
참조
[1]
일반텍스트
[2]
논문
Traversing binary trees simply and cheaply
본 사이트는 AI가 위키백과와 뉴스 기사,정부 간행물,학술 논문등을 바탕으로 정보를 가공하여 제공하는 백과사전형 서비스입니다.
모든 문서는 AI에 의해 자동 생성되며, CC BY-SA 4.0 라이선스에 따라 이용할 수 있습니다.
하지만, 위키백과나 뉴스 기사 자체에 오류, 부정확한 정보, 또는 가짜 뉴스가 포함될 수 있으며, AI는 이러한 내용을 완벽하게 걸러내지 못할 수 있습니다.
따라서 제공되는 정보에 일부 오류나 편향이 있을 수 있으므로, 중요한 정보는 반드시 다른 출처를 통해 교차 검증하시기 바랍니다.
문의하기 : help@durumis.com